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.
展开▼
