Morphing planar graphs

Graphs, Hypergraphs, and Computing

08 April 14:00 - 15:00

Penny Haxell - University of Waterloo

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)
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to