Dylan Thurston, Columbia University
Characterizing Generic Global Rigidity

A d-dimensional framework is a graph and a map from its vertices to E^d. Such a framework is globally rigid if it is the only framework in E^d with the same graph and edge lengths, up to rigid motions. For which underlying graphs is a generic framework globally rigid? We answer this question by proving a conjecture by Connelly, that his sufficient condition is also necessary. The condition comes from considering the geometry of the length-squared mapping l; essentially, the graph is generically locally rigid iff the rank of l is maximal, and it is generically globally rigid iff the rank of the Gauss map on the image of l is maximal. (This is an equivalent reformulation of Connelly's version of the condition, which was in terms of the size of the kernel of a generic stress matrix.) We also show that this condition is efficiently checkable with a randomized algorithm.

This is joint work with Steven Gortler and Alex

Back to the VGS page.