Rigidity matroid
In a rigidity matroid for a graph with n vertices in d-dimensional space, a set of edges that defines a subgraph with k degrees of freedom has matroid rank dn − k. A set of edges is independent if and only if, for every edge in the set, removing the edge would increase the number of degrees of freedom of the remaining subgraph.
[1][2][3] A framework is an undirected graph, embedded into d-dimensional Euclidean space by providing a d-tuple of Cartesian coordinates for each vertex of the graph.
In this matrix, the entry in row e and column (v,i) is zero if v is not an endpoint of edge e. If, on the other hand, edge e has vertices u and v as endpoints, then the value of the entry is the difference between the ith coordinates of v and u.
A framework is called generic if the coordinates of its vertices are algebraically independent real numbers.
Any two generic frameworks on the same graph G determine the same rigidity matroid, regardless of their specific coordinates.
This is the (d-dimensional) rigidity matroid of G.[1][3] A load on a framework is a system of forces on the vertices (represented as vectors).
A stress is a special case of a load, in which equal and opposite forces are applied to the two endpoints of each edge (which may be imagined as a spring) and the forces formed in this way are added at each vertex.
A linear dependence among the rows of the rigidity matrix may be represented as a self-stress, an assignment of equal and opposite forces to the endpoints of each edge that is not identically zero but that adds to zero at every vertex.
Alternatively and equivalently, in this case every equilibrium load on the framework may be resolved by a stress that generates an equal and opposite set of forces, and the framework is said to be statically rigid.
[3] If the vertices of a framework are in a motion, then that motion may be described over small scales of distance by its gradient, a vector for each vertex specifying its speed and direction.
The gradient describes a linearized approximation to the actual motion of the points, in which each point moves at constant velocity in a straight line.
The gradient may be described as a row vector that has one real number coordinate for each pair
-dimensional space; that is, the dimension of the gradient is the same as the width of the rigidity matrix.
[1][3] If the edges of the framework are assumed to be rigid bars that can neither expand nor contract (but can freely rotate) then any motion respecting this rigidity must preserve the lengths of the edges: the derivative of length, as a function of the time over which the motion occurs, must remain zero.
This condition may be expressed in linear algebra as a constraint that the gradient vector of the motion of the vertices must have zero inner product with the row of the rigidity matrix that represents the given edge.
[1][3] For frameworks that are not in generic position, it is possible that some infinitesimally rigid motions (vectors in the nullspace of the rigidity matrix) are not the gradients of any continuous motion, but this cannot happen for generic frameworks.
Rigid motions include translations and rotations of Euclidean space; the gradients of rigid motions form a linear space having the translations and rotations as bases, of dimension
[1] Although defined in different terms (column vectors versus row vectors, or forces versus motions) static rigidity and first-order rigidity reduce to the same properties of the underlying matrix and therefore coincide with each other.
In two dimensions, the generic rigidity matroid also describes the number of degrees of freedom of a different kind of motion, in which each edge is constrained to stay parallel to its original position rather than being constrained to maintain the same length; however, the equivalence between rigidity and parallel motion breaks down in higher dimensions.
[3] A framework has a unique realization in d-dimensional space if every placement of the same graph with the same edge lengths is congruent to it.
Such a framework must necessarily be rigid, because otherwise there exists a continuous motion bringing it to a non-congruent placement with the same edge lengths, but unique realizability is stronger than rigidity.
For instance, the diamond graph (two triangles sharing an edge) is rigid in two dimensions, but it is not uniquely realizable because it has two different realizations, one in which the triangles are on opposite sides of the shared edge and one in which they are both on the same side.
Uniquely realizable graphs are important in applications that involve reconstruction of shapes from distances, such as triangulation in land surveying,[4] the determination of the positions of the nodes in a wireless sensor network,[5] and the reconstruction of conformations of molecules via nuclear magnetic resonance spectroscopy.
Hendrickson proved that every uniquely realizable framework (with generic edge lengths) is either a complete graph or a
-vertex-connected, redundantly rigid graph, and he conjectured that this is an exact characterization of the uniquely realizable frameworks.
[6] The conjecture is true for one and two dimensions; in the one-dimensional case, for instance, a graph is uniquely realizable if and only if it is connected and bridgeless.
[10] From the consideration of loads and stresses it can be seen that a set of edges that is independent in the rigidity matroid forms a
-sparse graph, for if not there would exist a subgraph whose number of edges would exceed the dimension of its space of equilibrium loads, from which it follows that it would have a self-stress.
By similar reasoning, a set of edges that is both independent and rigid forms a
that forms a rigid framework in two dimensions, the spanning Laman subgraphs of
