BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260911T131231Z
UID:Seminar-dept-1041@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20230425T130000
DTEND:20230425T140000
SUMMARY:School Seminar Series
DESCRIPTION:Dr. Elena Arseneva: Morphing planar drawings of graphs and trees in 2 and 3 dimensions\n\nWe 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.\n\nDeriving any non-trivial lower bound for this problem is widely open.  \n\n\n\nAnother 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.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1041
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR