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é (2002) 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.

Download: [img] Postscript - Preprinted Version
Download (365kB) | Preview
Download: [img] PDF - Preprinted Version
Download (242kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2002-436
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 03 Apr 2003 00:00
Last Modified: 12 Jan 2012 12:18