Geiringer–Laman theorem
The Geiringer–Laman theorem gives a combinatorial characterization of generically rigid graphs in
This theorem was first proved by Hilda Pollaczek-Geiringer in 1927,[1] and later by Gerard Laman in 1970.
[2] An efficient algorithm called the pebble game is used to identify this class of graphs.
[4] This theorem relies on definitions of genericity that can be found on the structural rigidity page.
satisfying the conditions of the theorem is called a Geiringer-Laman, or minimally rigid, graph.
Graphs satisfying the second condition form the independent sets of a sparsity matroid, and are called
The direction of the theorem which states that a generically rigid graph is
-tight is not necessarily generically minimally rigid, i.e., the converse of the Maxwell Direction is not true.
The red velocity vectors depict a non-trivial infinitesimal flex.
Removing the red edge in (a) yields a generically minimally rigid spanning graph.
Adding the dashed red edge in (b) makes the graph generically minimally rigid.
The equivalence of the first and third statements was first proved by Crapo via the Geiringer-Laman theorem,[6] and later by Tay via a more direct approach.
[2] Furthermore, the details of the proofs below are based on lecture notes found here [8] Consider a bar-joint system
In particular, we can prove structural properties about the rigidity matrix of a generic framework.
These results were first proved by Asimow and Roth,[9][10] see Combinatorial characterizations of generically rigid graphs.
Note that in Step 1.4 the framework must be generic with respect to infinitesimal rigidity.
Step 2 is the Maxwell Direction of the proof, which follows from simple counting arguments on the rigidity matrix.
Step 3 shows that generically minimally rigid graphs are exactly the graphs that can be constructed starting from a single edge using two simple operations, which are defined below.
Step 4 shows that graphs with this type of construction are generically infinitesimally rigid.
First, we show that generic frameworks with respect to infinitesimal rigidity form an open and dense set in
does not have max rank, then it has a set of dependent rows corresponding to a subset of edges
Note that the kernel of the rigidity matrix is the space of infinitesimal motions of a framework, which has dimension
We now set up to apply the implicit function theorem.
The Maxwell Direction of the Geiringer-Laman theorem follows from a simple counting argument on the rigidity matrix.
Now we begin the proof of the other direction of the Geiringer-Laman theorem by first showing that a generically minimally rigid graph has a Henneberg construction.
A generically minimally rigid graph has no vertex with degree
A graph with a Henneberg construction is generically minimally rigid.
To complete the proof of the Geringer-Laman theorem, we show that if a graph has a Henneberg construction then it is generically infinitesimmaly rigid.
is equivalent to adding rows corresponding to the equations
form a basis for the trivial infinitesimal motions, the first three terms in the summation are
