Search

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.

Given two n-vertex plane graphs G1=(V1,E1) and G2=(V2,E2) with |E1|=|E2| embedded in the n×n grid, with straight-line segments as edges, we show that with a sequence of O(n) point moves (all point moves stay within a 5n×5n grid) and O(n2) edge moves, we can transform the embedding of G1 into the embedding of G2. In the case of n-vertex trees, we can perform the transformation with O(n) point and edge moves with all moves staying in the n×n grid. We prove that this is optimal in the worst case as there exist pairs of trees that require Ω(n) point and edge moves. We also study the equivalent problems in the labeled setting.

We consider combinatorial and computational issues that are related to the problem of moving coins from one configuration to another. Coins are defined as non-overlapping discs, and moves are defined as collision free translations, all in the Euclidean plane. We obtain combinatorial bounds on the number of moves that are necessary and/or sufficient to move coins from one configuration to another. We also consider several decision problems related to coin moving, and obtain some results regarding their computational complexity.