Morphing Schnyder drawings of planar triangulations (Q1739203): Difference between revisions

It is a known fact that, given a triangulation on $n$ vertices and two straight-line planar drawings of it, $\Gamma$ and $\Gamma^\prime$, that have the same unbounded face, it is possible to morph from $\Gamma$ to $\Gamma^\prime$ while preserving straight-line planarity. Various morphing algorithms are already known. In [SIAM J. Comput. 46, No. 2, 824--852 (2017; Zbl 1370.68224)] the authors give a morph that consists of $O(n)$ linear morphs that moves each of the $n$ vertices in a straight line at uniform speed. However, the resulting grid size of the intermediate drawings is not bounded and the morphs are not good for visualization purposes. \par The algorithm of this paper uses Schnyder embeddings to morph in $O(n^2)$ linear morphing steps while all $O(n^2)$ intermediate drawings are on a $6n\times 6n$ grid for a significant class of drawings of triangulations, namely the class of weighted Schnyder drawings. Furthermore, the morphs are visually attractive. \par A Schnyder wood is a special type of partition (colouring) and orientation of the edges of a planar triangulation into three rooted directed trees. Weighted Schnyder drawings are obtained from a Schnyder wood together with an assignment of positive weights to the interior faces. The method in the paper involves implementing the basic ``flip'' operations of Schnyder woods as linear morphs.