Gutwenger, Carsten, Leipert, Sebastian, Mutzel, Petra ORCID: 0000-0001-7621-971X, Percan, Merijam, Weiskircher, René and Jünger, Michael (2002). Advances in C-Planarity Testing of Clustered Graphs (Extended Abstract). In: Graph drawing : 10th international symposium, GD 2002, Irvine, CA, USA, August 26 - 28, 2002 ; revised papers, pp. 220-336. Springer.

zaik2002-436.pdf - Submitted Version

Download (242kB) | Preview


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: Book Section, Proceedings Item or annotation in a legal commentary
CreatorsEmailORCIDORCID Put Code
Percan, Merijammeripercan@yahoo.deUNSPECIFIEDUNSPECIFIED
URN: urn:nbn:de:hbz:38-548655
Title of Book: Graph drawing : 10th international symposium, GD 2002, Irvine, CA, USA, August 26 - 28, 2002 ; revised papers
Series Name: Lecture Notes in Computer Science
Volume: 2528
Page Range: pp. 220-336
Date: 2002
Publisher: Springer
Language: English
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: Data processing Computer science
Refereed: No


Downloads per month over past year


Actions (login required)

View Item View Item