TY - GEN
T1 - Planar and Toroidal Morphs Made Easier
AU - Erickson, Jeff
AU - Lin, Patrick
N1 - Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - 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 spring-embedding theorem. First, we give a very simple algorithm to construct piecewise-linear morphs between planar straight-line graphs. Specifically, given isomorphic straight-line drawings Γ0 and Γ1 of the same 3-connected planar graph G, with the same convex outer face, we construct a morph from Γ0 to Γ1 that consists of O(n) unidirectional morphing steps, in O(n1 + ω / 2) time. Our algorithm entirely avoids the classical edge-collapsing strategy dating back to Cairns; instead, in each morphing step, we interpolate the pair of weights associated with a single edge. 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ω / 2) time, after which we can compute the drawing at any point in the morph in O(nω / 2) time. Our algorithm is considerably simpler than the recent algorithm of Chambers et al. and produces more natural morphs. Our techniques also yield a simple proof of a conjecture of Connelly et al. for geodesic torus triangulations.
AB - 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 spring-embedding theorem. First, we give a very simple algorithm to construct piecewise-linear morphs between planar straight-line graphs. Specifically, given isomorphic straight-line drawings Γ0 and Γ1 of the same 3-connected planar graph G, with the same convex outer face, we construct a morph from Γ0 to Γ1 that consists of O(n) unidirectional morphing steps, in O(n1 + ω / 2) time. Our algorithm entirely avoids the classical edge-collapsing strategy dating back to Cairns; instead, in each morphing step, we interpolate the pair of weights associated with a single edge. 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ω / 2) time, after which we can compute the drawing at any point in the morph in O(nω / 2) time. Our algorithm is considerably simpler than the recent algorithm of Chambers et al. and produces more natural morphs. Our techniques also yield a simple proof of a conjecture of Connelly et al. for geodesic torus triangulations.
UR - http://www.scopus.com/inward/record.url?scp=85122135131&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85122135131&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-92931-2_9
DO - 10.1007/978-3-030-92931-2_9
M3 - Conference contribution
AN - SCOPUS:85122135131
SN - 9783030929305
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 123
EP - 137
BT - Graph Drawing and Network Visualization - 29th International Symposium, GD 2021, Revised Selected Papers
A2 - Purchase, Helen C.
A2 - Rutter, Ignaz
PB - Springer
T2 - 29th International Symposium on Graph Drawing and Network Visualization, GD 2021
Y2 - 14 September 2021 through 17 September 2021
ER -