The Number of Embeddings of Minimally Rigid Graphs

Rigid frameworks in some Euclidean space are embedded graphshaving a unique local realization (up to Euclidean motions) forthe given edge lengths, although globally they may have several.We study the number of distinct planar embeddings of minimallyrigid graphs with $n$ vertices. We show that, modulo planar rigidmotions, this number is at most ${{2n-4}choose {n-2}} approx4^n$. We also exhibit several families which realize lower boundsof the order of $2^n$, $2.21^n$ and $2.28^n$.For the upper bound we use techniques from complex algebraicgeometry, based on the (projective) Cayley--Menger variety${it CM}^{2,n}(C)subset P_{{{n}choose {2}}-1}(C)$ over the complexnumbers $C$. In this context, point configurations are representedby coordinates given by squared distances between all pairs ofpoints. Sectioning the variety with $2n-4$ hyperplanes yields atmost $deg({it CM}^{2,n})$ zero-dimensional components, and one findsthis degree to be $D^{2,n}=frac{1}{2}{{2n-4}choose {n-2}}$.The lower bounds are related to inductive constructions ofminimally rigid graphs via Henneberg sequences.The same approach works in higher dimensions. In particular, weshow that it leads to an upper bound of $2 D^{3,n}={({2^{n-3}}/({n-2}})){{2n-6}choose{n-3}}$ for the number ofspatial embeddings with generic edge lengths of the $1$-skeletonof a simplicial polyhedron, up to rigid motions.Our technique can also be adapted to the non-Euclidean case.