Subgraph Induced Connectivity Augmentation

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

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.


Actions:
Download: [img] Postscript - Preprinted Version
Download (409Kb) | Preview
Download: [img] PDF - Preprinted Version
Download (259Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2002-435
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 07 Dec 2005 00:00
Last Modified: 12 Jan 2012 11:28
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/435