In this paper we study planar morphs between planar straight-line grid drawings of trees. A morph consists of a sequence of morphing steps, where in a morphing step vertices move along straight-line trajectories at constant speed. We show how to construct planar morphs that simultaneously achieve a reduced number of morphing steps and a polynomially-bounded resolution. We assume that both the initial and final drawings lie on the grid and we ensure that each morphing step produces a grid drawing; further, we consider both upward drawings of rooted trees and drawings of arbitrary trees.
Barrera-Cruz, F., Borrazzo, M., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., et al. (2022). How to Morph a Tree on a Small Grid. DISCRETE & COMPUTATIONAL GEOMETRY, 67(3), 743-786 [10.1007/s00454-021-00363-8].
How to Morph a Tree on a Small Grid
Borrazzo, Manuel;Da Lozzo, Giordano;Di Battista, Giuseppe;Frati, Fabrizio
;Patrignani, Maurizio;Roselli, Vincenzo
2022-01-01
Abstract
In this paper we study planar morphs between planar straight-line grid drawings of trees. A morph consists of a sequence of morphing steps, where in a morphing step vertices move along straight-line trajectories at constant speed. We show how to construct planar morphs that simultaneously achieve a reduced number of morphing steps and a polynomially-bounded resolution. We assume that both the initial and final drawings lie on the grid and we ensure that each morphing step produces a grid drawing; further, we consider both upward drawings of rooted trees and drawings of arbitrary trees.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
