TOPICS
Search

Rigid Graph


The word "rigid" has two different meaning 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.) Rigidity of a framework (G,p), i.e., a structure with vertex coordinates p and underlying graph G=(V,E) having vertex set V and edge set E, can be thought of in two equivalent ways: infinitesimal rigidity (which considers infinitesimal displacements corresponding to velocity vectors) and static rigidity (which considers forces and loads on the structure).

A framework consisting of bars is said to be (infinitesimally) rigid iff continuous motion of the points of the configuration maintaining the bar constraints comes from a family of motions of all Euclidean space which are distance-preserving. This is equivalent to the condition that there exists an epsilon>0 such that every framework (G,q) which is equivalent to (G,p) and satisfies |p(v)-q(v)|<epsilon for all v in V is congruent to the framework (G,p).

A framework (G=(V,E),p) is infinitesimally rigid iff the rank of its rigidity matrix R(G,p) satisfies

 rank(R(G,p))=2|V|-3,

where |V| is the vertex count (Grasegger 2023).

Call a framework (G,p) a generic realization of G if the rigidity matrix R(G,p) is equal to the rigidity matroid R(G). This occurs when the coordinates of all points p(v) are algebraically independent over the field of rationals Q. A graph (as an abstract object with no explicit embedding) is said to be rigid iff there is a generic realization for which the framework is generically rigid. Similarly, a graph G is said to be (generically) d-rigid if, for almost all (i.e., an open dense set of) configurations of p, the framework (G,p) is rigid in R^d.

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. In general, however, a 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).


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, Rigid Polyhedron, Rigidity Matrix, Rigidity Theorem, Tensegrity, Unit-Distance Graph

Explore with Wolfram|Alpha

References

Albertson, M. and Collins, K. "Symmetry Breaking in Graphs." Electronic J. Combinatorics 3, No. 1, R18, 17 pp., 1996. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i1r18.Asimov, 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.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/record/7457820#.Y7V1Ay-B30o.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 Web Resource. https://mathworld.wolfram.com/RigidGraph.html

Subject classifications