Home Issues About JGAA Instructions for Authors
 
 
Special Issue on Selected Papers from the Fifteenth International Symposium on Graph Drawing, GD 2007
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, Ondřej 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.
Submitted: December 2007.
Reviewed: November 2008.
Revised: February 2009.
Accepted: August 2009.
Final: September 2009.
Published: November 2009.
Communicated by Seok-Hee Hong and Takao Nishizeki
article (PDF)
BibTeX