Advances in C-Planarity Testing of Clustered Graphs

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. [Preprint]

WarningThere is a more recent version of this item available.

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


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 c 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 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 for "almost" c-connected clustered graphs, i.e., graphs for which all c-vertices 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 are connected. The algorithm uses ideas of the algorithm for subgraph induced planar connectivity augmentation. We regard it as a first step towards general c-planarity testing.

Item Type:Preprint
Classifications:P Styles > P.180 Cluster
G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.540 Planar
ID Code:9
Alternative Locations:

Available Versions of this Item

Repository Staff Only: item control page


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

Booth, K. and Lueker G. (1976) 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

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

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

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

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

Feng, Q.-W. and Cohen, R.-F. and Eades, P. (1995) Planarity for clustered graphs. In: Spirakis, P. (ed.), Algorithms - ESA 95, Third Annual European Symposium, volume 979 of Lecture Notes in Computer Science, pp. 213-226. Springer-Verlag, 1995.

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

Gutwenger, C. and Mutzel, P. (2001) 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.

Hofcroft J. and Tarjan R. E. (1974) Efficient planarity testing. Journal of ACM, 21 (4) 549-568