Efficient C-Planarity Testing for Embedded Flat Clustered Graphs with Small Faces

Authors

  • Giuseppe Di Battista
  • Fabrizio Frati

DOI:

https://doi.org/10.7155/jgaa.00191

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.

Downloads

Download data is not yet available.

Downloads

Published

2009-11-01

How to Cite

Di Battista, G., & Frati, F. (2009). Efficient C-Planarity Testing for Embedded Flat Clustered Graphs with Small Faces. Journal of Graph Algorithms and Applications, 13(3), 349–378. https://doi.org/10.7155/jgaa.00191