 |
| 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. 241-279, 2023. Regular paper.
Abstract We study crossing-free 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 straight-line 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 crossing-free, 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 crossing-free 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$ non-crossing 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 CC-BY 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 publisher
|
Journal network
|
Journal Supporters
|
