Morphing tree drawings in a small 3D grid
Preprint
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 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.
Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- The efficient certification of knottedness and Thurston normAdvances in Mathematics, 2021
- Morphing Schnyder Drawings of Planar TriangulationsDiscrete & Computational Geometry, 2018
- Morphing Planar Graph Drawings OptimallyLecture Notes in Computer Science, 2014
- Morphing Planar Graph Drawings Efficiently2013
- The Level Ancestor Problem SimplifiedLecture Notes in Computer Science, 2002
- Guaranteed intersection-free polygon morphingComputers & Graphics, 2001
- How to morph tilings injectivelyJournal of Computational and Applied Mathematics, 1999
- Deformations of plane graphsJournal of Combinatorial Theory, Series B, 1983
- Quantitative analysis of watershed geomorphologyEOS, Transactions American Geophysical Union, 1957
- Deformations of Plane Rectilinear ComplexesThe American Mathematical Monthly, 1944