Morphing and Compatible Triangulations of Planar Graph Drawings
To morph a planar graph drawing is to move it continuously, preserving planarity. This is useful for animations and also for constructing 3-dimensional objects from 2-dimensional slices, where time becomes the third dimension.
I will survey results on planar graph morphing when the initial and final graph drawings are given.
I will also discuss some new work on morphing an initial planar graph drawing to become convex, which involves a new application of Tutte’s graph drawing algorithm.
For many algorithms on planar graphs, a first step is to triangulate the graph. For morphing between two given planar graph drawings, a first step is to find “compatible triangulations” of the two drawings, which necessitates adding new Steiner points, possibly a quadratic number. I will survey work on compatible triangulations, including a new result about hardness of minimizing the number of Steiner points. For the case of morphing, I will describe a way to avoid the quadratic blow-up.