Coupler curves of moving graphs and counting realizations of rigid graphs

Grasegger, Georg; El Hilany, Boulos; Lubbes, Niels

doi:10.1090/mcom/3886

Coupler curves of moving graphs and counting realizations of rigid graphs
HTML articles powered by AMS MathViewer

by Georg Grasegger, Boulos El Hilany and Niels Lubbes

Math. Comp. 93 (2024), 459-504

DOI: https://doi.org/10.1090/mcom/3886

Published electronically: August 25, 2023

HTML | PDF | Request permission

Abstract:

A calligraph is a graph that for almost all edge length assignments moves with one degree of freedom in the plane, if we fix an edge and consider the vertices as revolute joints. The trajectory of a distinguished vertex of the calligraph is called its coupler curve. To each calligraph we uniquely assign a vector consisting of three integers. This vector bounds the degrees and geometric genera of irreducible components of the coupler curve. A graph, that up to rotations and translations admits finitely many, but at least two, realizations into the plane for almost all edge length assignments, is a union of two calligraphs. We show that this number of realizations is equal to a certain inner product of the vectors associated to these two calligraphs. As an application we obtain an improved algorithm for counting numbers of realizations, and by counting realizations we characterize invariants of coupler curves.

References

Evangelos Bartzos, Ioannis Z. Emiris, Jan Legerský, and Elias Tsigaridas, On the maximal number of real embeddings of minimally rigid graphs in $\Bbb R^2$, $\Bbb R^3$ and $S^2$, J. Symbolic Comput. 102 (2021), 189–208. MR 4131456, DOI 10.1016/j.jsc.2019.10.015
Evangelos Bartzos, Ioannis Z. Emiris, and Josef Schicho, On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs, Appl. Algebra Engrg. Comm. Comput. 31 (2020), no. 5-6, 325–357. MR 4160790, DOI 10.1007/s00200-020-00447-7
Evangelos Bartzos, Ioannis Z. Emiris, and Raimundas Vidunas, New upper bounds for the number of embeddings of minimally rigid graphs, Discrete Comput. Geom. 68 (2022), no. 3, 796–816. MR 4481322, DOI 10.1007/s00454-022-00370-3
Ciprian Borcea and Ileana Streinu, The number of embeddings of minimally rigid graphs, Discrete Comput. Geom. 31 (2004), no. 2, 287–303. MR 2060642, DOI 10.1007/s00454-003-2902-0
Jose Capco, Matteo Gallet, Georg Grasegger, Christoph Koutschan, Niels Lubbes, and Josef Schicho, The number of realizations of a Laman graph, SIAM J. Appl. Algebra Geom. 2 (2018), no. 1, 94–125. MR 3771397, DOI 10.1137/17M1118312
Robert Connelly, Generic global rigidity, Discrete Comput. Geom. 33 (2005), no. 4, 549–563. MR 2132290, DOI 10.1007/s00454-004-1124-4
David Cox, John Little, and Donal O’Shea, Ideals, varieties, and algorithms, 3rd ed., Undergraduate Texts in Mathematics, Springer, New York, 2007. An introduction to computational algebraic geometry and commutative algebra. MR 2290010, DOI 10.1007/978-0-387-35651-8
David Eisenbud and Joe Harris, 3264 and all that—a second course in algebraic geometry, Cambridge University Press, Cambridge, 2016. MR 3617981, DOI 10.1017/CBO9781139062046
Ioannis Z. Emiris, Elias P. Tsigaridas, and Antonios E. Varvitsiotis, Algebraic methods for counting Euclidean embeddings of rigid graphs, Graph drawing, Lecture Notes in Comput. Sci., vol. 5849, Springer, Berlin, 2010, pp. 195–200. MR 2680451, DOI 10.1007/978-3-642-11805-0_{1}9
Matteo Gallet, Christoph Koutschan, Zijia Li, Georg Regensburger, Josef Schicho, and Nelly Villamizar, Planar linkages following a prescribed motion, Math. Comp. 86 (2017), no. 303, 473–506. MR 3557808, DOI 10.1090/mcom/3120
G. Grasegger, B. El Hilany, and N. Lubbes, Calligraphs and counting realizations of minimally rigid graphs, 2022, Software.
Georg Grasegger, Christoph Koutschan, and Elias Tsigaridas, Lower bounds on the number of realizations of rigid graphs, Exp. Math. 29 (2020), no. 2, 125–136. MR 4101414, DOI 10.1080/10586458.2018.1437851
Robin Hartshorne, Algebraic geometry, Graduate Texts in Mathematics, No. 52, Springer-Verlag, New York-Heidelberg, 1977. MR 463157, DOI 10.1007/978-1-4757-3849-0
K. H. Hunt, Kinematic geometry of mechanisms, Oxford Engineering Science Series, vol. 7, The Clarendon Press, Oxford University Press, New York, 1990. Corrected reprint of the 1978 original; Oxford Science Publications. MR 1070564
Bill Jackson and J. C. Owen, Equivalent realisations of a rigid graph, Discrete Appl. Math. 256 (2019), 42–58. MR 3926359, DOI 10.1016/j.dam.2017.12.009
Donald J. Jacobs and Bruce Hendrickson, An algorithm for two-dimensional rigidity percolation: the pebble game, J. Comput. Phys. 137 (1997), no. 2, 346–365. MR 1481894, DOI 10.1006/jcph.1997.5809
A. B. Kempe, On a General Method of describing Plane Curves of the nth degree by Linkwork, Proc. Lond. Math. Soc. 7 (1875/76), 213–216. MR 1575631, DOI 10.1112/plms/s1-7.1.213
G. Laman, On graphs and rigidity of plane skeletal structures, J. Engrg. Math. 4 (1970), 331–340. MR 269535, DOI 10.1007/BF01534980
Zijia Li, Josef Schicho, and Hans-Peter Schröcker, Kempe’s universality theorem for rational space curves, Found. Comput. Math. 18 (2018), no. 2, 509–536. MR 3777787, DOI 10.1007/s10208-017-9348-x
J. C. Maxwell, On the calculation of the equilibrium and stiffness of frames, The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science 27 (1864), no. 182, 294–299.
Rick Miranda, Linear systems of plane curves, Notices Amer. Math. Soc. 46 (1999), no. 2, 192–201. MR 1673756
H. Pollaczek-Geiringer, Über die Gliederung ebener Fachwerke, Z. Angew. Math. Mech. 7 (1927), 58–72.
M. Sadjadi, V. F. Hagh, M. Kang, M. Sitharam, R. Connelly, S. J. Gortler, L. Theran, M. Holmes-Cerfon, and M. F. Thorpe, Realizations of isostatic material frameworks, Phys. Status Solidi (b) 258 (2021), no. 9, 2000555.
Josef Schicho, And yet it moves: paradoxically moving linkages in kinematics, Bull. Amer. Math. Soc. (N.S.) 59 (2022), no. 1, 59–95. MR 4340827, DOI 10.1090/S0273-0979-2021-01721-6
Robert Silhol, Real algebraic surfaces, Lecture Notes in Mathematics, vol. 1392, Springer-Verlag, Berlin, 1989. MR 1015720, DOI 10.1007/BFb0088815
Reinhard Steffens and Thorsten Theobald, Mixed volume techniques for embeddings of Laman graphs, Comput. Geom. 43 (2010), no. 2, 84–93. MR 2569533, DOI 10.1016/j.comgeo.2009.04.004
Jaeman Kim, Rigidity theorems for Einstein-Thorpe metrics, Geom. Dedicata 80 (2000), no. 1-3, 281–287. MR 1762514, DOI 10.1023/A:1005208930993
W. Wunderlich, Höhere Koppelkurven, Österreichisches Ingenieur-Archiv 17 (1963), 162–165.