TY - JOUR
T1 - A TOROIDAL MAXWELL–CREMONA–DELAUNAY CORRESPONDENCE∗
AU - Erickson, Jeff
AU - Lin, Patrick
N1 - Funding Information:
∗Portions of this work were supported by NSF grant CCF-1408763. A preliminary version of this paper was presented at the 36th International Symposium on Computational Geometry [34]. †University of Illinois, Urbana-Champaign, https://jeffe.cs.illinois.edu/ ‡University of Illinois, Urbana-Champaign, https://patrickl.in/
Publisher Copyright:
© 2021, Carleton University. All rights reserved.
PY - 2021
Y1 - 2021
N2 - We consider three classes of geodesic embeddings of graphs on Euclidean flat tori: • A toroidal graph embedding Γ is positive equilibrium if it is possible to place positive weights on the edges, such that the weighted edge vectors incident to each vertex of Γ sum to zero. • A toroidal graph embedding Γ is reciprocal if there is a geodesic embedding Γ∗ of its dual on the same flat torus, where each edge of Γ is orthogonal to the corresponding dual edge in Γ∗. • A toroidal graph embedding Γ is coherent if it is possible to assign weights to the vertices, so that Γ is the (intrinsic) weighted Delaunay graph of its vertices. The classical Maxwell–Cremona correspondence and the well-known correspondence between convex hulls and weighted Delaunay triangulations imply that the analogous concepts for planar graph embeddings (with convex outer faces) are equivalent. Indeed, all three conditions are equivalent to Γ being the projection of the 1-skeleton of the lower convex hull of points in ℝ3. However, this three-way equivalence does not extend directly to geodesic graph embeddings on flat tori. On any flat torus, reciprocal and coherent embeddings are equivalent, and every reciprocal embedding is in positive equilibrium, but not every positive equilibrium embedding is reciprocal. We establish a weaker correspondence: Every positive equilibrium embedding on any flat torus is affinely equivalent to a reciprocal/coherent embedding on some flat torus.
AB - We consider three classes of geodesic embeddings of graphs on Euclidean flat tori: • A toroidal graph embedding Γ is positive equilibrium if it is possible to place positive weights on the edges, such that the weighted edge vectors incident to each vertex of Γ sum to zero. • A toroidal graph embedding Γ is reciprocal if there is a geodesic embedding Γ∗ of its dual on the same flat torus, where each edge of Γ is orthogonal to the corresponding dual edge in Γ∗. • A toroidal graph embedding Γ is coherent if it is possible to assign weights to the vertices, so that Γ is the (intrinsic) weighted Delaunay graph of its vertices. The classical Maxwell–Cremona correspondence and the well-known correspondence between convex hulls and weighted Delaunay triangulations imply that the analogous concepts for planar graph embeddings (with convex outer faces) are equivalent. Indeed, all three conditions are equivalent to Γ being the projection of the 1-skeleton of the lower convex hull of points in ℝ3. However, this three-way equivalence does not extend directly to geodesic graph embeddings on flat tori. On any flat torus, reciprocal and coherent embeddings are equivalent, and every reciprocal embedding is in positive equilibrium, but not every positive equilibrium embedding is reciprocal. We establish a weaker correspondence: Every positive equilibrium embedding on any flat torus is affinely equivalent to a reciprocal/coherent embedding on some flat torus.
UR - http://www.scopus.com/inward/record.url?scp=85133594693&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85133594693&partnerID=8YFLogxK
U2 - 10.20382/jocg.v12i2a4
DO - 10.20382/jocg.v12i2a4
M3 - Article
AN - SCOPUS:85133594693
SN - 1920-180X
VL - 12
SP - 55
EP - 85
JO - Journal of Computational Geometry
JF - Journal of Computational Geometry
IS - 2
ER -