Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00191 Efficient C-Planarity Testing for Embedded Flat Clustered Graphs with Small Faces Giuseppe Di Battista and Fabrizio Frati Vol. 13, no. 3, pp. 349-378, 2009. Regular paper Abstract Let C be a clustered graph and suppose that the planar embedding of its underlying graph is fixed. Is testing the c-planarity of C easier than in the variable embedding setting? In this paper we give a first contribution towards answering the above question. Namely, we characterize c-planar embedded flat clustered graphs with at most five vertices per face and give an efficient testing algorithm for such graphs. The results are based on a more general methodology that sheds new light on the c-planarity testing problem.
|
Revised: August 2008. Reviewed: May 2008. Accepted: November 2008. Submitted: December 2007. Final: December 2008. Published: November 2009. Communicated by Seok-Hee Hong and Takao Nishizeki |
Journal of Graph Algorithms and Applications |