š„Submitted to the 29th International Symposium on Graph Drawing and Network Visualization (2021)

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 spring-embedding theorem.First, we give a much simpler algorithm to construct piecewise-linear morphs between planar straight-line graphs. Specifically, given isomorphic straight-line drawings Īā and Īā of the same 3-connected planar graph, with the same convex outer face, we construct a morph from Īā to Īā that consists of O(

n) unidirectional morphing steps, in O(n^{1+Ļ/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 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.

Publications - Jeff Erickson (jeffe@illinois.edu) 10 Jun 2021