License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.40
URN: urn:nbn:de:0030-drops-121984
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12198/
Go to the corresponding LIPIcs Volume Portal

Erickson, Jeff ; Lin, Patrick

A Toroidal Maxwell-Cremona-Delaunay Correspondence

pdf-format:
LIPIcs-SoCG-2020-40.pdf (0.8 MB)

Abstract

We consider three classes of geodesic embeddings of graphs on Euclidean flat tori:
- A torus graph G is equilibrium if it is possible to place positive weights on the edges, such that the weighted edge vectors incident to each vertex of G sum to zero.
- A torus graph G is reciprocal if there is a geodesic embedding of the dual graph G^* on the same flat torus, where each edge of G is orthogonal to the corresponding dual edge in G^*.
- A torus graph G is coherent if it is possible to assign weights to the vertices, so that G 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 plane graphs (with convex outer faces) are equivalent. Indeed, all three conditions are equivalent to G being the projection of the 1-skeleton of the lower convex hull of points in ℝ³. 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 on some flat torus.

BibTeX - Entry

@InProceedings{erickson_et_al:LIPIcs:2020:12198,
  author =	{Jeff Erickson and Patrick Lin},
  title =	{{A Toroidal Maxwell-Cremona-Delaunay Correspondence}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{40:1--40:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12198},
  URN =		{urn:nbn:de:0030-drops-121984},
  doi =		{10.4230/LIPIcs.SoCG.2020.40},
  annote =	{Keywords: combinatorial topology, geometric graphs, homology, flat torus, spring embedding, intrinsic Delaunay}
}

Keywords: combinatorial topology, geometric graphs, homology, flat torus, spring embedding, intrinsic Delaunay
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI