Rigidity matroid

Last updated November 25, 2023

In the mathematics of structural rigidity, a rigidity matroid is a matroid that describes the number of degrees of freedom of an undirected graph with rigid edges of fixed lengths, embedded into Euclidean space. 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]

Definition

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. From a framework with n vertices and m edges, one can define a matrix with m rows and nd columns, an expanded version of the incidence matrix of the graph called the rigidity matrix. 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.^[1]^[3]

The rigidity matroid of the given framework is a linear matroid that has as its elements the edges of the graph. A set of edges is independent, in the matroid, if it corresponds to a set of rows of the rigidity matrix that is linearly independent. 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]

Statics

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. Every stress is an equilibrium load, a load that does not impose any translational force on the whole system (the sum of its force vectors is zero) nor any rotational force. 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. Thus, a set of edges forms an independent set in the rigidity matroid if and only if it has no self-stress.^[3]

The vector space of all possible loads, on a system of n vertices, has dimension dn, among which the equilibrium loads form a subspace of dimension $dn-{\binom {d+1}{2}}$ . An independent set in the rigidity matroid has a system of equilibrium loads whose dimension equals the cardinality of the set, so the maximum rank that any set in the matroid can have is $dn-{\binom {d+1}{2}}$ . If a set has this rank, it follows that its set of stresses is the same as the space of equilibrium loads. 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]

