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.
Partly done within GRADR – EUROGIGA project no. 10-EuroGIGA-OP-003. Supported by a fellowship within the Postdoc-Program of the German Academic Exchange Service (DAAD).
Chapter PDF
Similar content being viewed by others
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.) WG 1998. LNCS, vol. 1517, pp. 124–136. Springer, Heidelberg (1998)
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.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. System Sci. 13(3), 335–379 (1976)
Chimani, M., Klein, K.: Shrinking the search space for clustered planarity. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 90–101. Springer, Heidelberg (2013)
Cornelsen, S., Wagner, D.: Completely connected clustered graphs. J. of Disc. Alg. 4(2), 313–323 (2006)
Cortese, P.F., Di Battista, G., Frati, F., Patrignani, M., Pizzonia, M.: C-planarity of c-connected clustered graphs. J. Graph Alg. Appl. 12(2), 225–262 (2008)
Cortese, P.F., Di Battista, G., Patrignani, M., Pizzonia, M.: Clustering cycles into cycles of clusters. J. Graph Alg. Appl. 9(3), 391–413 (2005)
Cortese, P.F., Di Battista, G., Patrignani, M., Pizzonia, M.: On embedding a cycle in a plane graph. Disc. Math. 309(7), 1856–1869 (2009)
Dahlhaus, E.: A linear time algorithm to recognize clustered planar graphs and its parallelization. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN 1998. LNCS, vol. 1380, pp. 239–248. Springer, Heidelberg (1998)
Di 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.) GD 2007. LNCS, vol. 4875, pp. 291–302. Springer, Heidelberg (2008)
Feng, Q.W., Cohen, R.F., Eades, P.: Planarity for clustered graphs. In: Spirakis, P.G. (ed.) ESA 1995. LNCS, vol. 979, pp. 213–226. Springer, Heidelberg (1995)
Goodrich, M.T., Lueker, G.S., Sun, J.Z.: C-planarity of extrovert clustered graphs. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 211–222. Springer, Heidelberg (2006)
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.) GD 2002. LNCS, vol. 2528, pp. 220–235. Springer, Heidelberg (2002)
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.) GD 2008. LNCS, vol. 5417, pp. 121–132. Springer, Heidelberg (2009)
Jelínek, V., Suchý, O., Tesař, M., Vyskočil, T.: Clustered planarity: Clusters with few outgoing edges. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 102–113. Springer, Heidelberg (2009)
Jelínková, E., Kára, J., Kratochvíl, J., Pergel, M., Suchý, O., Vyskočil, T.: Clustered planarity: Small clusters in cycles and eulerian graphs. J. Graph Alg. Appl. 13(3), 379–422 (2009)
Lengauer, T.: Hierarchical planarity testing algorithms. J. ACM 36(3), 474–509 (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bläsius, T., Rutter, I. (2014). A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem. In: Duncan, C., Symvonis, A. (eds) Graph Drawing. GD 2014. Lecture Notes in Computer Science, vol 8871. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-45803-7_37
Download citation
DOI: https://doi.org/10.1007/978-3-662-45803-7_37
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-45802-0
Online ISBN: 978-3-662-45803-7
eBook Packages: Computer ScienceComputer Science (R0)