TOPICS
Search

Rigid Graph


The word "rigid" has two different meanings when applied to a graph. Firstly, a rigid graph may refer to a graph having a graph automorphism group containing a single element. In this work, such a graph is instead referred to using the more common term "identity graph" (e.g., Albertson and Collins 1996).

The more common meaning of rigidity considers a graph's resistance to deformation, where graph edges are commonly taken as rigid straight bars or rods that are connected to incident vertices via flexible hinges. (Other edge elements such as cables and struts are sometimes also considered.) A framework (G,p) consists of an underlying graph G=(V,E) and a placement p of its vertices in Euclidean space. Two placements are equivalent when corresponding edges have equal lengths. The framework is rigid iff there exists epsilon>0 such that every equivalent placement q with ||p(v)-q(v)||<epsilon for every v in V is congruent to p. Here congruence requires agreement of all pairwise distances between vertices, not only edge lengths.

Infinitesimal rigidity instead concerns velocity vectors h(v) satisfying (p(u)-p(v))·(h(u)-h(v))=0 on every graph edge uv. A framework is infinitesimally rigid when all such assignments are induced by translations and infinitesimal rotations of the ambient Euclidean space. Infinitesimal rigidity implies rigidity, and the converse holds at generic placements. The converse can fail at nongeneric placements (Asimow and Roth 1978). The equivalent static formulation asks whether equilibrium loads can be resolved by forces along the bars (Crapo and Whiteley 1982). Self-balancing bar forces are described by an equilibrium stress.

For a framework in R^d whose points affinely span R^d, infinitesimal rigidity is equivalent to the matrix rank condition

 rankR(G,p)=d|V|-(d(d+1))/2.

Here R(G,p) is the rigidity matrix and |V| is the vertex count. For a placement spanning the plane, this becomes 2|V|-3.

A realization is generic when all its point coordinates are algebraically independent over Q. A graph is generically d-rigid when its generic realizations in R^d are rigid. This is equivalent to rigidity for an open dense set of placements (Asimow and Roth 1978).

A graph that is not rigid is said to be flexible (Maehara 1992).

RigidFlexibleUtilityGraph

Any embeding of the triangle graph C_3 is rigid, while any embedding of the square graph C_4 is flexible.

A flexible graph cannot have a rigid embedding. However, in general, a rigid graph may have both rigid and flexible embeddings. For example, an embedding of the utility graph K_(3,3) in the plane is rigid unless its six vertices lie on a conic (Bolker and Roth 1980, Maehara 1992), some examples of which are illustrated above.

Cauchy (1813) proved the rigidity theorem, one of the first results in rigidity theory. Although rigidity problems were of immense interest to engineers, intensive mathematical study of these types of problems has occurred only relatively recently (Connelly 1993, Graver et al. 1993).

Deleting edges or vertices gives different optimization problems for generic planar rigidity. Cong et al. (2026) proved that finding the smallest number of edges whose deletion destroys rigidity is NP-hard, while the corresponding vertex-deletion problem is solvable in polynomial time. For generic global rigidity, both unweighted deletion problems are solvable in polynomial time. With positive integer deletion costs, all four problems are NP-hard, even on generically globally rigid inputs. Cong et al. (2026) attribute discovery of the main result to an AI system using GPT-6 Astra.


See also

Braced Polygon, Flexible Graph, Flexible Polyhedron, Framework, Graph Bar, Harborth Graph, Identity Graph, Just Rigid, Laman Graph, Laman's Theorem, Liebmann's Theorem, Pebble Game, Rigid Polyhedron, Rigidity Matrix, Rigidity Theorem, Rigidity Theory, Tensegrity, Unit-Distance Graph

Explore with Wolfram|Alpha

References

Albertson, M. and Collins, K. "Symmetry Breaking in Graphs." Elec. J. Combin. 3, No. 1, R18, 1996. https://doi.org/10.37236/1242.Asimow, L. and Roth, B. "The Rigidity of Graphs." Trans. Amer. Math. Soc. 245, 279-289, 1978.Bolker, E. D. and Roth, B. "When Is a Bipartite Graph a Rigid Framework?" Pacific J. Math. 90, 27-44, 1980.Cauchy, A. L. "Sur les polygones et les polyèdres." XVIe Cahier IX, 87-89, 1813.Cong, Y.; Xu, C.; and Zhao, Y. "Destroying Rigidity in the Plane." 28 Oct 2026. https://arxiv.org/abs/2610.38396.Connelly, R. "Rigidity." Ch. 1.7 in Handbook of Convex Geometry, Vol. A (Ed. P. M. Gruber and J. M. Wills). Amsterdam, Netherlands: North-Holland, pp. 223-271, 1993.Connelly, R. and Guest, S. D. Frameworks, Tensegrities and Symmetry. Cambridge, England: Cambridge University Press, 2022.Coxeter, H. S. M. and Greitzer, S. L. Geometry Revisited. Washington, DC: Math. Assoc. Amer., p. 56, 1967.Crapo, H. and Whiteley, W. "Statics of Frameworks and Motions of Panel Structures, A Projective Geometry Introduction." Structural Topology 6, 43-82, 1982.Croft, H. T.; Falconer, K. J.; and Guy, R. K. "Rigidity of Frameworks." §B14 in Unsolved Problems in Geometry. New York: Springer-Verlag, pp. 63-65, 1991.Dehn, M. "Über die Strakheit knovexer Polyeder." Math. Ann. 77, 466-473, 1916.Goldberg, M. "Unstable Polyhedral Structures." Math. Mag. 51, 165-170, 1978.Grasegger, G. "RigiComp--a Mathematica Package for Computational Rigidity of Graphs." Dec. 19, 2022a. https://zenodo.org/records/7457820.Grasegger, G. "Minimal Counterexamples to Hendrickson's Conjecture on Globally Rigid Graphs." Examples and Counterexamples 3, 100106, 2023.Graver, J.; Servatius, B.; and Servatius, H. Combinatorial Rigidity. Providence, RI: Amer. Math. Soc., 1993.Maehara, H. "Distances in a Rigid Unit-Distance Graph in the Plane." Disc. Appl. Math. 31, 193-200, 1991.Maehara, H. "Distance Graphs in Euclidean Space." Ryukyu Math. J. 5, 33-51, 1992.Roth, B. "Rigid and Flexible Frameworks." Amer. Math. Monthly 88, 6-21, 1981.Sitharam, M.; St. John, A.; and Sidman, J. (Eds.). Handbook of Geometric Constraint Systems Principles. Boca Raton, FL: CRC Press, 2018.

Referenced on Wolfram|Alpha

Rigid Graph

Cite this as:

Weisstein, Eric W. "Rigid Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/RigidGraph.html

Subject classifications