Morphing tree drawings in a small 3D grid

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.