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

Actions (login required)

View Item View Item