Technical Report RT-DIA-91-2004: Clustering Cycles into Cycles of Clusters

In this paper we study simple families 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 have a cyclestructure at each level of the inclusion tree. Even in this case we show efficient c-planarity testing and drawing algorithm