Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Combinatorics Seminar

Penny Haxell

University of Waterloo

Morphing planar graphs

Abstract:

Consider two straightline planar drawings G and H of the same planar triangulation, in which the outer face is fixed. A morph between G and H is a continuous family of drawings of the triangulation, beginning with G and ending with H. We say a morph between G and H is planar if each intermediate drawing is a straightline planar drawing of the triangulation. A morph is called linear if each vertex moves from its initial position in G to its final position in H along a line segment at constant speed. It is easy to see that in general the linear morph from G to H will not be planar. Here we consider the algorithmic problem of finding a planar morph between two given drawings G and H with fixed outer face. For various reasons it is desirable to find morphs in which each vertex trajectory is fairly simple. Thus we focus on the problem of constructing a planar morph consisting of a polynomial number of steps, in which each step is a planar linear morph. (Joint work with Fidel Barrera-Cruz and Anna Lubiw)

Host: Jacques Verstraete

February 25, 2015

2:00 PM

AP&M 6402

****************************