Morphing tree drawings in a small 3D grid

Elena Arseneva ; Rahul Gangopadhyay ; Aleksandra Istomina

Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the 16th International Conference and Workshops on Algorithms and Computation, WALCOM 2022 , Tome 27 (2023) no. 4, pp. 241-279.

Résumé

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.

Détail

DOI : 10.7155/jgaa.00623

Keywords: morphing grid drawings, bounded resolution, 3D morphing