Gutwenger, Carsten
[Author];
Leipert, Sebastian
[Author];
Mutzel, Petra
[Author];
Percan, Merijam
[Author];
Weiskircher, René
[Author];
Jünger, Michael
[Author]
Advances in C-Planarity Testing of Clustered Graphs (Extended Abstract)
You can manage bookmarks using lists, please log in to your user account for this.
Media type:
E-Article;
Text
Title:
Advances in C-Planarity Testing of Clustered Graphs (Extended Abstract)
Contributor:
Gutwenger, Carsten
[Author];
Leipert, Sebastian
[Author];
Mutzel, Petra
[Author];
Percan, Merijam
[Author];
Weiskircher, René
[Author];
Jünger, Michael
[Author]
Published:
Springer, 2002
Language:
English;
German
Origination:
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
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 'àlmost'' 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.