Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Twelfth International Symposium on Graph Drawing, GD 2004
DOI: 10.7155/jgaa.00115
Clustering Cycles into Cycles of Clusters
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.
|
Journal Supporters
|