Kinematics

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 $(v,i)$ where $v$ is a vertex of the framework and $i$ is the index of one of the Cartesian coordinates of $d$ -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. Thus, the family of gradients of (infinitesimally) rigid motions is given by the nullspace of the rigidity matrix.^[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.^[2]

A rigid motion of the framework is a motion such that, at each point in time, the framework is congruent to its original configuration. 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 ${\binom {d+1}{2}}$ , which must always be a subspace of the nullspace of the rigidity matrix. Because the nullspace always has at least this dimension, the rigidity matroid can have rank at most $dn-{\binom {d+1}{2}}$ , and when it does have this rank the only motions that preserve the lengths of the edges of the framework are the rigid motions. In this case the framework is said to be first-order (or infinitesimally) rigid.^[1]^[3] More generally, an edge $e$ belongs to the matroid closure operation of a set $S$ if and only if there does not exist a continuous motion of the framework that changes the length of $e$ but leaves the lengths of the edges in $S$ unchanged.^[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]

Unique realization

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.^[4]

Bruce Hendrickson defined a graph to be redundantly rigid if it remains rigid after removing any one of its edges. In matroidal terms, this means that the rigidity matroid has the full rank $dn-{\binom {d+1}{2}}$ and that the matroid does not have any coloops. Hendrickson proved that every uniquely realizable framework (with generic edge lengths) is either a complete graph or a $(d+1)$ -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.^[7] However, Henrickson's conjecture is false for three or more dimensions.^[8] For frameworks that are not generic, it is NP-hard to determine whether a given framework is uniquely realizable.^[9]

Relation to sparsity

Streinu & Theran (2009) define a graph as being $(k,l)$ -sparse if every nonempty subgraph with $n$ vertices has at most $kn-l$ edges, and $(k,l)$ -tight if it is $(k,l)$ -sparse and has exactly $kn-l$ edges.^[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 $(d,{\binom {d+1}{2}})$ -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 $(d,{\binom {d+1}{2}})$ -tight graph. For instance, in one dimension, the independent sets form the edge sets of forests, (1,1)-sparse graphs, and the independent rigid sets form the edge sets of trees, (1,1)-tight graphs. In this case the rigidity matroid of a framework is the same as the graphic matroid of the corresponding graph.^[2]

In two dimensions, Laman (1970) showed that the same characterization is true: the independent sets form the edge sets of (2,3)-sparse graphs and the independent rigid sets form the edge sets of (2,3)-tight graphs.^[11] Based on this work the (2,3)-tight graphs (the graphs of minimally rigid generic frameworks in two dimensions) have come to be known as Laman graphs. The family of Laman graphs on a fixed set of $n$ vertices forms the set of bases of the rigidity matroid of a complete graph, and more generally for every graph $G$ that forms a rigid framework in two dimensions, the spanning Laman subgraphs of $G$ are the bases of the rigidity matroid of $G$ .

However, in higher dimensions not every $(d,{\binom {d+1}{2}})$ -tight graph is minimally rigid, and characterizing the minimally rigid graphs (the bases of the rigidity matroid of the complete graph) is an important open problem.^[12]

Related Research Articles

The classical mathematical puzzle known as the three utilities problem or sometimes water, gas and electricity asks for non-crossing connections to be drawn between three houses and three utility companies in the plane. When posing it in the early 20th century, Henry Dudeney wrote that it was already an old problem. It is an impossible puzzle: it is not possible to connect all nine lines without crossing. Versions of the problem on nonplanar surfaces such as a torus or Möbius strip, or that allow connections to pass through other houses or utilities, can be solved.

In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its even-degree subgraphs.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In combinatorics, an abstract simplicial complex (ASC), often called an abstract complex or just a complex, is a family of sets that is closed under taking subsets, i.e., every subset of a set in the family is also in the family. It is a purely combinatorial description of the geometric notion of a simplicial complex. For example, in a 2-dimensional simplicial complex, the sets in the family are the triangles, their edges, and their vertices.

In the mathematical theory of matroids, a graphic matroid is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is sometimes called a planar matroid ; these are exactly the graphic matroids formed from planar graphs.

<span class="mw-page-title-main">Circuit rank</span> Fewest graph edges whose removal breaks all cycles

In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest. It is equal to the number of independent cycles in the graph. Unlike the corresponding feedback arc set problem for directed graphs, the circuit rank $r$ is easily computed using the formula

In the mathematical discipline of graph theory, a wheel graph is a graph formed by connecting a single universal vertex to all vertices of a cycle. A wheel graph with $n$ vertices can also be defined as the 1-skeleton of an ( $n - 1$ )-gonal pyramid. Some authors write $W n$ to denote a wheel graph with $n$ vertices ; other authors instead use $W n$ to denote a wheel graph with $n + 1$ vertices, which is formed by connecting a single vertex to all vertices of a cycle of length $n$ . The rest of this article uses the former notation.

<span class="mw-page-title-main">Hypercube graph</span> Graphs formed by a hypercubes edges and vertices

In graph theory, the hypercube graph $Q n$ is the graph formed from the vertices and edges of an $n$ -dimensional hypercube. For instance, the cube graph $Q 3$ is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. $Q n$ has $2 n$ vertices, $2 n - 1 n$ edges, and is a regular graph with $n$ edges touching each vertex.

In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.

<span class="mw-page-title-main">Pseudotriangle</span>

In Euclidean plane geometry, a pseudotriangle (pseudo-triangle) is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A pseudotriangulation (pseudo-triangulations) is a partition of a region of the plane into pseudotriangles, and a pointed pseudotriangulation is a pseudotriangulation in which at each vertex the incident edges span an angle of less than π.

<span class="mw-page-title-main">Pseudoforest</span> Graph with one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

In graph theory, the Laman graphs are a family of sparse graphs describing the minimally rigid systems of rods and joints in the plane. Formally, a Laman graph is a graph on n vertices such that, for all k, every k-vertex subgraph has at most 2k − 3 edges, and such that the whole graph has exactly 2n − 3 edges. Laman graphs are named after Gerard Laman, of the University of Amsterdam, who in 1970 used them to characterize rigid planar structures. This characterization, however, had already been discovered in 1927 by Hilda Geiringer.

Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.

In discrete geometry and mechanics, structural rigidity is a combinatorial theory for predicting the flexibility of ensembles formed by rigid bodies connected by flexible linkages or hinges.

In the mathematical theory of matroids, a matroid representation is a family of vectors whose linear independence relation is the same as that of a given matroid. Matroid representations are analogous to group representations; both types of representation provide abstract algebraic structures with concrete descriptions in terms of linear algebra.

In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by Lawler (1976) as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem.

A sparsity matroid is a mathematical structure that captures how densely a multigraph is populated with edges. To unpack this a little, sparsity is a measure of density of a graph that bounds the number of edges in any subgraph. The property of having a particular matroid as its density measure is invariant under graph isomorphisms and so it is a graph invariant.

Flattenability in some $-dimensional normed vector space is a property of graphs which states that any embedding, or drawing, of the graph in some high dimension can be "flattened" down to live in -dimensions, such that the distances between pairs of points connected by edges are preserved. A graph is -flattenable if every distance constraint system (DCS) with as its constraint graph has a -dimensional framework. Flattenability was first called realizability, but the name was changed to avoid confusion with a graph having some DCS with a -dimensional framework.$

In discrete geometry, geometric rigidity is a theory for determining if a geometric constraint system (GCS) has finitely many $-dimensional solutions, or frameworks, in some metric space. A framework of a GCS is rigid in -dimensions, for a given if it is an isolated solution of the GCS, factoring out the set of trivial motions, or isometric group, of the metric space, e.g. translations and rotations in Euclidean space. In other words, a rigid framework of a GCS has no nearby framework of the GCS that is reachable via a non-trivial continuous motion of that preserves the constraints of the GCS. Structural rigidity is another theory of rigidity that concerns generic frameworks, i.e., frameworks whose rigidity properties are representative of all frameworks with the same constraint graph. Results in geometric rigidity apply to all frameworks; in particular, to non-generic frameworks.$

The Geiringer–Laman theorem gives a combinatorial characterization of generically rigid graphs in $-dimensional Euclidean space, with respect to bar-joint frameworks. This theorem was first proved by Hilda Pollaczek-Geiringer in 1927, and later by Gerard Laman in 1970. An efficient algorithm called the Pebble Game is used to identify this class of graphs. This theorem has been the inspiration for many Geiringer-Laman type results for other types of frameworks with generalized Pebble games.$

References

1 2 3 4 5 6 7 Graver, Jack E. (1991), "Rigidity matroids", SIAM Journal on Discrete Mathematics, 4 (3): 355–368, doi:10.1137/0404032, MR 1105942 .
1 2 3 Whiteley, Walter (1992), "Matroids and rigid structures", Matroid Applications, Encyclopedia of Mathematics and its Applications, vol. 40, Cambridge: Cambridge Univ. Press, pp. 1–53, doi:10.1017/CBO9780511662041.002, MR 1165538 .
1 2 3 4 5 6 7 8 9 Whiteley, Walter (1996), "Some matroids from discrete applied geometry", Matroid theory (Seattle, WA, 1995), Contemporary Mathematics, vol. 197, Providence, RI: American Mathematical Society, pp. 171–311, doi: 10.1090/conm/197/02540 , MR 1411692 .
1 2 Hendrickson, Bruce (1995), "The molecule problem: exploiting structure in global optimization", SIAM Journal on Optimization, 5 (4): 835–857, CiteSeerX 10.1.1.55.2335 , doi:10.1137/0805040, MR 1358807 .
↑ Eren, T.; Goldenberg, O.K.; Whiteley, W.; Yang, Y.R.; Morse, A.S.; Anderson, B.D.O.; Belhumeur, P.N. (2004), "Rigidity, computation, and randomization in network localization", Proc. Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2004), vol. 4, pp. 2673–2684, doi:10.1109/INFCOM.2004.1354686, S2CID 5674760 .
↑ Hendrickson, Bruce (1992), "Conditions for unique graph realizations", SIAM Journal on Computing, 21 (1): 65–84, doi:10.1137/0221008, MR 1148818 .
↑ Jackson, Bill; Jordán, Tibor (2005), "Connected rigidity matroids and unique realizations of graphs", Journal of Combinatorial Theory , Series B, 94 (1): 1–29, doi: 10.1016/j.jctb.2004.11.002 , MR 2130278 .
↑ Connelly, Robert (1991), "On generic global rigidity", Applied Geometry and Discrete Mathematics, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 4, Providence, RI: American Mathematical Society, pp. 147–155, MR 1116345 .
↑ Saxe, J. B. (1979), Embeddability of weighted graphs in k-space is strongly NP-hard, Technical Report, Pittsburgh, PA: Computer Science Department, Carnegie-Mellon University. As cited by Jackson & Jordán (2005).
↑ Streinu, I.; Theran, L. (2009), "Sparse hypergraphs and pebble game algorithms", European Journal of Combinatorics , 30 (8): 1944–1964, arXiv: math/0703921 , doi:10.1016/j.ejc.2008.12.018, S2CID 5477763 .
↑ Laman, G. (1970), "On graphs and the rigidity of plane skeletal structures", J. Engineering Mathematics, 4 (4): 331–340, Bibcode:1970JEnMa...4..331L, doi:10.1007/BF01534980, MR 0269535, S2CID 122631794 .
↑ Jackson, Bill; Jordán, Tibor (2006), "On the rank function of the 3-dimensional rigidity matroid" (PDF), International Journal of Computational Geometry & Applications, 16 (5–6): 415–429, doi:10.1142/S0218195906002117, MR 2269396 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[graver-1] 1 2 3 4 5 6 7 Graver, Jack E. (1991), "Rigidity matroids", SIAM Journal on Discrete Mathematics, 4 (3): 355–368, doi:10.1137/0404032, MR 1105942 .

[w92-2] 1 2 3 Whiteley, Walter (1992), "Matroids and rigid structures", Matroid Applications, Encyclopedia of Mathematics and its Applications, vol. 40, Cambridge: Cambridge Univ. Press, pp. 1–53, doi:10.1017/CBO9780511662041.002, MR 1165538 .

[whiteley-3] 1 2 3 4 5 6 7 8 9 Whiteley, Walter (1996), "Some matroids from discrete applied geometry", Matroid theory (Seattle, WA, 1995), Contemporary Mathematics, vol. 197, Providence, RI: American Mathematical Society, pp. 171–311, doi: 10.1090/conm/197/02540 , MR 1411692 .

[molecule-4] 1 2 Hendrickson, Bruce (1995), "The molecule problem: exploiting structure in global optimization", SIAM Journal on Optimization, 5 (4): 835–857, CiteSeerX 10.1.1.55.2335 , doi:10.1137/0805040, MR 1358807 .

[5] Eren, T.; Goldenberg, O.K.; Whiteley, W.; Yang, Y.R.; Morse, A.S.; Anderson, B.D.O.; Belhumeur, P.N. (2004), "Rigidity, computation, and randomization in network localization", Proc. Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2004), vol. 4, pp. 2673–2684, doi:10.1109/INFCOM.2004.1354686, S2CID 5674760 .

