Shrinking the Search Space for Clustered Planarity

Chimani, Markus and Klein, Karsten (2013) Shrinking the Search Space for Clustered Planarity. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 90-101 (Official URL:

Full text not available from this repository.


A clustered graph is a graph augmented with a hierarchical inclusion structure over its vertices, and arises very naturally in multiple application areas. While it is long known that planarity—i.e., drawability without edge crossings—of graphs can be tested in polynomial (linear) time, the complexity for the clustered case is still unknown. In this paper, we present a new graph theoretic reduction which allows us to considerably shrink the combinatorial search space, which is of benefit for all enumeration-type algorithms. Based thereon, we give new classes of polynomially testable graphs and a practically efficient exact planarity test for general clustered graphs based on an integer linear program.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_9
Classifications:G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.180 Cluster
ID Code:1300

Repository Staff Only: item control page


Angelini, P., Frati, F., Patrignani, M.: Splitting Clusters to Get C-Planarity. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 57–68. Springer, Heidelberg (2010)

Chimani, M., Gutwenger, C., Jansen, M., Klein, K., Mutzel, P.: Computing Maximum C-Planar Subgraphs. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 114–120. Springer, Heidelberg (2009)

Cornelsen, S., Wagner, D.: Completely connected clustered graphs. J. Discrete Algorithms 4(2), 313–323 (2006)

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)

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)

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)

Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. ACM 21(4), 549–568 (1974)

Jelínek, V., Jelínková, E., Kratochvíl, J., Lidický, B.: Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters. 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., Vyskocil, T.: Small clusters in cycles and eulerian graphs. J. Graph Alg. Appl. 13(3), 379–422 (2009)

Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press (2006)