Generically globally rigid graphs have generic universally rigid frameworks

Robert Connelly, Steven Gortler, Louis Simon Theran

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

We show that any graph that is generically globally rigid in ℝd has a realization in ℝd both generic and universally rigid. It also must have a realization in ℝd that is both infinitesimally rigid and universally rigid. This also implies that the graph also must have a realization in ℝd that is both infinitesimally rigid and universally rigid; such a realization serves as a certificate of generic global rigidity.

Our approach involves an algorithm by Lovász, Saks and Schrijver that, for a sufficiently connected graph, constructs a general position orthogonal representation of the vertices, and a result of Alfakih that shows how this representation leads to a stress matrix and a universally rigid framework of the graph.
Original languageEnglish
Pages (from-to)1-37
JournalCombinatorica
Volume40
DOIs
Publication statusPublished - 22 Mar 2020

Fingerprint

Dive into the research topics of 'Generically globally rigid graphs have generic universally rigid frameworks'. Together they form a unique fingerprint.

Cite this