A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem

Bläsius, Thomas and Rutter, Ignaz (2014) A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014 , pp. 440-451(Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_37).

Full text not available from this repository.


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 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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-662-45803-7_37
Classifications: G Algorithms and Complexity > G.350 Clusters
G Algorithms and Complexity > G.770 Planarity Testing
M Methods > M.900 Tree
P Styles > P.180 Cluster
P Styles > P.540 Planar
Z Theory > Z.750 Topology
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1453

Actions (login required)

View Item View Item