Given two n-vertex plane graphs G1 and G2 embedded in the n x 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 x 5n grid) and O(n2) 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.

School of Computer Science

Abellanas, M. (Manuel), Bose, P, García, A. (Alfredo), Hurtado, F. (Ferran), Ramos, P. (Pedro), Rivera-Campo, E. (Eduardo), & Tejel, J. (Javier). (2004). On local transformations in plane geometric graphs embedded on small grids (extended abstract).