Generic Global and Universal Rigidity

Authors: Robert Connelly, Steven J. Gortler, and Louis Theran
Preprint: 1604.07475, 2016
Full text: arXiv

We show that any graph that is generically globally rigid in has a realization in that is both generic and universally rigid. It also must have a realization in that is both infinitesimally rigid and universally rigid. Such a realization serves as a certificate of generic global rigidity. Previous certificates for generic global rigidity, even though they did involve calculations for particular configurations, did not necessarily guarantee that those configurations were globally rigid.

Our approach involves an algorithm by Lovász, Saks and Schrijver that constructs a general position orthogonal representation of the vertices, when the graph is vertex (d+1)-connected, and a result of Alfakih that shows how this representation leads to a stress matrix and a universally rigid framework of the graph.