Clustered Planarity Testing Revisited

Fulek, Radoslav and Kynčl, Jan and Malinović, Igor and Pálvölgyi , Dömötör (2014) Clustered Planarity Testing Revisited. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 428-439 (Official URL:

Full text not available from this repository.


The Hanani–Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this classical result to clustered graphs with two disjoint clusters, and show that a straightforward extension of our result to flat clustered graphs with three or more disjoint clusters is not possible. We also give a new and short proof for a related result by Di Battista and Frati based on the matroid intersection algorithm.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_36
Classifications:G Algorithms and Complexity > G.350 Clusters
G Algorithms and Complexity > G.770 Planarity Testing
M Methods > M.100 Algebraic
P Styles > P.180 Cluster
P Styles > P.540 Planar
Z Theory > Z.750 Topology
ID Code:1452

Repository Staff Only: item control page


Angelini, P., Lozzo, G., Battista, G., Frati, F. Strip planarity testing. In: Wismath, S., Wolff, A. eds. (2013) Graph Drawing. Springer, Heidelberg, pp. 37-48

Biedl, T.C.: Drawing planar partitions III: Two constrained embedding problems. Technical report, RUTCOR, Rutgers University (1998)

Cairns, G., Nikolayevsky, Y. (2000) Bounds for generalized thrackles. Discrete Comput. Geom. 23: pp. 191-206

Chimani, M., Zeranski, R. Upward planarity testing: A computational study. In: Wismath, S., Wolff, A. eds. (2013) Graph Drawing. Springer, Heidelberg, pp. 13-24

Cortese, P.F., Di Battista, G.: Clustered planarity (invited lecture). In: Twenty-First Annual Symposium on Computational Geometry (Proc. SoCG 2005), pp. 30–32. ACM (2005)

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

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

Cunningham, W.H. (1986) Improved bounds for matroid partition and intersection algorithms. SIAM Journal on Computing 15: pp. 948-957

Fraysseix, H., Mendez, P.O., Rosenstiehl, P. (2006) Trémaux trees and planarity. International Journal of Foundations of Computer Science 17: pp. 1017-1029

Fraysseix, H., Rosenstiehl, P. (1985) A characterization of planar graphs by Trémaux orders. Combinatorica 5: pp. 127-135

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

Edmonds, J. Submodular functions, matroids, and certain polyhedra. In: Jünger, M., Reinelt, G., Rinaldi, G. eds. (2003) Combinatorial Optimization - Eureka, You Shrink!. Springer, Heidelberg, pp. 11-26

Feng, Q.-W., Cohen, R.F., Eades, P. How to draw a planar clustered graph. In: Li, M., Du, D.-Z. eds. (1995) Computing and Combinatorics. Springer, Heidelberg, pp. 21-30

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

Fulek, R.: Towards Hanani–Tutte theorem for clustered graphs. In: 40th International Workshop on Graph-Theoretic Concepts in Computer Science (accepted)

Fulek, R., Kynčl, J., Malinović, I., Pálvölgyi, D.: Efficient c-planarity testing algebraically. arXiv:1305.4519

Fulek, R., Pelsmajer, M., Schaefer, M., Štefankovič, D.: Hanani-Tutte, monotone drawings and level-planarity. In: Pach, J. (ed.) Thirty Essays in Geometric Graph Theory, pp. 263–288 (2012)

Gall, F.L.: Powers of tensors and fast matrix multiplication. CoRR abs/1401.7714 (2014)

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

Gutwenger, C., Mutzel, P., Schaefer, M.: Practical experience with Hanani-Tutte for testing c-planarity. In: 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 86–97 (2014)

Hanani, H. (1934) Über wesentlich unplättbare Kurven im drei-dimensionalen Raume. Fundamenta Mathematicae 23: pp. 135-142

Hong, S., Nagamochi, H.: Two-page book embedding and clustered graph planarity. Technical report, Dept. of Applied Mathematics and Physics, University of Kyoto (2009)

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

Ibarra, O.H., Moran, S., Hui, R. (1982) A generalization of the fast LUP matrix decomposition algorithm and applications. J. Algorithms 3: pp. 45-56

Katz, B., Rutter, I., Woeginger, G. An algorithmic study of switch graphs. In: Paul, C., Habib, M. eds. (2010) Graph-Theoretic Concepts in Computer Science. Springer, Heidelberg, pp. 226-237

Kuratowski, K. (1930) Sur le problème des courbes gauches en topologie. Fund. Math. 15: pp. 271-283

Lawler, E.L. (1975) Matroid intersection algorithms. Mathematical Programming 9: pp. 31-56

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

Oxley, J.: Matroid Theory. Oxford University Press (2011)

Pach, J., Tóth, G. (2000) Which crossing number is it anyway?. J. Combin. Theory Ser. B 80: pp. 225-246

Pach, J., Tóth, G. (2004) Monotone drawings of planar graphs. J. Graph Theory 46: pp. 39-47

Pelsmajer, M.J., Schaefer, M., Stasi, D. (2009) Strong Hanani–Tutte on the projective plane. SIAM Journal on Discrete Mathematics 23: pp. 1317-1323

Pelsmajer, M.J., Schaefer, M., Štefankovič, D. (2007) Removing even crossings. J. Combin. Theory Ser. B 97: pp. 489-500

Pelsmajer, M.J., Schaefer, M., Štefankovič, D. (2009) Removing even crossings on surfaces. European Journal of Combinatorics 30: pp. 1704-1717

Schaefer, M.: Hanani-Tutte and related results. To appear in Bolyai Memorial Volume

Schaefer, M. (2013) Toward a theory of planarity: Hanani-tutte and planarity variants. J. Graph Algorithms Appl. 17: pp. 367-440

Tutte, W.T. (1970) Toward a theory of crossing numbers. J. Combin. Theory 8: pp. 45-53

Whitney, H. (1932) Non-separable and planar graphs. Trans. Amer. Math. Soc. 34: pp. 339-362

Williams, V.V.: Multiplying matrices faster than Coppersmith-Winograd. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC 2012, pp. 887–898 (2012