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. -
PIER FRANCESCO, C., DI BATTISTA, G., Patrignani, M., Pizzonia, M. (2004). Clustering Cycles into Cycles of Clusters. In Graph Drawing, 12th International Symposium, GD 2004, New York, USA, September/October 2004, Revised Selected Papers (pp. 100-110). Berlin : SPRINGER-VERLAG [10.1007/978-3-540-31843-9_12].
Clustering Cycles into Cycles of Clusters
DI BATTISTA, Giuseppe;PATRIGNANI, Maurizio;PIZZONIA, MAURIZIO
2004-01-01
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. -I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
