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

Abstract

A graph is $d$-rigid if for any generic realisation of the graph in ${\mathbb{R}}^d$ (equivalently, the $d$-dimensional sphere ${\mathbb{S}}^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^{\ast }(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)\le c_2^{\ast }(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)\le c_d^{\ast }(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.

33 pages, 8 figures

References in corpus (4)

• The number of realizations of a Laman graph
• Counting realizations of Laman graphs on the sphere
• On the maximal number of real embeddings of minimally rigid graphs in ${\mathbb{R}}^2$, ${\mathbb{R}}^3$ and $S^2$
• Lower bounds on the number of realizations of rigid graphs