Clustered Planarity: Small Clusters in Cycles and Eulerian Graphs

Abstract

We present several polynomial-time algorithms for c-planarity testing for cluster hierarchy C containing clusters of size at most three. The main result is an O(|C|³ + n)-time algorithm for clusters of size at most three on a cycle. The result is then generalized to a special class of Eulerian graphs, namely graphs obtained from a 3-connected planar graph of fixed size k by multiplying and then subdividing edges. An O(3^k ·k ·n³)-time algorithm is presented. We further give an O(|C|² + n)-time algorithm for general 3-connected planar graphs.