Advances in C-Planarity Testing of Clustered Graphs (Extended Abstract)
Gutwenger, Carsten and Jünger, Michael and Leipert, Sebastian and Mutzel, Petra and Percan, Merijam and Weiskircher, René
Advances in C-Planarity Testing of Clustered Graphs (Extended Abstract).
Published In: Graph drawing : 10th international symposium, GD 2002, Irvine, CA, USA, August 26 - 28, 2002 ; revised papers, Lecture Notes in Computer Science. 2528 Springer 2002, pp. 220-336.
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.
|Item Type:||Proceedings article|
|Citations:||No citation data.|
|Uncontrolled Keywords:||c-planarity clustered graphs cluster|
|Divisions:||Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger|
|Depositing User:||Prof. Dr. Michael Jünger|
|Date Deposited:||03 Apr 2003 00:00|
|Last Modified:||12 Jan 2012 12:18|