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 , pp. 303-314(Official URL:

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.

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

Actions (login required)

View Item View Item