Back to Search
Start Over
Clustering Cycles into Cycles of Clusters
- Source :
- Graph Drawing ISBN: 9783540245285, Graph Drawing
- Publication Year :
- 2004
- Publisher :
- SPRINGER-VERLAG, 2004.
-
Abstract
- In this paper we study the clustered graphs whose underlying graph is a cycle. This is a simple family of clustered graphs that are “highly non connected”. We start by studying 3-cluster cycles, that 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 at each level of the inclusion tree have a cycle structure. Even in this case we show efficient c-planarity testing and drawing algorithms.
Details
- Language :
- English
- ISBN :
- 978-3-540-24528-5
- ISBNs :
- 9783540245285
- Database :
- OpenAIRE
- Journal :
- Graph Drawing ISBN: 9783540245285, Graph Drawing
- Accession number :
- edsair.doi.dedup.....65781249f3e34a1b2454447e9014bf52