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, Würzburg, Germany , pp. 440-451 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_37).

Full text not available from this repository.

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 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
ID Code:1453

Repository Staff Only: item control page

References

Biedl, T.: Drawing planar partitions I: LL-drawings and LH-drawings. In: SoCG 1998, pp. 287–296. ACM (1998)

Biedl, T., Kaufmann, M., Mutzel, P. Drawing planar partitions II: HH-drawings. In: Hromkovič, J., Sýkora, O. eds. (1998) Graph-Theoretic Concepts in Computer Science. Springer, Heidelberg, pp. 124-136

Bläsius, T., Rutter, I.: Simultaneous PQ-ordering with applications to constrained embedding problems. CoRR abs/1112.0245, 1–46 (2011)

Bläsius, T., Rutter, I.: Simultaneous PQ-ordering with applications to constrained embedding problems. In: SODA 2013. SIAM (2013)

Booth, K.S., Lueker, G.S. (1976) Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. System Sci. 13: pp. 335-379

Chimani, M., Klein, K. Shrinking the search space for clustered planarity. In: Didimo, W., Patrignani, M. eds. (2013) Graph Drawing. Springer, Heidelberg, pp. 90-101

Cornelsen, S., Wagner, D. (2006) Completely connected clustered graphs. J. of Disc. Alg. 4: pp. 313-323

Cortese, P.F., Battista, G., Frati, F., Patrignani, M., Pizzonia, M. (2008) C-planarity of c-connected clustered graphs. J. Graph Alg. Appl. 12: pp. 225-262

Cortese, P.F., Battista, G., Patrignani, M., Pizzonia, M. (2005) Clustering cycles into cycles of clusters. J. Graph Alg. Appl. 9: pp. 391-413

Cortese, P.F., Battista, G., Patrignani, M., Pizzonia, M. (2009) On embedding a cycle in a plane graph. Disc. Math. 309: pp. 1856-1869

Dahlhaus, E. A linear time algorithm to recognize clustered planar graphs and its parallelization. In: Lucchesi, C.L., Moura, A.V. eds. (1998) LATIN’98: Theoretical Informatics. Springer, Heidelberg, pp. 239-248

Battista, G., Frati, F. Efficient C-planarity testing for embedded flat clustered graphs with small faces. In: Hong, S.-H., Nishizeki, T., Quan, W. eds. (2008) Graph Drawing. Springer, Heidelberg, pp. 291-302

Feng, Q.W., Cohen, R.F., Eades, P. Planarity for clustered graphs. In: Spirakis, P.G. eds. (1995) Algorithms - ESA ’95. Springer, Heidelberg, pp. 213-226

Goodrich, M.T., Lueker, G.S., Sun, J.Z. C-planarity of extrovert clustered graphs. In: Healy, P., Nikolov, N.S. eds. (2006) Graph Drawing. Springer, Heidelberg, pp. 211-222

Gutwenger, C., Jünger, M., Leipert, S., Mutzel, P., Percan, M., Weiskircher, R. Advances in c-planarity testing of clustered graphs. In: Goodrich, M.T., Kobourov, S.G. eds. (2002) Graph Drawing. Springer, Heidelberg, pp. 220-235

Hong, S.H., Nagamochi, H.: Two-page book embedding and clustered graph planarity. Tech. Rep. 2009-004, Kyoto University, Depart. Appl. Math. & Phys. (2009)

Jelínek, V., Jelínková, E., Kratochvíl, J., Lidický, B.: Clustered planarity: Embedded clustered graphs with two-component clusters (2009), http://kam.mff.cuni.cz/~bernard/pub/flat.pdf (manuscript)

Jelínek, V., Jelínková, E., Kratochvíl, J., Lidický, B. Clustered planarity: Embedded clustered graphs with two-component clusters (extended abstract). In: Tollis, I.G., Patrignani, M. eds. (2009) Graph Drawing. Springer, Heidelberg, pp. 121-132

Jelínek, V., Suchý, O., Tesař, M., Vyskočil, T. Clustered planarity: Clusters with few outgoing edges. In: Tollis, I.G., Patrignani, M. eds. (2009) Graph Drawing. Springer, Heidelberg, pp. 102-113

Jelínková, E., Kára, J., Kratochvíl, J., Pergel, M., Suchý, O., Vyskočil, T. (2009) Clustered planarity: Small clusters in cycles and eulerian graphs. J. Graph Alg. Appl. 13: pp. 379-422

Lengauer, T. (1989) Hierarchical planarity testing algorithms. J. ACM 36: pp. 474-509