Home  Issues  About JGAA  Instructions for Authors 
Special issue on Selected papers from the Twentynineth International Symposium on Graph Drawing and Network Visualization, GD 2021
DOI: 10.7155/jgaa.00616
Planar and Toroidal Morphs Made Easier
Vol. 27, no. 2, pp. 95118, 2023. Regular paper.
Abstract We present simpler algorithms for two closely related morphing problems, both based on the barycentric interpolation paradigm introduced by Floater and Gotsman, which is in turn based on Floater’s asymmetric extension of Tutte’s classical springembedding theorem.
First, we give a very simple algorithm to construct piecewiselinear morphs between planar straightline graphs. Our algorithm entirely avoids the classical edgecollapsing strategy dating back to Cairns; instead, in each morphing step, we interpolate the pair of weights associated with a single edge. Specifically, given equivalent straightline drawings $\Gamma_0$ and $\Gamma_1$ of the same 3connected planar graph $G$, with the same convex outer face, we construct a morph from $\Gamma_0$ to $\Gamma_1$ that consists of $O(n)$ unidirectional morphing steps, in $O(n^{1+\omega/2})$ time, where $n$ is the number of vertices and $\omega$ is the matrix multiplication constant.
Second, we describe a natural extension of barycentric interpolation to geodesic graphs on the flat torus. Barycentric interpolation cannot be applied directly in this setting, because the linear systems defining intermediate vertex positions are not necessarily solvable. We describe a simple scaling strategy that circumvents this issue. Computing the appropriate scaling requires $O(n^{\omega/2})$ time, after which we can compute the drawing at any point in the morph in $O(n^{\omega/2})$ time. Our algorithm is considerably simpler than the recent algorithm of Chambers, Erickson, Lin, and Parsa, and produces more natural morphs. Our techniques also yield a simple proof of a conjecture of Connelly, Henderson, Ho, and Starbird for geodesic torus triangulations.
This work is licensed under the terms of the CCBY license.

Submitted: November 2021.
Reviewed: March 2022.
Revised: June 2022.
Accepted: October 2022.
Final: October 2022.
Published: February 2023.

Journal Supporters
