cite>Proceedings of the 36th International Symposium on Computational Geometry, 40:1–40:17, 2020.

🔥 Full version invited and submitted to the special issue of Journal of Computational Geomettry devoted to the conference.

arXiv:2003.10057.

- Download SOCG version:
- Official SOCG version from LIPIcs
- 🔥 Download submitted journal version:
- I presented results from this paper in the first half of my invited talk at Graph Drawing 2020

Abstract:

We consider three classes of geodesic embeddings of graphs on Euclidean flat tori:The classical Maxwell-Cremona correspondence and the well-known correspondence between convex hulls and weighted Delaunay triangulations imply that the analogous concepts for plane graphs (with convex outer faces) are equivalent. Indeed, all three conditions are equivalent to

- A torus graph
Gisequilibriumif it is possible to place positive weights on the edges, such that the weighted edge vectors incident to each vertex ofGsum to zero.- A torus graph
Gisreciprocalif there is a geodesic embedding of the dual graphG*on the same flat torus, where each edge ofGis orthogonal to the corresponding dual edge inG*.- A torus graph
Giscoherentif it is possible to assign weights to the vertices, so thatGis the (intrinsic) weighted Delaunay graph of its vertices.Gbeing the projection of the 1-skeleton of the lower convex hull of points inR^{3}. However, this three-way equivalence does not extend directly to geodesic graphs on flat tori. On any flat torus, reciprocal and coherent graphs are equivalent, and every reciprocal graph is equilibrium, but not every equilibrium graph is reciprocal. We establish a weaker correspondence: Every equilibrium graph on any flat torus is affinely equivalent to a reciprocal/coherent graph onsomeflat torus.

Publications - Jeff Erickson (jeffe@illinois.edu) 18 Sep 2020