The number of realisations of a rigid graph in Euclidean and spherical geometries

Dewar, Sean; Grasegger, Georg

doi:10.5802/alco.390

Dewar, Sean ¹; Grasegger, Georg ²

¹ School of Mathematics, University of Bristol, Bristol, UK
² Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Linz, Austria

Algebraic Combinatorics, Volume 7 (2024) no. 6, pp. 1615-1645.

Abstract

A graph is $d$ -rigid if for any generic realisation of the graph in $ℝ^{d}$ (equivalently, the $d$ -dimensional sphere $𝕊^{d}$ ), there are only finitely many non-congruent realisations in the same space with the same edge lengths. By extending this definition to complex realisations in a natural way, we define $c_{d} (G)$ to be the number of equivalent $d$ -dimensional complex realisations of a $d$ -rigid graph $G$ for a given generic realisation, and $c_{d}^{*} (G)$ to be the number of equivalent $d$ -dimensional complex spherical realisations of $G$ for a given generic spherical realisation. Somewhat surprisingly, these two realisation numbers are not always equal. Recently developed algorithms for computing realisation numbers determined that the inequality $c_{2} (G) \leq c_{2}^{*} (G)$ holds for any minimally 2-rigid graph $G$ with 12 vertices or less. In this paper we confirm that, for any dimension $d$ , the inequality $c_{d} (G) \leq c_{d}^{*} (G)$ holds for every $d$ -rigid graph $G$ . This result is obtained via new techniques involving coning, the graph operation that adds an extra vertex adjacent to all original vertices of the graph.

Received: 2023-10-12
Revised: 2024-02-29
Accepted: 2024-07-08
Published online: 2025-01-07

DOI: 10.5802/alco.390

Classification: 52C25, 05C30, 68R10, 68R12
Mots-clés : rigid graph, realisation count, non-Euclidean geometry, pseudo-Euclidean space

Author's affiliations:

Dewar, Sean ¹; Grasegger, Georg ²

¹ School of Mathematics, University of Bristol, Bristol, UK
² Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Linz, Austria

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{ALCO_2024__7_6_1615_0,
     author = {Dewar, Sean and Grasegger, Georg},
     title = {The number of realisations of a rigid graph in {Euclidean} and spherical geometries},
     journal = {Algebraic Combinatorics},
     pages = {1615--1645},
     publisher = {The Combinatorics Consortium},
     volume = {7},
     number = {6},
     year = {2024},
     doi = {10.5802/alco.390},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.390/}
}

TY  - JOUR
AU  - Dewar, Sean
AU  - Grasegger, Georg
TI  - The number of realisations of a rigid graph in Euclidean and spherical geometries
JO  - Algebraic Combinatorics
PY  - 2024
SP  - 1615
EP  - 1645
VL  - 7
IS  - 6
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.390/
DO  - 10.5802/alco.390
LA  - en
ID  - ALCO_2024__7_6_1615_0
ER  -

%0 Journal Article
%A Dewar, Sean
%A Grasegger, Georg
%T The number of realisations of a rigid graph in Euclidean and spherical geometries
%J Algebraic Combinatorics
%D 2024
%P 1615-1645
%V 7
%N 6
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.390/
%R 10.5802/alco.390
%G en
%F ALCO_2024__7_6_1615_0

Dewar, Sean; Grasegger, Georg. The number of realisations of a rigid graph in Euclidean and spherical geometries. Algebraic Combinatorics, Volume 7 (2024) no. 6, pp. 1615-1645. doi : 10.5802/alco.390. https://alco.centre-mersenne.org/articles/10.5802/alco.390/

References
Cited by

[1] Abbott, Timothy G. Generalizations of Kempe’s universality theorem, Masters thesis, Massachusetts Institute of Technology (2008)

[2] Asimow, L.; Roth, B. The rigidity of graphs, Trans. Amer. Math. Soc., Volume 245 (1978), pp. 279-289 | DOI | MR | Zbl

[3] Bartzos, Evangelos; Emiris, Ioannis Z.; Legerský, Jan; Tsigaridas, Elias On the maximal number of real embeddings of minimally rigid graphs in $ℝ^{2}$ , $ℝ^{3}$ and $S^{2}$ , J. Symbolic Comput., Volume 102 (2021), pp. 189-208 | DOI | MR | Zbl

[4] Bartzos, Evangelos; Emiris, Ioannis Z.; Schicho, Josef On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs, Appl. Algebra Engrg. Comm. Comput., Volume 31 (2020) no. 5-6, pp. 325-357 | DOI | MR | Zbl

[5] Bartzos, Evangelos; Emiris, Ioannis Z.; Tzamos, Charalambos An asymptotic upper bound for graph embeddings, Discrete Appl. Math., Volume 327 (2023), pp. 157-177 | DOI | MR | Zbl

[6] Bartzos, Evangelos; Emiris, Ioannis Z.; Vidunas, Raimundas New upper bounds for the number of embeddings of minimally rigid graphs, Discrete Comput. Geom., Volume 68 (2022) no. 3, pp. 796-816 | DOI | MR | Zbl

