Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00275
Augmenting the Connectivity of Planar and Geometric Graphs
Vol. 16, no. 2, pp. 599-628, 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 2-vertex connected (or 2-edge 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 graph-theoretic and in a
geometric setting, where vertices correspond to points in the plane
and edges to straight-line segments.
We show that it is NP-hard to find a minimum-cardinality
augmentation that makes a planar graph 2-edge connected. For making
a planar graph 2-vertex 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 polynomial-time
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 s-t paths? For the planar case we give a linear-time
algorithm for c=2. For the plane geometric case we
give optimal worst-case 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 T. Goodrich
|
Journal Supporters
|