Clustered Planarity: Small Clusters in Eulerian Graphs

Jelínková, Eva and Kára, Jan and Kratochvíl, Jan and Pergel, Martin and Suchý, Ondrej and Vyskocil, Tomás (2008) Clustered Planarity: Small Clusters in Eulerian Graphs. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 303-314 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_30).

Full text not available from this repository.

Abstract

We present several polynomial-time algorithms for c-planarity testing for clustered graphs with clusters of size at most three. The most general result concerns a special class of Eulerian graphs, namely graphs obtained from a fixed-size 3-connected graph by multiplying and then subdividing edges. We further give algorithms for 3-connected graphs, and for graphs with small faces. The last result applies with no restrictions on the cluster size.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_30
Classifications:G Algorithms and Complexity > G.350 Clusters
G Algorithms and Complexity > G.770 Planarity Testing
ID Code:847

Repository Staff Only: item control page

References

S. Cornelsen and D. Wagner: Completely Connected Clustered Graphs, Journal of Discrete Algorithms 4(2): 313-323, 2006

Cortese P. F., Di Battista G., Patrignani M., Pizzonia M.: Clustering Cycles into Cycles of Clusters, Journal of Graph Algorithms and Applications, Special Issue on the 2004 Symposium on Graph Drawing, GD '04. 9(3):391-413. 2005.

E. Dahlhaus: Linear time algorithm to recognize clustered planar graphs and its parallelization, In C. Lucchesi, editor, LATIN '98, 3rd Latin American symposium on theoretical informatics, Campinas, Brazil, April 20-24, 1998, volume 1380 of LNCS, 239-248, 1998.

Q. W. Feng, R. F. Cohen, and P. Eades.: Planarity for clustered graphs, In P. Spirakis, editor, Symposium on Algorithms (Proc. ESA '95), volume 979 of LNCS, 213-226, Springer-Verlag, 1995.

C. Gutwenger, M. Jünger, S. Leipert, P. Mutzel, M. Percan, and R. Weiskircher: $C$-planarity testing of clustered graphs, In S. G. Kobourov and M. T. Goodrich, editor, Proc. Graph Drawing 2002 (GD'2002), volume 2528 of LNCS, 220-235, Springer-Verlag, 2002.

C. Gutwenger, M. Jünger, S. Leipert, P. Mutzel, M. Percan, and R. Weiskircher: Subgraph induces planar connectivity augmentation, In 29-th Workshop on Graph-Theoretic Concepts in Computer Science (WG 2003),

volume 2880 of LNCS, 261-272, Springer-Verlag, 2003.