Universität zu Köln

Gutwenger, Carsten, Leipert, Sebastian, Mutzel, Petra ORCID: 0000-0001-7621-971X, Percan, Merijam, Jünger, Michael and Weiskircher, René (2003). Subgraph Induced Connectivity Augmentation. In: Graph-theoretic concepts in computer science : 29th International Workshop, WG 2003, Elspeet, The Netherlands, June 19 - 21, 2003 ; revised papers, pp. 261-272. Springer.

Preview

PDF zaik2002-435.pdf - Submitted Version Download (265kB) | Preview

Abstract

Given a planar graph G=(V,E) and a vertex set Wsubseteq V , the subgraph induced planar connectivity augmentation problem asks for a minimum cardinality set F of additional edges with end vertices in W such that G'=(V,Ecup F) is planar and the subgraph of G' induced by W is connected. The problem arises in automatic graph drawing in the context of c -planarity testing of clustered graphs. We describe a linear time algorithm based on SPQR-trees that tests if a subgraph induced planar connectivity augmentation exists and, if so, constructs an minimum cardinality augmenting edge set.

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 Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Weiskircher, René UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-548648
Title of Book:	Graph-theoretic concepts in computer science : 29th International Workshop, WG 2003, Elspeet, The Netherlands, June 19 - 21, 2003 ; revised papers
Series Name:	Lecture Notes in Computer Science
Volume:	2880
Page Range:	pp. 261-272
Date:	2003
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/54864