Characterizing generic global rigidity

Source abstract

A $d$-dimensional {\it framework} is a graph and a map from its vertices to~${\Bbb E}^d$. Such a framework is {\it globally rigid} if it is the only framework in ${\Bbb 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: a generic framework is globally rigid if and only if it has a stress matrix with kernel of dimension $d+1$, the minimum possible. An alternate version of the condition comes from considering the geometry of the length-squared mapping~$\ell$: the graph is generically locally rigid iff the rank of $\ell$ is maximal, and it is generically globally rigid iff the rank of the Gauss map on the image of $\ell$ is maximal. We also show that this condition is efficiently checkable with a randomized algorithm, and prove that if a graph is not generically globally rigid then it is flexible one dimension higher.