Special issue on Selected papers from the Twenty-sixth International Symposium on Graph Drawing and Network Visualization, GD 2018
Pole Dancing: 3D Morphs for Tree Drawings
Vol. 23, no. 3, pp. 579-602, 2019. Regular paper.
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.
Submitted: November 2018.
Reviewed: January 2019.
Revised: May 2019.
Accepted: June 2019.
Final: July 2019.
Published: September 2019.
Communicated by Therese Biedl and Andreas Kerren
article (PDF)