Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 15261719
DOI: 10.7155/jgaa.00275 Augmenting the Connectivity of Planar and Geometric Graphs Ignaz Rutter and Alexander Wolff Vol. 16, no. 2, pp. 599628, 2012. Regular paper Abstract In this paper we study connectivity augmentation problems. Given a connected graph G with some desirable property, we want to make G 2vertex connected (or 2edge connected) by adding edges such that the resulting graph keeps the property. The aim is to add as few edges as possible. The property that we consider is planarity, both in an abstract graphtheoretic and in a geometric setting, where vertices correspond to points in the plane and edges to straightline segments. We show that it is NPhard to find a minimumcardinality augmentation that makes a planar graph 2edge connected. For making a planar graph 2vertex connected this was known. We further show that both problems are hard in the geometric setting, even when restricted to trees. The problems remain hard for higher degrees of connectivity. On the other hand we give polynomialtime algorithms for the special case of convex geometric graphs. We also study the following related problem. Given a planar (plane geometric) graph G, two vertices s and t of G, and an integer c, how many edges have to be added to G such that G is still planar (plane geometric) and contains c edge (or vertex) disjoint st paths? For the planar case we give a lineartime algorithm for c=2. For the plane geometric case we give optimal worstcase bounds for c=2; for c=3 we characterize the cases that have a solution.

Submitted: August 2010. Reviewed: August 2012. Revised: August 2012. Accepted: August 2012. Final: August 2012. Published: September 2012. Communicated by Michael Goodrich 
Journal of Graph Algorithms and Applications 