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.


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.

Download: [img] Postscript - Preprinted Version
Download (419kB) | Preview
Download: [img] PDF - Preprinted Version
Download (265kB) | Preview
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