Universität zu Köln

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.

Preview

PDF zaik2002-436.pdf - Submitted Version Download (242kB) | Preview

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 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
Creators:	Creators Email ORCID ORCID Put Code Gutwenger, Carsten UNSPECIFIED UNSPECIFIED UNSPECIFIED Leipert, Sebastian UNSPECIFIED UNSPECIFIED UNSPECIFIED Mutzel, Petra UNSPECIFIED https://orcid.org/0000-0001-7621-971X UNSPECIFIED Percan, Merijam meripercan@yahoo.de UNSPECIFIED UNSPECIFIED Weiskircher, René UNSPECIFIED UNSPECIFIED UNSPECIFIED Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED
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
URI:	http://kups.ub.uni-koeln.de/id/eprint/54865