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: http://dx.doi.org/10.1007/978-3-662-45803-7_36).

Full text not available from this repository.

Abstract

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
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 22 May 2015 12:48
Last Modified: 22 May 2015 12:48
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1452

Actions (login required)

View Item View Item