Fun with Toroidal Embeddings (Graph Drawing 2020)
Channel: Jeff Erickson
Date: 2020-09-18

Invited talk at the 28th International Symposium on Graph Drawing and Network Visualization, virtually in Vancouver, on September 17, 2020.

Conference website: https://gd2020.cs.ubc.ca/
Our Maxwell-Cremona paper: https://arxiv.org/abs/2003.10057
Our toroidal morphing paper: https://arxiv.org/abs/2007.07927

Tutte’s classical spring embedding theorem is the foundation of hundreds of algorithms for drawing and manipulating planar graphs. A somewhat less well-known generalization of Tutte’s theorem, first proved by Yves Colin de Verdière in 1990, applies to graphs on more complex surfaces. I will describe two recent applications of this more general theorem to graphs on the Euclidean flat torus. The first is a natural toroidal analogue of the Maxwell-Cremona correspondence, which relates equilibrium stresses, orthogonal dual embeddings, and weighted Delaunay complexes. The second is an efficient algorithm to morph between geodesic torus graphs using a small number of parallel linear morphing steps, matching (and slightly simplifying) recent planar morphing algorithms.

This talk includes joint work with Erin Chambers, Patrick Lin, and Salman Parsa, available at https://arxiv.org/abs/2003.10057 and https://arxiv.org/abs/2007.07927 .