Generically globally rigid graphs have generic universally rigid frameworks

Graph representations (geometric and intersection representations, etc.) (05C62) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Abstract: We show that any graph that is generically globally rigid in

m a t h b b R^{d}

has a realization in

m a t h b b R^{d}

that is both generic and universally rigid. This also implies that the graph also must have a realization in

m a t h b b R^{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'asz, 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.

Review text

A framework in \(\mathbb{R}^d\) is a pair \((G,\mathrm{p})\), where \(G\) is a finite graph with \(n\) vertices and \(\mathrm{p}:=(\mathrm{p}_1,\ldots,\mathrm{p}_n)\) is a realization of its vertices in \(\mathbb{R}^d\). A framework \((G,\mathrm{p})\) for \(G\) is \textit{globally rigid} in \(\mathbb{R}^d\) if every framework \((G,\mathrm{q})\) for \(G\) in \(\mathbb{R}^d\), with edges of the same length as \((G,\mathrm{p})\), is congruent to \((G,\mathrm{p})\). A framework \((G,\mathrm{p})\) is \textit{universally rigid} if every framework \((G,\mathrm{q})\) for \(G\) in any finite-dimensional Euclidean space, with the same edge lengths, is congruent to \((G,\mathrm{p})\). A graph \(G\) is \textit{generically globally rigid} in \(\mathbb{R}^d\) if every ``generic framework for \(G\) is \textit{globally rigid}. The authors prove that any graph \(G\) that is generically globally rigid in \(\mathbb{R}^d\) has a realization in \(\mathbb{R}^d\) that is both generic and universally rigid. This implies that \(G\) must also have a realization in \(\mathbb{R}^d\) that is both infinitesimally rigid and universally rigid.

Recommendations

Cites work

Cited in

(17)

This page was built for publication: Generically globally rigid graphs have generic universally rigid frameworks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2182252)