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
