Abstract
We study crossing-free grid morphs for planar tree drawings using 3D. A morph consists of morphing steps, where vertices move simultaneously along straight-line trajectories at constant speed. A crossing-free morph is known between two drawings of an $n$-vertex planar graph $G$ with $\mathcal{O}(n)$ morphing steps and sometimes $\Omega(n)$ steps is necessary even when $G$ is a path~[Alamdari et al.\ 2017], while using 3D can reduce the number of steps to $\mathcal{O}(\log n)$ for an $n$-vertex tree [Arseneva et al.\ 2019]. However, these morphs do not bound one practical parameter, the resolution. Recently [Barrera-Cruz et al.\ 2019] a 2D crossing-free morph was devised between two planar drawings of an $n$-vertex tree in $\mathcal{O}(n)$ steps with polynomial resolution, that is, all intermediate drawings are grid drawings on a grid of polynomial size. Can the number of steps in this setting be reduced substantially by using 3D? We answer this question in affirmative and present a 3D non-crossing morph between two planar grid drawings of an $n$-vertex tree in $\mathcal{O}(\sqrt{n} \log n)$ morphing steps. Each intermediate drawing lies in a $3D$ grid of polynomial volume.

This publication has 17 references indexed in Scilit: