Home  Issues  About JGAA  Instructions for Authors 
Special Issue on Selected Papers from the 16th International Conference and Workshops on Algorithms and Computation, WALCOM 2022
DOI: 10.7155/jgaa.00623
Morphing tree drawings in a small 3D grid
Vol. 27, no. 4, pp. 241279, 2023. Regular paper.
Abstract We study crossingfree grid morphs for planar drawings of trees using the third dimension. A morph
consists of morphing steps,
where vertices of the tree move simultaneously along straightline trajectories at constant speeds. The aim is to find a morph between two given drawings of the same tree that has a small number of steps and is crossingfree, i.e. no two vertices overlap or no two edges of the tree intersect except in their common endpoints at any moment during the morph. It is already known, that there exists a crossingfree morph between two drawings of an $n$vertex planar graph $G$ with $\mathcal{O}(n)$ morphing steps, and that using the third dimension the number of steps can be reduced to $\mathcal{O}(\log n)$ for an $n$vertex tree. However, these morphs do not bound one practical parameter, the resolution. Can the number of steps still be reduced substantially by using the third dimension with an additional restriction of keeping the resolution bounded throughout the morph? We answer this question in affirmative by presenting a $3D$ noncrossing morph between two planar grid drawings of an $n$vertex tree in $\mathcal{O}(\sqrt{n} \log n)$ morphing steps such that each intermediate drawing is a grid drawing, i.e., vertices of the tree are mapped to the nodes of a $3D$ grid of polynomial volume.
This work is licensed under the terms of the CCBY license.

Submitted: July 2022.
Reviewed: November 2022.
Revised: January 2023.
Reviewed: March 2023.
Revised: March 2023.
Accepted: April 2023.
Final: May 2023.
Published: May 2023.

Journal Supporters
