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.
|
Journal Supporters
|