Generic rigidity in three dimensions

From Egres Open
Jump to: navigation, search

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

  1. B. Jackson, T. Jordán, On the rank function of the 3-dimensional rigidity matroid, DOI link, EGRES Technical Report
  2. B. Jackson, A necessary condition for generic rigidity of bar-and-joint frameworks in d-space, arXiv link
  3. J. Cruickshank, On Spaces of Infinitesimal Motions and Henneberg Extensions, DOI link, arXiv link
  4. N. Katoh, S. Tanigawa, A Proof of the Molecular Conjecture, DOI link, arXiv link