[7] Borcea, Ciprian; Streinu, Ileana The number of embeddings of minimally rigid graphs, Discrete Comput. Geom., Volume 31 (2004) no. 2, pp. 287-303 | DOI | MR | Zbl

[8] Borel, Armand Linear algebraic groups, Graduate Texts in Mathematics, 126, Springer-Verlag, New York, 1991, xii+288 pages | DOI | MR

[9] Capco, Jose; Gallet, Matteo; Grasegger, Georg; Koutschan, Christoph; Lubbes, Niels; Schicho, Josef An algorithm for computing the number of realizations of a Laman graph, Zenodo, 2018 | DOI

[10] Capco, Jose; Gallet, Matteo; Grasegger, Georg; Koutschan, Christoph; Lubbes, Niels; Schicho, Josef The number of realizations of a Laman graph, SIAM J. Appl. Algebra Geom., Volume 2 (2018) no. 1, pp. 94-125 | DOI | MR | Zbl

[11] Capco, Jose; Gallet, Matteo; Grasegger, Georg; Koutschan, Christoph; Lubbes, Niels; Schicho, Josef The number of realizations of all Laman graphs with at most 12 vertices, Zenodo, 2018 | DOI

[12] Connelly, R.; Whiteley, W. J. Global rigidity: the effect of coning, Discrete Comput. Geom., Volume 43 (2010) no. 4, pp. 717-735 | DOI | MR | Zbl

[13] Eftekhari, Yaser; Jackson, Bill; Nixon, Anthony; Schulze, Bernd; Tanigawa, Shin-ichi; Whiteley, Walter Point-hyperplane frameworks, slider joints, and rigidity preserving transformations, J. Combin. Theory Ser. B, Volume 135 (2019), pp. 44-74 | DOI | MR | Zbl

[14] Fritzsche, Klaus; Grauert, Hans From holomorphic functions to complex manifolds, Graduate Texts in Mathematics, 213, Springer-Verlag, New York, 2002, xvi+392 pages | DOI | MR

[15] Gallet, Matteo; Grasegger, Georg; Schicho, Josef Counting realizations of Laman graphs on the sphere, Electron. J. Combin., Volume 27 (2020) no. 2, Paper no. 2.5, 18 pages | DOI | MR | Zbl

[16] Gallet, Matteo; Grasegger, Georg; Schicho, Josef Software for counting realizations of minimally rigid graphs on the sphere, Zenodo, 2022 | DOI

[17] Gortler, Steven J.; Thurston, Dylan P. Generic global rigidity in complex and pseudo-Euclidean spaces, Rigidity and symmetry (Fields Inst. Commun.), Volume 70, Springer, New York, 2014, pp. 131-154 | DOI | MR | Zbl

[18] Grasegger, Georg RigiComp — A Mathematica package for computational rigidity of graphs, Zenodo, 2022 | DOI

[19] Grasegger, Georg; Koutschan, Christoph; Tsigaridas, Elias Lower bounds on the number of realizations of rigid graphs, Exp. Math., Volume 29 (2020) no. 2, pp. 125-136 | DOI | MR | Zbl

[20] Graver, Jack; Servatius, Brigitte; Servatius, Herman Combinatorial rigidity, Graduate Studies in Mathematics, 2, American Mathematical Society, Providence, RI, 1993, x+172 pages | DOI | MR

[21] Harris, Joe Algebraic geometry. A first course, Graduate Texts in Mathematics, 133, Springer-Verlag, New York, 1992, xx+328 pages | DOI | MR

[22] Hopcroft, John; Tarjan, Robert Algorithm 447: Efficient algorithms for graph manipulation, Communications of the ACM, Volume 16 (1973) no. 6, pp. 372-378 | DOI

[23] Izmestiev, Ivan Projective background of the infinitesimal rigidity of frameworks, Geom. Dedicata, Volume 140 (2009), pp. 183-203 | DOI | MR | Zbl

[24] Jackson, Bill; Owen, J. C. Equivalent realisations of a rigid graph, Discrete Appl. Math., Volume 256 (2019), pp. 42-58 | DOI | MR | Zbl

[25] Mumford, David The red book of varieties and schemes, Lecture Notes in Mathematics, 1358, Springer-Verlag, Berlin, 1988, vi+309 pages | DOI | MR

[26] Pogorelov, A. V. Extrinsic geometry of convex surfaces, Translations of Mathematical Monographs, Vol. 35, American Mathematical Society, Providence, RI, 1973, vi+669 pages (Translated from the Russian by Israel Program for Scientific Translations) | DOI | MR

[27] Roman, Steven Advanced linear algebra, Graduate Texts in Mathematics, 135, Springer, New York, 2008, xviii+522 pages | DOI | MR

[28] Steffens, Reinhard; Theobald, Thorsten Mixed volume techniques for embeddings of Laman graphs, Comput. Geom., Volume 43 (2010) no. 2, pp. 84-93 | DOI | MR | Zbl

[29] Tay, Tiong-Seng; Whiteley, Walter Generating isostatic frameworks, Structural Topology (1985) no. 11, pp. 21-69 | MR | Zbl

[30] Whiteley, Walter Cones, infinity and $1$ -story buildings, Structural Topology (1983) no. 8, pp. 53-70 | MR | Zbl

Cited by Sources: