Can I read How to Morph Graphs on the Torus on EtoBox?

How to Morph Graphs on the Torus by Erin Wolf Chambers; Jeff Erickson; Patrick Lin; Salman Parsa is a book available to read on EtoBox.

What is How to Morph Graphs on the Torus about?

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.

Author

Erin Wolf Chambers; Jeff Erickson; Patrick Lin; Salman Parsa

Published

2021

Language

EN