Morphing planar triangulations

Series: 
Combinatorics Seminar
Friday, October 2, 2015 - 15:00
1 hour (actually 50 minutes)
Location: 
Skiles 005
,  
Georgia Tech
,  
Organizer: 
A morph between two drawings of the same graph can be thought of as a continuous deformation between the two given drawings. In this talk we consider the algorithmic problem of morphing between any two planar drawings of a planar triangulation while preserving planarity during the morph. We outline two different solutions to the morphing problem. The first solution gives a strengthening of the result of Alamdari et al. where each step is a unidirectional morph. The second morphing algorithm finds a planar morph consisting of O(n²) steps between any two Schnyder drawings while remaining in an O(n)×O(n) grid, here n is the number of vertices of the graph. However, there are drawings of planar triangulations which are not Schnyder drawings, and for these drawings we show that a unidirectional morph consisting of O(n) steps that ends at a Schnyder drawing can be found. (Joint work with Penny Haxell and Anna Lubiw)