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.
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.
Repository Staff Only: item control page