C. Gutwenger, M. Jünger, S. Leipert, P. Mutzel, M. Percan, R. Weiskircher
Published in:
„Graph-Theoretic Concepts in Computer Science, 29th International Workshop, WG 2003“ (edited by Hans L. Bodlaender), series „Lecture Notes in Computer Science“, volume LNCS, number 2880, 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.