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 条

[1]

Alamdari S, 2013, PROCEEDINGS OF THE TWENTY-FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA 2013), P1656

[2]

Angelini Patrizio, 2013, Graph Drawing. 21st International Symposium, GD 2013. Revised Selected Papers: LNCS 8242, P49, DOI 10.1007/978-3-319-03841-4_5

[3]

Angelini P., 2014, ABS14024364 CORR

[4]

[Anonymous], 1984, PROGR GRAPH THEORY

[5]

Barrera-Cruz F., 2013, MEX C DISCR MATH COM

[6]

Cairns S., 1944, Am. Math. Monthly, V51, P247, DOI [10.1080/00029890.1944.11999082, DOI 10.1080/00029890.1944.11999082]

[7]

Chiba Norishige., 1984, Progress in Graph Theory, P153

[8]

Erten C, 2004, LECT NOTES COMPUT SC, V2912, P320

[9]

Friedrich C., 2002, Journal of Graph Algorithms and Applications, V6, DOI 10.7155/jgaa.00057

[10] Guaranteed intersection-free polygon morphing [J].

Gotsman, C ;

Surazhsky, V .

COMPUTERS & GRAPHICS-UK, 2001, 25 (01) :67-75

← 1 2 →