Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00115 Clustering Cycles into Cycles of Clusters Pier Francesco Cortese , Giuseppe Di Battista , Maurizio Patrignani , and Maurizio Pizzonia Vol. 9, no. 3, pp. 391-413, 2005. Regular paper Abstract In this paper we study simple families of clustered graphs that are highly unconnected. We start by studying 3-cluster cycles, which are clustered graphs such that the underlying graph is a simple cycle and there are three clusters all at the same level. We show that in this case, testing the c-planarity can be done efficiently and give an efficient drawing algorithm. Also, we characterize 3-cluster cycles in terms of formal grammars. Finally, we generalize the results on 3-cluster cycles considering clustered graphs that have a cycle structure at each level of the inclusion tree. We present efficient c-planarity testing and drawing algorithms also for this case.
|
Submitted: November 2004. Revised: July 2005. Communicated by Emden Gansner and János Pach |
| Journal of Graph Algorithms and Applications |