ALCOMFT-TR-02-126

Carsten Gutwenger, Michael Jünger, Sebastian Leipert, Petra Mutzel, Merijam Percan and René Weiskircher
Subgraph Induced Planar Connectivity Augmentation
Cologne. Work package 4. May 2002.

Abstract: Given a planar graph G=(V,E) and a vertex set W\subseteq 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,E\cup 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.

Postscript file: ALCOMFT-TR-02-126.ps.gz (145 kb).