On local transformations in plane geometric graphs embedded on small grids

详细信息	查看全文 | 推荐本文 |

• 作者：Manuel Abellanas ; Prosenjit Bose ; Alfredo Garcí ; a ; Ferran Hurtado ; Pedro Ramos ; Eduardo Rivera-Campo ; Javier Tejel
• 关键词：Graph transformation ; Flip ; Local transformation ; Grid drawing ; Planar embedding ; Graph drawing
• 刊名：Computational Geometry
• 出版年：2008
• 期刊代码：18_09257721
• 类别：cp
• 出版时间：February 2008
• 卷：39
• 期：2
• 页码：65-77
• 文件大小：331 K

摘要

Given two n-vertex plane graphs G₁=(V₁,E₁) and G₂=(V₂,E₂) with |E₁|=|E₂| 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²) edge moves, we can transform the embedding of G₁ into the embedding of G₂. 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.