page_title: Rigidity matroid
section_title: Unique realization
hierarchical_section_title: Rigidity matroid / Unique realization
context_page_description: 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.
context_section_description: 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, the determination of the positions of the nodes in a wireless sensor network, and the reconstruction of conformations of molecules via nuclear magnetic resonance spectroscopy.
  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  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 -vertex-connected, redundantly rigid graph, and he conjectured that this is an exact characterization of the uniquely realizable frameworks. 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. However, Henrickson's conjecture is false for three or more dimensions. For frameworks that are not generic, it is NP-hard to determine whether a given framework is uniquely realizable.
caption: The diamond graph, generically rigid but not uniquely realizable