TOPICS
Search

Universal Rigidity

Universal rigidity is the property of a graph framework that its edge lengths determine all pairwise vertex distances even when realizations in higher dimensions are allowed. More precisely, a framework (G,p) with p:V(G)->R^d is universally rigid if every placement q:V(G)->R^D, D>=d, having the same lengths on the edges has the same distances for all pairs of vertices (Gortler and Thurston 2014).

A graph is d-universally rigid when every generic framework in R^d has this property. Generic means that all vertex coordinates are algebraically independent over Q. This is stronger than requiring a single universally rigid realization.

Gabsdil et al. (2026) prove that 1-universally rigid graphs exist with arbitrarily large girth. They also prove that G(n,p) is 1-universally rigid with high probability when p>=Clnnlnlnn/n for a sufficiently large absolute constant C. The existence theorem for large girth is nonconstructive. Gabsdil et al. (2026) credit ChatGPT with optimizing the computation giving the random-graph threshold and supplying a symbolic proof of an auxiliary lemma.

See also

Generically Globally Rigid, Graph

Explore with Wolfram|Alpha

References

Gabsdil, O.; Hirschi, E.; and Portier, J. "On Sparse Universally Rigid Graphs in R." 30 Oct 2026. https://arxiv.org/abs/2610.41581v1.Gortler, S. J. and Thurston, D. P. "Characterizing the Universal Rigidity of Generic Frameworks." Discrete Comput. Geom. 51, 1017-1036, 2014. https://doi.org/10.1007/s00454-014-9590-9.

Cite this as:

Weisstein, Eric W. "Universal Rigidity." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/UniversalRigidity.html

Subject classifications