On Local Transformations in Plane Geometric Graphs Embedded on Small Grids (Extended Abstract)
Manju Manuel, Prosenjit K. Bose, Annicchiarico Alfredo, Florence de Ferran, P Pedro, E Eduardo, José Javier · 2004
Given two n-vertex plane graphs G1 and G2 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(n 2 ) edge moves, we can transform G1 into G2. In the case of n-vertex trees, we can perform the transformation with O(n) point and edge moves, and show this is optimal. We also study the equivalent problems in the labelled setting.