Advances in CPlanarity Testing of Clustered Graphs (Extended Abstract)
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 (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. 220336.
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 'à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 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 c planarity testing.
Download: 
Postscript
 Preprinted Version
Download (357Kb)  Preview 

Download: 
PDF
 Preprinted Version
Download (236Kb)  Preview 
Export as:  
Editorial actions:  View Item (Login required) 
Item Type:  Proceedings article 

Citations:  No citation data. 
Uncontrolled Keywords:  cplanarity clustered graphs cluster 
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Related URLs: 
ZAIK Number:  zaik2002436 

Depositing User:  Prof. Dr. Michael Jünger 
Date Deposited:  03 Apr 2003 00:00 
Last Modified:  12 Jan 2012 12:18 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/436 