Morphing Planar Graph Drawings Optimally

We provide an algorithm for computing a planar morph between any two planar straight-line drawings of any $n$-vertex plane graph in $O(n)$ morphing steps, thus improving upon the previously best known $O(n^2)$ upper bound. Further, we prove that our algorithm is optimal, that is, we show that there exist two planar straight-line drawings ${\mathrm{\Gamma }}_s$ and ${\mathrm{\Gamma }}_t$ of an $n$-vertex plane graph $G$ such that any planar morph between ${\mathrm{\Gamma }}_s$ and ${\mathrm{\Gamma }}_t$ requires $\mathrm{\Omega }(n)$ morphing steps.