Clustered planarity testing revisited - Fulek, Radoslav; Kynčl, Jan; Malinović, Igor; Pálvölgyi, Dömötör (International Symposium on Graph Drawing, 2014)
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.
published
yes
Keywords: conference paper