Morphing tree drawings using a small 3D grid

Elena Arseneva, Rahul Gangopadhyay, Aleksandra Istomina

Morphing between two planar drawings using an extra dimension is relatively new area of research. Also, the morphs with polynomially-bounded resolution has gained a lot of attention in recent years. Recent results use linear number of morphing steps to morph between two planar straight-line grid drawings of an $n$-vertex tree while maintaining the resolution. In this paper, we bring together both the paradigms to develop an algorithm that morphs between two planar straight-line grid drawings of an $n$-vertex tree $T$ in sublinear number of morphing steps such that each intermediate morphing step produces a $3D$ straight-line crossing free grid drawing of $T$ while maintaining the resolution. To be precise, we first devise an algorithm that takes $\mathcal{O}(n)$ morphing steps but uses a grid of small volume. We then use this algorithm to devise a better algorithm that takes $\mathcal{O}(\sqrt{n} \log n)$ morphing steps. We also ensure that each intermediate drawing lies in a $3D$ grid of polynomially-bounded volume. To the best of our knowledge, this is the first morphing algorithm that takes sublinear number of morphing steps while maintaining a polynomially-bounded grid size, and thus the resolution.

Knowledge Graph



Sign up or login to leave a comment