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.
2022
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].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/398119
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact