A new perspective on clustered planarity as a combinatorial embedding problem

T. Blaesius, I. Rutter

Research output: Contribution to journalArticleAcademicpeer-review

10 Citations (Scopus)

Abstract

The clustered planarity problem (c-planarity) asks whether a hierarchically clustered graph admits a planar drawing such that the clusters can be nicely represented by regions. We introduce the cd-tree data structure and give a new characterization of c-planarity. It leads to efficient algorithms for c-planarity testing in the following cases. (i) Every cluster and every co-cluster (complement of a cluster) has at most two connected components. (ii) Every cluster has at most five outgoing edges.

Moreover, the cd-tree reveals interesting connections between c-planarity and planarity with constraints on the order of edges around vertices. On one hand, this gives rise to a bunch of new open problems related to c-planarity, on the other hand it provides a new perspective on previous results.
Original languageEnglish
Pages (from-to)306-315
JournalTheoretical Computer Science
Volume609
DOIs
Publication statusPublished - 4 Jan 2016
Externally publishedYes

Keywords

  • Graph drawing
  • Clustered planarity
  • Constrained planar embedding
  • Characterization
  • Algorithms

Cite this

@article{f9493a107bf24cce931c7bcf207dce9b,
title = "A new perspective on clustered planarity as a combinatorial embedding problem",
abstract = "The clustered planarity problem (c-planarity) asks whether a hierarchically clustered graph admits a planar drawing such that the clusters can be nicely represented by regions. We introduce the cd-tree data structure and give a new characterization of c-planarity. It leads to efficient algorithms for c-planarity testing in the following cases. (i) Every cluster and every co-cluster (complement of a cluster) has at most two connected components. (ii) Every cluster has at most five outgoing edges.Moreover, the cd-tree reveals interesting connections between c-planarity and planarity with constraints on the order of edges around vertices. On one hand, this gives rise to a bunch of new open problems related to c-planarity, on the other hand it provides a new perspective on previous results.",
keywords = "Graph drawing, Clustered planarity, Constrained planar embedding, Characterization, Algorithms",
author = "T. Blaesius and I. Rutter",
year = "2016",
month = "1",
day = "4",
doi = "10.1016/j.tcs.2015.10.011",
language = "English",
volume = "609",
pages = "306--315",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

A new perspective on clustered planarity as a combinatorial embedding problem. / Blaesius, T.; Rutter, I.

In: Theoretical Computer Science, Vol. 609, 04.01.2016, p. 306-315.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - A new perspective on clustered planarity as a combinatorial embedding problem

AU - Blaesius, T.

AU - Rutter, I.

PY - 2016/1/4

Y1 - 2016/1/4

N2 - The clustered planarity problem (c-planarity) asks whether a hierarchically clustered graph admits a planar drawing such that the clusters can be nicely represented by regions. We introduce the cd-tree data structure and give a new characterization of c-planarity. It leads to efficient algorithms for c-planarity testing in the following cases. (i) Every cluster and every co-cluster (complement of a cluster) has at most two connected components. (ii) Every cluster has at most five outgoing edges.Moreover, the cd-tree reveals interesting connections between c-planarity and planarity with constraints on the order of edges around vertices. On one hand, this gives rise to a bunch of new open problems related to c-planarity, on the other hand it provides a new perspective on previous results.

AB - The clustered planarity problem (c-planarity) asks whether a hierarchically clustered graph admits a planar drawing such that the clusters can be nicely represented by regions. We introduce the cd-tree data structure and give a new characterization of c-planarity. It leads to efficient algorithms for c-planarity testing in the following cases. (i) Every cluster and every co-cluster (complement of a cluster) has at most two connected components. (ii) Every cluster has at most five outgoing edges.Moreover, the cd-tree reveals interesting connections between c-planarity and planarity with constraints on the order of edges around vertices. On one hand, this gives rise to a bunch of new open problems related to c-planarity, on the other hand it provides a new perspective on previous results.

KW - Graph drawing

KW - Clustered planarity

KW - Constrained planar embedding

KW - Characterization

KW - Algorithms

U2 - 10.1016/j.tcs.2015.10.011

DO - 10.1016/j.tcs.2015.10.011

M3 - Article

VL - 609

SP - 306

EP - 315

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -