# Rigid graph

## Bar-joint frameworks

For a graph [math]G=(V,E)[/math], a *d*-dimensional **realization** of *G* is a function [math]p:V \rightarrow \mathbb{R}^d[/math]. A *d*-dimensional **bar-joint framework** is a pair [math](G,p)[/math], where *G* is a graph and *p* is a realization of *G*.

- Two frameworks [math](G,p_1),(G,p_2)[/math] are
**equivalent**if for*any edge*[math] uv \in E [/math] the distances of the endpoints are the same, i.e. [math]\| p_1(u)-p_1(v) \| = \| p_2(u)-p_2(v) \|[/math]. - Two frameworks [math](G,p_1),(G,p_2)[/math] are
**congruent**if for*any two nodes*[math] u,v[/math] the distances are the same, i.e. [math]\| p_1(u)-p_1(v)\| = \| p_2(u)-p_2(v)\|[/math]. - A framework
*(G,p)*is**globally rigid**if every equivalent framework is congruent. - A framework
*(G,p)*is**rigid**if there is an [math]\epsilon\gt0[/math] such that every equivalent framework*(G,q)*for which [math]\| p(v)-q(v)\|\lt\epsilon[/math] for every [math]v \in V[/math] is congruent to*(G,p)*. - A framework is
**generic**if the set containing the coordinates of all of its points is algebraically independent over the rationals.

See also ^{[1]} for further definitions.

## Rigid graphs

The graph [math]G=(V,E)[/math] is **rigid** in *d*-dimensional space if every *d*-dimensional generic realization is rigid. It was shown by Whiteley ^{[2]} that this is equivalent to the property that *G* has at least one rigid *d*-dimensional generic realization. The graph *G* is **minimally rigid** if it is rigid, but by deleting any edge we get a non-rigid graph; *G* is **redundantly rigid** if deleting any edge of *G* results in a graph which is rigid.

*The graph on the left is redundantly rigid in 2D, while the graph on the right is not, because the removal of the red or blue edge makes it non-rigid.*

## Globally rigid graphs

The graph [math]G=(V,E)[/math] is **globally rigid** in *d*-dimensional space if every *d*-dimensional generic realization is globally rigid. It was shown by Gortler, Healy, and Thurston ^{[3]} that this follows if *G* has a single globally rigid *d*-dimensional generic realization (previously, this was known only for [math]d \leq 2[/math]).

*This graph is globally rigid in 2D. The second figure is a non-generic realization (the red edges are on the same line), and the third figure is an equivalent realization, which shows that this realization is not globally rigid.*

## References

- ↑ W. Whiteley,
*Rigidity and scene analysis*, in: Handbook of Discrete and Computational Geometry, pdf link - ↑ W. Whiteley,
*Some matroids from discrete applied geometry*, Matroid theory (Seattle, WA, 1995), 171–311, Contemp. Math., 197, Amer. Math. Soc., Providence, RI, 1996, ResearchGate link - ↑ S. J. Gortler, A. D. Healy, D. P. Thurston,
*Characterizing Generic Global Rigidity*, DOI link, arXiv link