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
2100595965 2024465063 2065527713 2098823334
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. This paper addresses the problem of representing the connectivity information of geometric objects, using as little memory as possible. As opposed to raw compression issues, the focus here is on designing data structures that preserve the possibility of answering incidence queries in constant time. We propose, in particular, the first optimal representations for 3-connected planar graphs and triangulations, which are the most standard classes of graphs underlying meshes with spherical topology. Optimal means that these representations asymptotically match the respective entropy of the two classes, namely 2 bits per edge for 3-connected planar graphs, and 1.62 bits per triangle, or equivalently 3.24 bits per vertex for triangulations. These representations support adjacency queries between vertices and faces in constant time. We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. Specifically, a graph with property @math is called a @math -graph . If @math satisfies certain properties, then an n-node m-edge @math -graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2) X has at most @math bits for any continuous superadditive function @math so that there are at most @math distinct @math -node @math -graphs. The methodology is applicable to general classes of graphs; this paper focuses on planar graphs. Examples of such @math include all conjunctions over the following groups of properties: (1) G is a planar graph or a plane graph; (2) @math is directed or undirected; (3) @math is triangulated, triconnected, biconnected, merely connected, or not required to be connected; (4) the nodes of G are labeled with labels from @math for @math ; (5) the edges of G are labeled with labels from @math for @math ; and (6) each node (respectively, edge) of G has at most @math self-loops (respectively, @math multiple edges). Moreover, @math and @math are not required to be O(1) for the cases of @math being a plane triangulation. These examples are novel applications of small cycle separators of planar graphs and are the only nontrivial classes of graphs, other than rooted trees, with known polynomial-time information-theoretically optimal coding schemes. 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.