Generic rigidity in three dimensions
Can we decide in polynomial time whether a given graph is rigid in 3-dimensional space?
Remarks
The problem amounts to deciding independence in the 3-dimensional rigidity matroid of a graph in polynomial time. Since the matroid is represented by a matrix of indeterminates, there is a randomized polynomial algorithm to decide the rigidity of a graph, in arbitrary dimension.
Various lower and upper bounds on the rank function of the rigidity matroid are described in the survey of Jackson and Jordán [1]. They also propose a conjecture that would imply a good characterization of the rank function. Partial results are obtained in [2] and [3].
In the special case when we want to decide the 3-dimensional rigidity of the square of a graph, there is a characterization that became known as the Molecular Conjecture. The validity of the characterization was proved by Katoh and Tanigawa [4].
References
- ↑ B. Jackson, T. Jordán, On the rank function of the 3-dimensional rigidity matroid, DOI link, EGRES Technical Report
- ↑ B. Jackson, A necessary condition for generic rigidity of bar-and-joint frameworks in d-space, arXiv link
- ↑ J. Cruickshank, On Spaces of Infinitesimal Motions and Henneberg Extensions, DOI link, arXiv link
- ↑ N. Katoh, S. Tanigawa, A Proof of the Molecular Conjecture, DOI link, arXiv link
