| Geometry © 2003 Springer-Verlag New York Inc. The Number of Embeddings of Minimally Rigid Graphs ∗ (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. Rigid frameworks in some Euclidean space are embedded graphs having a unique local realization (up to Euclidean motions) for the given edge lengths, although globally they may have several. We study the number of distinct planar embeddings of minimally rigid graphs with n vertices. We show that, modulo planar rigid motions, this number is at most � � 2n−4 n ≈ 4. We also exhibit several families which realize lower bounds n−2 of the order of 2n,2.21n and 2.28n. For the upper bound we use techniques from complex algebraic geometry, based on the (projective) Cayley–Menger variety CM2,n (C) ⊂ P n ( 2)−1(C) over the complex numbers C. In this context, point configurations are represented by coordinates given by squared distances between all pairs of points. Sectioning the variety with 2n − 4 hyperplanes yields at most deg(CM2,n) zero-dimensional components, and one finds this degree to be D2,n � � = 1 2n−4. The lower bounds are related to inductive constructions of minimally rigid graphs 2 n−2 via Henneberg sequences. The same approach works in higher dimensions. In particular, we show that it leads to an upper bound of 2D3,n = (2n−3 /(n − 2)) � � 2n−6 for the number of spatial embeddings n−3 with generic edge lengths of the 1-skeleton of a simplicial polyhedron, up to rigid motions. Our technique can also be adapted to the non-Euclidean case. 1. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||