Clustered Planarity: Small Clusters in Cycles and Eulerian Graphs
Eva Jelínková, Jan Kára, Jan Kratochvı́l, Martin Pergel, Ondřej Suchý, Tomáš Vyskočil · Journal of Graph Algorithms and Applications · 2009
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|3 + 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(3k ·k ·n3)-time algorithm is presented. We further give an O(|C|2 + n)-time algorithm for general 3-connected planar graphs.