ðŸ”¥Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms, 2759â€“2778, 2021

arXiv:2007.07927

- Download SODA version:
- ðŸ”¥
Official SODA version from SIAM
- I presented results from this paper in the second half of my invited talk at Graph Drawing 2020

Abstract:

We present the first algorithm to morph graphs on the torus. Given two isotopic essentially 3-connected embeddings of the same graph on the Euclidean flat torus, where the edges in both drawings are geodesics, our algorithm computes a continuous deformation from one drawing to the other, such that all edges are geodesics at all times. Previously even the existence of such a morph was not known. Our algorithm runs in O(n^{1+Ï‰/2}) time, where Ï‰ is the matrix multiplication exponent, and the computed morph consists of O(n) parallel linear morphing steps. Existing techniques for morphing planar straight-line graphs do not immediately generalize to graphs on the torus; in particular, Cairnsâ€˜ original 1944 proof and its more recent improvements rely on the fact that every planar graph contains a vertex of degree at most 5. Our proof relies on a subtle geometric analysis of 6-regular triangulations of the torus. We also make heavy use of a natural extension of Tutteâ€™s spring embedding theorem to torus graphs.

Publications - Jeff Erickson (jeffe@illinois.edu) 28 Jan 2021