Given a set @math of @math points in the plane, we solve the problems of constructing a geometric planar graph spanning @math 1) of minimum degree 2, and 2) which is 2-edge connected, respectively, and has max edge length bounded by a factor of 2 times the optimal; we also show that the factor 2 is best possible given appropriate connectivity conditions on the set @math , respectively. First, we construct in @math time a geometric planar graph of minimum degree 2 and max edge length bounded by 2 times the optimal. This is then used to construct in @math time a 2-edge connected geometric planar graph spanning @math with max edge length bounded by @math times the optimal, assuming that the set @math forms a connected Unit Disk Graph. Second, we prove that 2 times the optimal is always sufficient if the set of points forms a 2 edge connected Unit Disk Graph and give an algorithm that runs in @math time. We also show that for @math , there exists a set @math of @math points in the plane such that even though the Unit Disk Graph spanning @math is @math -vertex connected, there is no 2-edge connected geometric planar graph spanning @math even if the length of its edges is allowed to be up to 17 16.
@cite_0 give a polynomial algorithm which augments any geometric planar graph to 2-vertex connected or 2-edge connected geometric planar graph, respectively, but no bounds are given on the length of the augmented edges. T 'oth @cite_6 improves the bound on the number of necessary edges in such augmentations, and Rutter and Wolff @cite_7 prove that it is NP-hard to determine the minimum number of edges that have to be added in such augmentations.
@cite_0 @cite_7 @cite_6
2098823334 1571925205 1981160608 2022451101
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 nd 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. It is shown that if a planar straight line graph (Pslg) with n vertices in general position in the plane can be augmented to a 3-edge-connected Pslg, then 2n ? 2 new edges are enough for the augmentation. This bound is tight: there are Pslgs with n ? 4 vertices such that any augmentation to a 3-edge-connected Pslg requires 2n ? 2 new edges. We characterize the planar straight line graphs (Pslgs) that can be augmented to 3-connected and 3-edge-connected Pslgs, respectively. We show that if a Pslg with n vertices can be augmented to a 3-edge-connected Pslg, then at most 2n−2 new edges are always sufficient and sometimes necessary for the augmentation. If the input Pslg is, in addition, already 2-edge-connected, then n−2 new edges are always sufficient and sometimes necessary for the augmentation to a 3-edge-connected Pslg. It is shown that every connected planar straight line graph with n>=3 vertices has an embedding preserving augmentation to a 2-edge connected planar straight line graph with at most @?(2n-2) 3@? new edges. It is also shown that every planar straight line tree with n>=3 vertices has an embedding preserving augmentation to a 2-edge connected planar topological graph with at most @?n 2@? new edges. These bounds are the best possible. However, for every n>=3, there are planar straight line trees with n vertices that do not have an embedding preserving augmentation to a 2-edge connected planar straight line graph with fewer than 1733n-O(1) new edges.