Motivated by applications to graph morphing, we consider the following : We are given a labelled @math -vertex planar graph, @math , that has @math connected components, and @math isomorphic planar straight-line drawings, @math , of @math . We wish to augment @math by adding vertices and edges to make it connected in such a way that these vertices and edges can be added to @math as points and straight-line segments, respectively, to obtain @math planar straight-line drawings isomorphic to the augmentation of @math . We show that adding @math edges and vertices to @math is always sufficient and sometimes necessary to achieve this goal. The upper bound holds for all @math and @math and is achievable by an algorithm whose running time is @math for @math and whose running time is @math for general values of @math . The lower bound holds for all @math and @math .
Finally, several papers have dealt with the problem of increasing the connectivity of a (single) geometric planar graph while adding few vertices and edges. Abellenas al @cite_1 consider the problem of adding edges to a planar drawing in order to make it 2-edge connected and showed that @math edge are sometimes necessary and @math edges are always sufficient. T 'oth @cite_8 later obtained the tight upper-bound of @math for the same problem. Rutter and Wolff @cite_17 show that finding the minimum number of edges required to achieve 2-edge connectivity is NP-hard.
@cite_1 @cite_17 @cite_8
2063013286 2011374244 2022451101
Let G be a connected plane geometric graph with n vertices. In this paper, we study bounds on the number of edges required to be added to G to obtain 2-vertex or 2-edge connected plane geometric graphs. In particular, we show that for G to become 2-edge connected, 2n3 additional edges are required in some cases and that 6n7 additional edges are always sufficient. For the special case of plane geometric trees, these bounds decrease to n2 and 2n3, respectively. 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.