# Characterizing Generic Global Rigidity

Steven J. Gortler, Alexander D. Healy, Dylan P. Thurston

Arxiv ID: 0710.0926•Last updated: 10/13/2021

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: 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 l: 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.
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.

#### PaperStudio AI Chat

I'm your research assistant! Ask me anything about this paper.