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 speeds. A crossing-free morph is known between two drawings of an $n$-vertex planar graph $G$ with $\mathcal{O}(n)$ morphing steps and using the third dimension it can be reduced 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. Can the number of steps be reduced substantially by using the third dimension while keeping the resolution bounded throughout the morph? We answer this question in an 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.
翻译:我们用 3D 来研究平面树图的无跨网格变形。 一个变形由变形步骤组成, 顶部以恒定速度同时沿着直线轨迹移动。 在以$mathcal{O}(n) 美元平面图的两幅图中, 以$\mathcal{O}( log n) 来研究平面树图绘制的无跨网格变形。 但是, 这些变形并不约束一个实用参数, 即分辨率。 能否使用第三个维度来大幅减少步骤的数目, 同时又将分辨率绑在全变形中? 我们以肯定的方式回答这个问题, 并在 $\ mathcal{ O} (\ qrt{ n\ log n) 的两幅平面图图图上, 以 $n- mathcal 树为单位, 平面图上以 3D 平面 。