Gutwenger, Carsten and Jünger, Michael and Leipert, Sebastian and Mutzel, Petra and Percan, Merijam and Weiskircher, René
(2002)
Advances in CPlanarity Testing of Clustered Graphs.
[Preprint]
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''. Cplanarity is a natural extension of graph planarity for clustered graphs, and plays an important role in automatic graph drawing. The complexity status of cplanarity testing is unknown. It has been shown that cplanarity can be tested in linear time for cconnected graphs, i.e., graphs in which the cluster induced subgraphs are connected.
In this paper, we provide a polynomial time algorithm for cplanarity testing for "almost" cconnected clustered graphs, i.e., graphs for which all cvertices corresponding to the noncconnected clusters lie on the same path in T starting at the root of T, or graphs in which for each nonconnected cluster its supercluster 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 cplanarity testing.
Available Versions of this Item

Advances in CPlanarity Testing of Clustered Graphs. (deposited 12 Apr 2005)
[Currently Displayed]
Actions (login required)

View Item 