# 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 $\mathbb{R}^d$ has a realization in $\mathbb{R}^d$ that is both generic and universally rigid. It also must have a realization in $\mathbb{R}^d$ 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.