Advances in C-Planarity Testing of Clustered Graphs (Extended Abstract)

Gutwenger, Carsten and Jünger, Michael and Leipert, Sebastian and Mutzel, Petra and Percan, Merijam and Weiskircher, René (2002) Advances in C-Planarity Testing of Clustered Graphs (Extended Abstract). In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 220-235 (Official URL:

This is the latest version of this item.

Full text not available from this repository.


A clustered graph C=(G,T) consists of an undirected graph G and a rooted tree T in which the leaves of T correspond to the vertices of G=(V,E). Each vertex \mu in T corresponds to a subset of the vertices of the graph called "cluster". c-planarity is a natural extension of graph planarity for clustered graphs, and plays an important role in automatic graph drawing. The complexity status of c-planarity testing is unknown. It has been shown in [FCE95,Dah98] that c-planarity can be tested in linear time for c-connected graphs, i.e., graphs in which the cluster induced subgraphs are connected. In this paper, we provide a polynomial time algorithm for c-planarity testing of "almost" c-connected clustered graphs, i.e., graphs for which all nodes corresponding to the non-c-connected clusters lie on the same path in T starting at the root of T, or graphs in which for each non-connected cluster its super-cluster and all its siblings in T are connected. The algorithm is based on the concepts for the subgraph induced planar connectivity augmentation problem presented in [GJL+02]. We regard it as a first step towards general c-planarity testing.

Item Type:Conference Paper
Additional Information:10.1007/3-540-36151-0_21
Classifications:G Algorithms and Complexity > G.490 Embeddings
M Methods > M.600 Planar
G Algorithms and Complexity > G.770 Planarity Testing
G Algorithms and Complexity > G.350 Clusters
ID Code:248

Available Versions of this Item

Repository Staff Only: item control page


G. Di Battista, W. Didimo, and A. Marcandalli. Planarization of clustered graphs (extended abstract). In P. Mutzel, Michael Jünger, and Sebastian Leipert, editors, Graph Drawing, volume 2265 of Lecture Notes in Computer Science, pages 60-74. Springer-Verlag, 2002.

K. Booth and G. Lueker. Testing for the consecutive ones property, interval graphs and graph planarity using pq-tree algorithms. Journal of Computer and System Sciences, 13(1):335-379, 1976.

G. Di Battista and R. Tamassia. On-line planarity testing. SIAM Journal on Computing, 25(5):956-997, 1996.

I. Cederbaum, S. Even and A. Lempel. An algorithm for planarity testing of graphs. In Theory of Graphs, International Symposium, Rome, pages 215--232, 1967.

E. Dahlhaus. Linear time algorithm to recognize clustered graphs and its parallelization (extended abstract). In C.L. Lucchesi, editor, LATIN '98, 3rd Latin American symposium in theoretical informatics, Campinas, Brazil, April 20-24, 1998., volume 1380 of Lecture Notes in Computer Science, pages 239-248, 1998.

P. Eades. Q.-W. Feng, and H. Nagamochi. Drawing clustered graphs on an orthogonal grid. Journal of Graph Algorithms and Applications. 3:3-29, 2000.

Q.-W. Feng, R.-F. Cohen, and P. Eades. Planarity for clustered graphs. In P. Spirakis, editor, Algorithms - ESA '95, Third Annual European Symposium, volume 979 of Lecture Notes in Compuetr Science, pages 213-226. Springer-Verlag, 1995.

C. Gutwenger, M. Jünger, S. Leipert, P. Mutzel, M. Percan, and R. Weiskircher. Subgraph induced planar connectivity augmentation. Technical report, Institut für Informatik, Universität zu Köln, 2002. zaik2002-435.

C. Gutwenger and P. Mutzel. A linear time implementation of SPQR-trees. In J. Marks, editor, Graph Drawing (Proc. 2000), volume 1984 of Lecture Notes in Computer Science, pages 77-90. Springer-Verlag, 2001.