Given a planar graph G= (V, E) and a vertex set W is contained inV, 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∪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 a minimum cardinality augmenting edge set.
展开▼
