Morphing Schnyder Drawings of Planar Triangulations

Barrera-Cruz, Fidel and Haxell, Penny and Lubiw, Anna (2014) Morphing Schnyder Drawings of Planar Triangulations. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014 , pp. 294-305(Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_25).

Full text not available from this repository.

Abstract

We consider the problem of morphing between two planar drawings of the same triangulated graph, maintaining straight-line planarity. A paper in SODA 2013 gave a morph that consists of O(n 2) steps where each step is a linear morph that moves each of the n vertices in a straight line at uniform speed [1]. However, their method imitates edge contractions so the grid size of the intermediate drawings is not bounded and the morphs are not good for visualization purposes. Using Schnyder embeddings, we are able to morph in O(n 2) linear morphing steps and improve the grid size to O(n)×O(n) for a significant class of drawings of triangulations, namely the class of weighted Schnyder drawings. The morphs are visually attractive. Our method involves implementing the basic “flip” operations of Schnyder woods as linear morphs.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-662-45803-7_25
Classifications: D Aesthetics > D.999 Others
G Algorithms and Complexity > G.999 Others
M Methods > M.200 Animation
M Methods > M.600 Planar
P Styles > P.540 Planar
P Styles > P.720 Straight-line
S Software and Systems > S.120 Visualization
Z Theory > Z.250 Geometry
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 22 May 2015 09:04
Last Modified: 22 May 2015 09:04
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1441

Actions (login required)

View Item View Item