Document Open Access Logo

A Toroidal Maxwell-Cremona-Delaunay Correspondence

Authors Jeff Erickson , Patrick Lin

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.40.pdf
  • Filesize: 0.84 MB
  • 17 pages

Document Identifiers

Author Details

Jeff Erickson
  • University of Illinois, Urbana-Champaign, IL, USA
Patrick Lin
  • University of Illinois, Urbana-Champaign, IL, USA

Funding

Portions of this work were supported by NSF grant CCF-1408763.

Acknowledgements

We thank the anonymous reviewers for their helpful comments and suggestions.

Cite AsGet BibTex

Jeff Erickson and Patrick Lin. A Toroidal Maxwell-Cremona-Delaunay Correspondence. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.40

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graphs and surfaces
Keywords
  • combinatorial topology
  • geometric graphs
  • homology
  • flat torus
  • spring embedding
  • intrinsic Delaunay

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. E. M. Andreev. Convex polyhedra in Lobačevskiĭ space. Mat. Sbornik, 10(3):413-440, 1970. URL: https://doi.org/10.1070/SM1970v010n03ABEH001677.
  2. E. M. Andreev. On convex polyhedra of finite volume in Lobačevskiĭ space. Mat. Sbornik, 12(2):270-259, 1970. URL: https://doi.org/10.1070/SM1970v012n02ABEH000920.
  3. Franz Aurenhammer. A criterion for the affine equivalence of cell complexes in R^d and convex polyhedra in R^d+1. Discrete Comput. Geom., 2(1):49-64, 1987. URL: https://doi.org/10.1007/BF02187870.
  4. Franz Aurenhammer. Power diagrams: Properties, algorithms and applications. SIAM J. Comput., 16(1):78-96, 1987. URL: https://doi.org/10.1137/0216006.
  5. Franz Aurenhammer. Recognising polytopical cell complexes and constructing projection polyhedra. J. Symb. Comput., 3(3):249-255, 1987. URL: https://doi.org/10.1016/S0747-7171(87)80003-2.
  6. Franz Aurenhammer and Hiroshi Imai. Geometric relations among Voronoi diagrams. Geom. Dedicata, 27(1):65-75, 1988. URL: https://doi.org/10.1007/BF00181613.
  7. Alexander I. Bobenko and Boris A. Springborn. A discrete Laplace-Beltrami operator for simplicial surfaces. Discrete Comput. Geom., 38(4):740-756, 2007. URL: https://doi.org/10.1007/s00454-007-9006-1.
  8. Mikhail Bogdanov, Monique Teillaud, and Gert Vegter. Delaunay triangulations on orientable surfaces of low genus. In Sándor Fekete and Anna Lubiw, editors, Proc. 32nd Int. Symp. Comput. Geom., number 51 in Leibniz Int. Proc. Informatics, pages 20:1-20:17, 2016. URL: https://doi.org/10.4230/LIPIcs.SoCG.2016.20.
  9. Ciprian Borcea and Ileana Streinu. Periodic frameworks and flexibility. Proc. Royal Soc. A, 466(2121):2633-2649, 2010. URL: https://doi.org/10.1098/rspa.2009.0676.
  10. Ciprian Borcea and Ileana Streinu. Minimally rigid periodic graphs. Bull. London Math. Soc., 43(6):1093-1103, 2011. URL: https://doi.org/10.1112/blms/bdr044.
  11. Ciprian Borcea and Ileana Streinu. Liftings and stresses for planar periodic frameworks. Discrete Comput. Geom., 53(4):747-782, 2015. URL: https://doi.org/10.1007/s00454-015-9689-7.
  12. Graham R. Brightwell and Edward R. Scheinerman. Representations of planar graphs. SIAM J. Discrete Math., 6(2):214-229, 1993. URL: https://doi.org/10.1137/0406017.
  13. Kevin Q. Brown. Voronoi diagrams from convex hulls. Inform. Process. Lett., 9(5):223-228, 1979. URL: https://doi.org/10.1016/0020-0190(79)90074-7.
  14. Manuel Caroli and Monique Teillaud. Delaunay triangulations of closed Euclidean d-orbifolds. Discrete Comput. Geom., 55(4):827-853, 2016. URL: https://doi.org/10.1007/s00454-016-9782-6.
  15. Marek Chrobak, Michael T. Goodrich, and Roberto Tamassia. Convex drawings of graphs in two and three dimensions (preliminary version). In Proc. 12th Ann. Symp. Comput. Geom., pages 319-328, 1996. URL: https://doi.org/10.1145/237218.237401.
  16. Yves Colin de Verdière. Empilements de cercles: Convergence d’une méthode de point fixe. Forum Math., 1(1):395-402, 1989. URL: https://doi.org/10.1515/form.1989.1.395.
  17. Yves Colin de Verdière. Sur un nouvel invariant des graphes et un critère de planarité. J. Comb. Theory Ser. B, 50(1):11-21, 1990. In French, English translation in [20]. URL: https://doi.org/10.1016/0095-8956(90)90093-F.
  18. Yves Colin de Verdière. Comment rendre géodésique une triangulation d'une surface? L'Enseignment Mathématique, 37:201-212, 1991. URL: https://doi.org/10.5169/seals-58738.
  19. Yves Colin de Verdière. Un principe variationnel pour les empilements de cercles. Invent. Math., 104(1):655-669, 1991. URL: https://doi.org/10.1007/BF01245096.
  20. Yves Colin de Verdière. On a new graph invariant and a criterion for planarity. In Neil Robertson and Paul Seymour, editors, Graph Structure Theory, number 147 in Contemporary Mathematics, pages 137-147. Amer. Math. Soc., 1993. English translation of [17] by Neil Calkin. Google Scholar
  21. Éric Colin de Verdière and Arnaud de Mesmay. Testing graph isotopy on surfaces. Discrete Comput. Geom., 51(1):171-206, 2014. URL: https://doi.org/10.1007/s00454-013-9555-4.
  22. Robert Connelly, Erik D. Demaine, and Günter Rote. Infinitesimally locked self-touching linkages with applications to locked trees. In Jorge Calvo, Kenneth Millett, and Eric Rawdon, editors, Physical Knots: Knotting, Linking, and Folding of Geometric Objects in ℝ³, pages 287-311. Amer. Math. Soc., 2002. Google Scholar
  23. Keenan Crane. Discrete differential geometry: An applied introduction, 2019. URL: http://www.cs.cmu.edu/~kmcrane/Projects/DDG/paper.pdf.
  24. Henry Crapo and Walter Whiteley. Plane self stresses and projected polyhedra I: The basic pattern. Topologie structurale / Structural Topology, 20:55-77, 1993. URL: http://hdl.handle.net/2099/1091.
  25. Luigi Cremona. Le figure reciproche nella statica grafica. Tipografia di Giuseppe Bernardoni, 1872. English translation in [26]. URL: http://www.luigi-cremona.it/download/Scritti_matematici/1872_statica_grafica.pdf.
  26. Luigi Cremona. Graphical Statics. Oxford Univ. Press, 1890. English translation of [25] by Thomas Hudson Beare. URL: https://archive.org/details/graphicalstatic02cremgoog.
  27. Jesús De Loera, Jörg Rambau, and Francisco Santos. Triangulations: Structures for Algorithms and Applications. Number 25 in Algorithms and Computation in Mathematics. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-12971-1.
  28. Olaf Delgado-Friedrichs. Equilibrium placement of periodic graphs and convexity of plane tilings. Discrete Comput. Geom., 33(1):67-81, 2004. URL: https://doi.org/10.1007/s00454-004-1147-x.
  29. Erik D. Demaine and Joseph O'Rourke. Geometric Folding Algorithms: Linkages, Origami, Polyhedra. Cambridge Univ. Press, 2007. Google Scholar
  30. Erik D. Demaine and André Schulz. Embedding stacked polytopes on a polynomial-size grid. Discrete Comput. Geom., 57(4):782-809, 2017. URL: https://doi.org/10.1007/s00454-017-9887-6.
  31. Peter Eades and Patrick Garvan. Drawing stressed planar graphs in three dimensions. In Proc. 2nd Symp. Graph Drawing, number 1027 in Lecture Notes Comput. Sci., pages 212-223, 1995. URL: https://doi.org/10.1007/BFb0021805.
  32. Herbert Edelsbrunner and Raimund Seidel. Voronoi diagrams and arrangements. Discrete Comput. Geom., 1(1):25-44, 1986. URL: https://doi.org/10.1007/BF02187681.
  33. Jeff Erickson and Patrick Lin. A toroidal Maxwell-Cremona-Delaunay correspondence. Prepint, March 2020. Google Scholar
  34. Stefan Felsner and Günter Rote. On Primal-Dual Circle Representations. In Proc. 2nd Symp. Simplicity in Algorithms, volume 69 of OpenAccess Series in Informatics (OASIcs), pages 8:1-8:18. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/OASIcs.SOSA.2019.8.
  35. Daniel Gonçalves and Benjamin Lévêque. Toroidal maps: Schnyder woods, orthogonal surfaces and straight-line representations. Discrete Comput. Geom., 51(1):67-131, 2014. URL: https://doi.org/10.1007/s00454-013-9552-7.
  36. Steven J. Gortler, Craig Gotsman, and Dylan Thurston. Discrete one-forms on meshes and applications to 3D mesh parameterization. Comput. Aided Geom. Design, 23(2):83-112, 2006. URL: https://doi.org/10.1016/j.cagd.2005.05.002.
  37. Clara I. Grima and Alberto Márquez. Computational Geometry on Surfaces. Springer, 2001. Google Scholar
  38. John E. Hopcroft and Peter J. Kahn. A paradigm for robust geometric algorithms. Algorithmica, 7(1-6):339-380, 1992. URL: https://doi.org/10.1007/BF01758769.
  39. David Huffman. A duality concept for the analysis of polyhedral scenes. In Edward W. Elcock and Donald Michie, editors, Machine Intelligence, volume 8, pages 475-492. Ellis Horwood Ltd. and John Wiley & Sons, 1977. Google Scholar
  40. Alexander Igambardiev and André Schulz. A duality transform for constructing small grid embeddings of 3d polytopes. Comput. Geom. Theory Appl., 56:19-36, 2016. URL: https://doi.org/10.1016/j.comgeo.2016.03.004.
  41. Clause Indermitte, Thomas M. Liebling, Marc Troyanov, and Heinz Clemençon. Voronoi diagrams on piecewise flat surfaces and an application to biological growth. Theoret. Comput. Sci., 263(1-2):263-274, 2001. URL: https://doi.org/10.1016/S0304-3975(00)00248-6.
  42. Ivan Izmestiev. Statics and kinematics of frameworks in Euclidean and non-Euclidean geometry. In Vincent Alberge and Athanase Papadopoulos, editors, Eighteen Essays in Non-Euclidean Geometry, number 29 in IRMA Lectures in Mathematics and Theoretical Physics. Europ. Math. Soc., 2019. URL: https://doi.org/10.4171/196-1/12.
  43. Paul Koebe. Kontaktprobleme der Konformen Abbildung. Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl., 88:141-164, 1936. Google Scholar
  44. Andrew Kotlov, László Lovász, and Santosh Vempala. The Colin de Verdière number and sphere representations of a graph. Combinatorica, 17(4):483-521, 1997. URL: https://doi.org/10.1007/BF01195002.
  45. Yves Ladegaillerie. Classes d'isotopie de plongements de 1-complexes dans les surfaces. Topology, 23(3):303-311, 1984. Google Scholar
  46. Charles L. Lawson. Transforming triangulations. Discrete Math., 3(4):365-372, 1972. URL: https://doi.org/10.1016/0012-365X(72)90093-3.
  47. László Lovász. Representations of polyhedra and the Colin de Verdière number. J. Comb. Theory Ser. B, 82(2):223-236, 2001. URL: https://doi.org/10.1006/jctb.2000.2027.
  48. László Lovász. Discrete analytic functions: An exposition. In Alexander Grigor’yan and Shing-Tung Yau, editors, Eigenvalues of Laplacians and other geometric operators, volume 9 of Surveys in Differential Geometry, pages 241-273. Int. Press, 2004. URL: https://doi.org/10.4310/SDG.2004.v9.n1.a7.
  49. László Lovász. Graphs and Geometry. Number 69 in Colloquium Publications. Amer. Math. Soc., 2019. Google Scholar
  50. James Clerk Maxwell. On reciprocal figures and diagrams of forces. Phil. Mag. (Ser. 4), 27(182):250-261, 1864. URL: https://doi.org/10.1080/14786446408643663.
  51. James Clerk Maxwell. On the application of the theory of reciprocal polar figures to the construction of diagrams of forces. Engineer, 24:402, 1867. Google Scholar
  52. James Clerk Maxwell. On reciprocal figures, frames, and diagrams of forces. Trans. Royal Soc. Edinburgh, 26(1):1-40, 1870. URL: https://doi.org/10.1017/S0080456800026351.
  53. Maria Mazón and Tomás Recio. Voronoi diagrams on orbifolds. Comput. Geom. Theory Appl., 8(5):219-230, 1997. URL: https://doi.org/10.1016/S0925-7721(96)00017-X.
  54. Bojan Mohar. A polynomial time circle packing algorithm. Discrete Math., 117(1-3):257-263, 1993. URL: https://doi.org/10.1016/0012-365X(93)90340-Y.
  55. Bojan Mohar. Circle packings of maps - The Euclidean case. Rend. Sem. Mat. Fis. Milano, 67(1):191-206, 1997. URL: https://doi.org/10.1007/BF02930499.
  56. Bojan Mohar. Circle packings of maps in polynomial time. Europ. J. Combin., 18(7):785-805, 1997. URL: https://doi.org/10.1006/eujc.1996.0135.
  57. Bojan Mohar and Pierre Rosenstiehl. Tessellation and visibility representations of maps on the torus. Discrete Comput. Geom., 19(2):249-263, 1998. URL: https://doi.org/10.1007/PL00009344.
  58. Bojan Mohar and Alexander Schrijver. Blocking nonorientability of a surface. J. Comb. Theory Ser. B, 87(1):2-16, 2003. Google Scholar
  59. Shmuel Onn and Bernd Sturmfels. A quantitative Steinitz' theorem. Beitr. Algebra Geom., 35(1):125-129, 1994. URL: https://www.emis.de/journals/BAG/vol.35/no.1/.
  60. David Orden, Günter Rote, Fransisco Santos, Brigitte Servatius, Herman Servatius, and Walter Whiteley. Non-crossing frameworks with non-crossing reciprocals. Discrete Comput. Geom., 32(4):567-600, 2004. URL: https://doi.org/10.1007/s00454-004-1139-x.
  61. W. J. Macquorn Rankine. Principle of the equilibrium of polyhedral frams. London, Edinburgh, and Dublin Phil. Mag J. Sci., 27(180):92, 1864. URL: https://doi.org/10.1080/14786446408643629.
  62. William John Macquorn Rankine. A Manual of Applied Mechanics. Richard Griffin and Co., 1858. URL: https://archive.org/details/manualappmecha00rankrich.
  63. Ares Ribó Mor, Günter Rote, and André Schulz. Small grid embeddings of 3-polytopes. Discrete Comput. Geom., 45(1):65-87, 2011. URL: https://doi.org/10.1007/s00454-010-9301-0.
  64. Jürgen Richter-Gebert. Realization spaces of polytopes. Number 1643 in Lecture Notes Math. Springer, 1996. URL: https://doi.org/10.1007/BFb0093761.
  65. Igor Rivin. Euclidean structures on simplicial surfaces and hyperbolic volume. Ann. Math., 139:553-580, 1994. URL: https://doi.org/10.2307/2118572.
  66. Günter Rote, Fransisco Santos, and Ileana Streinu. Pseudo-triangulations - a survey. In Jacob E. Goodman, János Pach, and Richard Pollack, editors, Essays on Discrete and Computational Geometry: Twenty Years Later, number 453 in Contemporary Mathematics, pages 343-410. Amer. Math. Soc., 2008. Google Scholar
  67. André Schulz. Drawing 3-polytopes with good vertex resolution. J. Graph Algorithms Appl., 15(1):33-52, 2011. URL: https://doi.org/10.7155/jgaa.00216.
  68. Dvir Steiner and Anath Fischer. Planar parameterization for closed 2-manifold genus-1 meshes. In Proc. 9th ACM Symp. Solid Modeling Appl., pages 83-91, 2004. Google Scholar
  69. Ernst Steinitz. Polyeder und Raumeinteilungen. Enzyklopädie der mathematischen Wissenschaften mit Einschluss ihrer Anwendungen, III.AB(12):1-139, 1916. Google Scholar
  70. Ernst Steinitz and Hans Rademacher. Vorlesungen über die Theorie der Polyeder: unter Einschluß der Elemente der Topologie, volume 41 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, 1934. Reprinted 1976. Google Scholar
  71. Kenneth Stephenson. Introduction to Circle Packing: The Theory of Discrete Analytic Functions. Cambridge Univ. Press, 2005. Google Scholar
  72. Ileana Streinu. Erratum to “Pseudo-triangulations, rigidity and motion planning”. Discrete Comput. Geom., 35(2):358, 2006. URL: https://doi.org/10.1007/s00454-006-3300-1.
  73. Ileana Streinu. Pseudo-triangulations, rigidity and motion planning. Discrete Comput. Geom., 34(4):587-635, 2006. Publisher’s erratum in [72]. URL: https://doi.org/10.1007/s00454-005-1184-0.
  74. Kokichi Sugihara. Realizability of polyhedrons from line drawings. In Godfried T. Toussaint, editor, Computational Morphology: A Computational Geometric Approach to the Analysis Of Form, number 6 in Machine Intelligence and Pattern Recognition, pages 177-206, 1988. Google Scholar
  75. William T. Tutte. How to draw a graph. Proc. London Math. Soc., 13(3):743-768, 1963. Google Scholar
  76. Pierre Varignon. Nouvelle mechanique ou statique, dont le projet fut donné en M.DC.LXXVII. Claude Jombert, Paris, 1725. URL: https://gallica.bnf.fr/ark:/12148/bpt6k5652714w.texteImage.
  77. Walter Whiteley. Motion and stresses of projected polyhedra. Topologie structurale / Structural Topology, 7:13-38, 1982. URL: http://hdl.handle.net/2099/989.
  78. Walter Whiteley, Peter F. Ash, Ethan Poiker, and Henry Crapo. Convex polyhedra, Dirichlet tesselations, and spider webs. In Marjorie Senechal, editor, Shaping Space: Exploring Polyhedra in Nature, Art, and the Geometrical Imagination, chapter 18, pages 231-251. Springer, 2013. URL: https://doi.org/10.1007/978-0-387-92714-5_18.
  79. Günter M. Ziegler. Lectures on Polytopes. Number 152 in Graduate Texts in Mathematics. Springer, 1995. Google Scholar
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact