Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00192 Clustered Planarity: Small Clusters in Cycles and Eulerian Graphs Eva Jelínková , Jan Kára , Jan Kratochvíl , Martin Pergel , Ondrej Suchý , and Tomáš Vyskocil Vol. 13, no. 3, pp. 379-422, 2009. Regular paper 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|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.
|
Reviewed: November 2008. Final: September 2009. Published: November 2009. Submitted: December 2007. Revised: February 2009. Accepted: August 2009. Communicated by Seok-Hee Hong and Takao Nishizeki |
| Journal of Graph Algorithms and Applications |