Morphing Planar Graph Drawings Optimally

被引：0

作者：

Angelini, Patrizio ^{[1
]}

Da Lozzo, Giordano ^{[1
]}

Di Battista, Giuseppe ^{[1
]}

Frati, Fabrizio ^{[2
]}

Patrignani, Maurizio ^{[1
]}

Roselli, Vincenzo ^{[1
]}

机构：

[1] Roma Tre Univ, Dipartimento Ingn, Rome, Italy

[2] Univ Sydney, Sch Informat Technol, Sydney, NSW 2006, Australia

来源：

AUTOMATA, LANGUAGES, AND PROGRAMMING (ICALP 2014), PT I | 2014年 / 8572卷

关键词：

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We provide an algorithm for computing a planar morph between any two planar straight-line drawings of any n-vertex plane graph in O(n) morphing steps, thus improving upon the previously best known O(n(2)) upper bound. Furthermore, we prove that our algorithm is optimal, that is, we show that there exist two planar straight-line drawings Gamma(s) and Gamma(t) of an n-vertex plane graph G such that any planar morph between Gamma(s) and Gamma(t) requires Omega(n) morphing steps.

引用

页码：126 / 137

页数：12

共 15 条

[11]

Grunbaum B., 1981, GEOMETRY PLANAR GRAP

[12] Convex drawings of hierarchical planar graphs and clustered planar graphs [J].