Morphing planar drawings of graphs and trees in 2 and 3 dimensions

25^th April 2023, 13:00 Ashton Lecture Theatre
Dr. Elena Arseneva
University of Lugano, Switzerland

Abstract

We will discuss crossing-free morphs for planar drawings of a graph in 2 dimensions and 3 dimensions. A morph consists of morphing steps, where vertices of the graph move simultaneously along straight-line trajectories at constant speeds. The aim is to find a morph between two given drawings of the same graph that has a small number of steps and is crossing-free, i.e. no two separate elements of the drawing intersect at any moment during the morph. There exists a crossing-free morph between two topologically equivalent drawings of an n-vertex planar graph G with O(n) morphing steps in the plane. We have shown that using the third dimension the number of steps can be reduced to O(log n) for an n-vertex tree. Very recently it was also shown that there exists a morph with O(n^2) steps between two planar drawings of an arbitrary planar graph. Both results involving the third dimension lift the requirement of topological equivalence.
Deriving any non-trivial lower bound for this problem is widely open.

Another tightly related direction is based on the fact that all the above mentioned morphs do not bound one practical parameter, the resolution. In the plane, there is a morph with O(n) steps that transforms one planar drawing of a tree into another, where all the drawings are restricted to lie on a grid of polynomial volume. 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 managed to answer this question in affirmative by presenting a 3D non-crossing morph between two planar grid drawings of an n-vertex tree in O(√n log n) morphing steps such that each intermediate drawing is a grid drawing.