[6] Hendrickson, Bruce (1992), "Conditions for unique graph realizations", SIAM Journal on Computing, 21 (1): 65–84, doi:10.1137/0221008, MR 1148818 .

[7] Jackson, Bill; Jordán, Tibor (2005), "Connected rigidity matroids and unique realizations of graphs", Journal of Combinatorial Theory , Series B, 94 (1): 1–29, doi: 10.1016/j.jctb.2004.11.002 , MR 2130278 .

[8] Connelly, Robert (1991), "On generic global rigidity", Applied Geometry and Discrete Mathematics, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 4, Providence, RI: American Mathematical Society, pp. 147–155, MR 1116345 .

[9] Saxe, J. B. (1979), Embeddability of weighted graphs in k-space is strongly NP-hard, Technical Report, Pittsburgh, PA: Computer Science Department, Carnegie-Mellon University. As cited by Jackson & Jordán (2005).

[10] Streinu, I.; Theran, L. (2009), "Sparse hypergraphs and pebble game algorithms", European Journal of Combinatorics , 30 (8): 1944–1964, arXiv: math/0703921 , doi:10.1016/j.ejc.2008.12.018, S2CID 5477763 .

[11] Laman, G. (1970), "On graphs and the rigidity of plane skeletal structures", J. Engineering Mathematics, 4 (4): 331–340, Bibcode:1970JEnMa...4..331L, doi:10.1007/BF01534980, MR 0269535, S2CID 122631794 .

[12] Jackson, Bill; Jordán, Tibor (2006), "On the rank function of the 3-dimensional rigidity matroid" (PDF), International Journal of Computational Geometry & Applications, 16 (5–6): 415–429, doi:10.1142/S0218195906002117, MR 2269396 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]