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

Actions (login required)

View Item View Item