The $d$-dimensional realisation number of a rigid graph
Preprint
Abstract
Determining the number of (complex) realisations of a rigid graph for a specific choice of edge lengths is a fundamental problem in discrete geometry. In this article we provide two new tools for determining realisation numbers in arbitrary dimensions: (i) we prove that subgraph inclusion translates to realisation number divisibility; and (ii) we provide lower bounds on realisation numbers under specific graph operations in all dimensions. We use these methods to prove that every triangulated sphere with $n$ vertices has at least $2^{n-4}$ edge-length equivalent realisations in 3-dimensions, extending a 2-dimensional result of Jackson and Owen in the case of planar graphs. Additionally, our tools solve a family of conjectures set by Grasegger regarding how 1-extensions, X-replacements, and V-replacements affect realisation numbers.
Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- New Upper Bounds for the Number of Embeddings of Minimally Rigid GraphsDiscrete & Computational Geometry, 2022
- On the maximal number of real embeddings of minimally rigid graphs in R2, R3 and S2Journal of Symbolic Computation, 2021
- Equivalent realisations of a rigid graphDiscrete Applied Mathematics, 2019
- Generic Global Rigidity in Complex and Pseudo-Euclidean Spaces2014
- Mixed volume techniques for embeddings of Laman graphsComputational Geometry, 2010
- Generic Global RigidityDiscrete & Computational Geometry, 2004
- The Number of Embeddings of Minimally Rigid GraphsDiscrete & Computational Geometry, 2004
- A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroidJournal of Combinatorial Theory, Series B, 2003
- Almost all simply connected closed surfaces are rigid1975
- L. On the calculation of the equilibrium and stiffness of framesJournal of Computers in Education, 1864