TY - GEN

T1 - Augmenting the connectivity of planar and geometric graphs

AU - Rutter, I.

AU - Wolff, A.

PY - 2008

Y1 - 2008

N2 - In this paper we study some connectivity augmentation problems. We want to make planar graphs 2-vertex (or 2-edge) connected by adding edges such that the resulting graphs remain planar. We show that it is NP-hard to find a minimum-cardinality augmentation that makes a planar graph 2-edge connected. This was known for 2-vertex connectivity. We further show that both problems are hard in a geometric setting, even when restricted to trees. For the special case of convex geometric graphs we give efficient algorithms.
We also study the following related problem. Given a plane geometric graph G, two vertices s and t of G, and an integer k, how many edges have to be added to G such that G contains k edge- (or vertex-) disjoint s-t paths? For k=2 we give optimal worst-case bounds; for k=3 we characterize all cases that have a solution.

AB - In this paper we study some connectivity augmentation problems. We want to make planar graphs 2-vertex (or 2-edge) connected by adding edges such that the resulting graphs remain planar. We show that it is NP-hard to find a minimum-cardinality augmentation that makes a planar graph 2-edge connected. This was known for 2-vertex connectivity. We further show that both problems are hard in a geometric setting, even when restricted to trees. For the special case of convex geometric graphs we give efficient algorithms.
We also study the following related problem. Given a plane geometric graph G, two vertices s and t of G, and an integer k, how many edges have to be added to G such that G contains k edge- (or vertex-) disjoint s-t paths? For k=2 we give optimal worst-case bounds; for k=3 we characterize all cases that have a solution.

U2 - 10.1016/j.endm.2008.06.009

DO - 10.1016/j.endm.2008.06.009

M3 - Conference contribution

T3 - Electronic Notes in Discrete Mathematics

SP - 53

EP - 56

BT - Proceedings International Conference on Topological and Geometric Graph Theory (TGGT'08, Paris, France, May 19-23, 2008)

A2 - Ossona de Mendez, P.

A2 - Pocchiola, M.

A2 - Poulalhon, D.

A2 - Ramírez Alfonsín, J.L.

A2 - Schaeffer, G.

ER -