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 .
To the best of our knowledge, there is little work on compatible connectivity-augmentation of planar graphs, though there is work on isomorphic triangulations of polygons. Refer to Figure . In this setting, the graph @math is a cycle and one has two non-crossing drawings, @math and @math , of @math . The goal is to augment @math (and the two drawings @math and @math ) so that @math becomes a near-triangulation, and @math and @math become (geometric) triangulations of the interiors of the polygons whose boundaries are @math and @math . Aronov al @cite_0 showed that this can always be accomplished with the addition of @math vertices and that @math vertices are sometimes necessary. Kranakis and Urrutia @cite_10 showed that this result can be made sensitive to the number of reflex vertices of @math and @math , so that the number of triangles required is @math where @math and @math are the number of reflex vertices of @math and @math , respectively.
@cite_0 @cite_10
2058517112 2100595965
Abstract It is well known that, given two simple n-sided polygons, it may not be possible to triangulate the two polygons in a compatible fashion, if one's choice of triangulation vertices is restricted to polygon corners. Is it always possible to produce compatible triangulations if additional vertices inside the polygon are allowed? We give a positive answer and construct a pair of such triangulations with O(n2) new triangulation vertices. Moreover, we show that there exists a ‘universal’ way of triangulating an n-sided polygon with O(n2) extra triangulation vertices. Finally, we also show that creating compatible triangulations requires a quadratic number of extra vertices in the worst case. Assume that an isomorphism between two n-vertex simple polygons, P,Q (with k,l reflex vertices, respectively) is given. We present two algorithms for constructing isomorphic (i.e. adjacency preserving) triangulations of P and Q, respectively. The first algorithm computes isomorphic triangulations of P and Q by introducing at most O((k+l)2) Steiner points and has running time O(n+(k+l)2). The second algorithm computes isomorphic traingulations of P and Q by introducing at most O(kl) Steiner points and has running time O(n+kllog n). The number of Steiner points introduced by the second algorithm is also worst-case optimal. Unlike the O(n2) algorithm of Aronov, Seidel and Souvaine1 our algorithms are sensitive to the number of reflex vertices of the polygons. In particular, our algorithms have linear running time when for the first algorithm, and kl≤n log n for the second algorithm.