2004-12-01
On local transformations in plane geometric graphs embedded on small grids (extended abstract)
Publication
Publication
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.
| Additional Metadata | |
|---|---|
| Organisation | 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).
|
|