On local transformations in plane geometric graphs embedded on small grids

摘要

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.