ALCOMFT-TR-02-127

Carsten Gutwenger, Michael Jünger, Sebastian Leipert, Petra Mutzel, Merijam Percan and René Weiskircher
Advances in C-Planarity Testing of Clustered Graphs
Cologne. Work package 4. May 2002.

Abstract: 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.

Postscript file: ALCOMFT-TR-02-127.ps.gz (137 kb).