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 μ 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 automaticgraph 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 nonconnected 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.
Partially supported by the Future and Emerging Technologies programme of the EU under contract number IST-1999-14186 (ALCOM-FT).