# 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