Pole Dancing: 3D Morphs for Tree Drawings

Authors

Elena Arseneva
Prosenjit Bose
Pilar Cano
Anthony D'Angelo
Vida Dujmović
Fabrizio Frati
Stefan Langerman
Alessandra Tappini

DOI:

Keywords:

graph drawing, morph, crossing-free 3D drawing, straight-line drawing, tree drawing

Abstract

We study the question whether a crossing-free 3D morph between two straight-line drawings of an $n$-vertex tree $T$ can be constructed consisting of a small number of linear morphing steps. We look both at the case in which the two given drawings are two-dimensional and at the one in which they are three-dimensional. In the former setting we prove that a crossing-free 3D morph always exists with $O({rpw}(T))\subseteq O(\log n)$ steps, where ${rpw}(T)$ is the rooted pathwidth or Strahler number of $T$, while for the latter setting $\Theta(n)$ steps are always sufficient and sometimes necessary.

Downloads

Download data is not yet available.

Downloads

article (PDF)

Published

2019-09-01

How to Cite

Arseneva, E., Bose, P., Cano, P., D'Angelo, A., Dujmović, V., Frati, F., … Tappini, A. (2019). Pole Dancing: 3D Morphs for Tree Drawings.Journal of Graph Algorithms and Applications,23(3), 579–602. https://doi.org/10.7155/jgaa.00503