Geiringer–Laman Theorem

The Geiringer–Laman theorem gives a combinatorial characterization of generically rigid graphs in $2$-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.

Statement of the theorem

This theorem relies on definitions of genericity that can be found on the structural rigidity page. Let $V(E)$ denote the vertex set of a set of edges $E$.

Geiringer-Laman Theorem. A graph $G=(V,E)$ is generically rigid in $2$-dimensions with respect to bar-joint frameworks if and only if $G$ has a spanning subgraph $G'=(V,E')$ such that

* $, E', =2, V, -3$
* for all subsets $F \subset E'$, $, F, \leq 2, V(F), - 3$.

The spanning subgraph $G'$ 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 $(2,3)$-sparse. A graph satisfying both conditions is also called a $(2,3)$-tight graph. The direction of the theorem which states that a generically rigid graph is $(2,3)$-tight is called the Maxwell direction, because James Clerk Maxwell gave an analogous necessary condition of $\textstyle\big(d, \big)$-sparsity for a graph to be independent in the $d$-dimensional generic rigidity matroid. The other direction of the theorem is the more difficult direction to prove. For dimensions $d \geq 3$, a graph that is $\textstyle\big(d, \big)$-tight is not necessarily generically minimally rigid, i.e., the converse of the Maxwell Direction is not true.

Example. Consider the graphs in Figure 1. The graph in (c) is generically minimally rigid, but it is not infinitesimally rigid. 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.

Theorem. Let $G$ be a graph. The following statements are equivalent:

* $G$ is a generically minimally rigid;
* $G$ is $(2,3)$-tight; and
* $G$ contains three edge-disjoint spanning trees $T_1,T_2,$ and $T_3$ such that (i) each vertex of $G$ is contained in exactly two of these spanning trees and (ii) distinct subtrees of these spanning trees do not have the same vertex set.

The equivalence of the first and second statements is the Geiringer-Laman theorem. The equivalence of the first and third statements was first proved by Crapo via the Geiringer-Laman theorem, and later by Tay via a more direct approach.

Outline of proof

The proof of the Geiringer-Laman theorem given below is based on Laman's proof. Furthermore, the details of the proofs below are based on lecture notes found here

Consider a bar-joint system $(G=(V,E),\delta)$ and a framework $(G,p)$ of this system, where $p:V \rightarrow \mathbb^$ is a map that places the vertices of $G$ in the plane such that the distance constraints $\delta$ are satisfied. For convenience, we refer to $p$ as a framework of $G$. The proof of the Geiringer-Laman theorem follows the outline below.

# A graph $G$ is generically rigid if and only if it is generically infinitesimally rigid.
## Infinitesimal rigidity is a generic property of graphs.
## Rigidity is a generic property of graphs.
## If a framework $(G,p)$ is infinitesimally rigid, then it is rigid.
## If a framework $(G,p)$ is generic with respect to infinitesimally rigidity and rigid, then it is infinitesimally rigid.
# If a graph $G$ has a generic infinitesimally rigid framework, then $G$ is a Geiringer-Laman graph.
# A graph $G$ is a Geiringer-Laman graph if and only if $G$ has a Henneberg construction.
# If a graph $G$ has a Henneberg construction, then $G$ has a generic infinitesimally rigid framework.

Step 1 sets up the generic setting of rigidity so that we can focus on generic infinitesimal rigidity rather than generic rigidity. This is an easier approach, because infinitesimal rigidity involves a system of linear equations, rather than quadratic in the case of regular rigidity. In particular, we can prove structural properties about the rigidity matrix of a generic framework. These results were first proved by Asimow and Roth, see Combinatorial characterizations of generically rigid graphs. Note that in Step 1.4 the framework must be generic with respect to infinitesimal rigidity. In particular, a framework $(G,p)$ that is rigid and generic with respect to rigidity is not necessarily infinitesimally rigid. 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. Finally, once Step 1 is proved, Steps 2-3 prove the Geiringer-Laman theorem.

Equivalence of generic rigidity and generic infinitesimal rigidity

Let $G=(V,E)$ be a graph. First, we show that generic frameworks with respect to infinitesimal rigidity form an open and dense set in $\mathbb^$. One necessary and sufficient condition for a framework $p$ of $G$ to be infinitesimally rigid is for its rigidity matrix $R(p)$ to have max rank over all frameworks of $G$.

Proposition 1. For any framework $p$ of $G$ and any neighborhood $N(p)$, there exists a framework $q$ in $N(p)$ such that the rigidity matrix $R(q)$ has max rank.

''Proof.'' If the rigidity matrix $R(p)$ does not have max rank, then it has a set of dependent rows corresponding to a subset of edges $E' \subset E$ such that for some other rigidity matrix $R(q)$, the rows corresponding to $E'$ are independent. Let $\mathcal_$ be the set of frameworks such that the rows corresponding to $E'$ in their rigidity matrices are dependent. In other words, $\mathcal_$ is the set of frameworks $p$ such that the minor of the rows corresponding to $E'$ in $R(p)$ is $0$. Hence, $\mathcal_$ is a curve in $\mathbb^$, because a minor is a polynomial in the entries of a matrix. Let $\mathcal$ be the union of these curves over all subsets of edges of $E$. If a framework $R(p)$ does not have max rank for some framework $p$, then $p$ is contained in $\mathcal$. Finally, since $\mathcal$ is a finite set of curves, the proposition is proved.

Proposition 2. Infinitesimal rigidity is a generic property of graphs.

''Proof.'' We show that if one generic framework with respect to infinitesimal rigidity is infinitesimally rigid, then all generic frameworks are infinitesimally rigid. If a framework $p$ of a graph $G$ is infinitesimally rigid, then $R(p)$ has max rank. Note that the kernel of the rigidity matrix is the space of infinitesimal motions of a framework, which has dimension $$ for infinitesimally rigid frameworks. Hence, by the Rank–nullity theorem, if one generic framework is infinitesimally rigid then all generic frameworks are infinitesimal rigidity have rigid.

Proposition 3. If a framework $p$ of a graph $G$ is infinitesimally rigid, then it is rigid.

''Proof.'' Assume that $p$ is not rigid, so there exists a framework $q$ in a neighborhood $N(p)$ such that $\rho (p) = \rho(q)$ and $q$ is cannot be obtained via a trivial motion of $p$. Since $q$ is in $N(p)$, there exists a $\delta>0$ and $\, h\, < \delta$ such that $q = p + h$. Applying some algebra yields:

$\begin \rho (p)_ - \rho (q)_ &= \, p_i - p_j\, ^2 - \, q_i - q_j\, ^2 \\ &= \, h_i - h_j\, ^2 - 2(p_i - p_j)(h_i - h_j) \\ &= 0. \end$

Hence,

$\frac = 2(p_i - p_j) \frac = 0.$

We can choose a sequence of $\delta_n$ such that $\delta_ < \delta_n$ and $\lim_ \delta_n = 0$. This causes $\lim_ \, h_n\, = 0$ and $\lim_ \frac = (h^_i - h^_j)$. Hence,

$\begin 2(p_i - p_j)( h^_i - h^_j) &= \lim_ 2(p_i - p_j) \frac \\ &= \lim_ \frac \\ &=0. \end$

The first and last expressions in the equations above state that $h^$ is an infinitesimal motion of the framework $p$. Since there is no trivial motion between $p$ and $q$, $h^$ is not a trivial infinitesimal motion. Thus, $p$ is not infinitesimally rigid.

Proposition 4. If a framework $p$ of a graph $G$ is rigid and generic with respect to infinitesimal rigidity, then $p$ is infinitesimally rigid.

''Proof.'' This follows from the implicit function theorem. First, we will factor out all trivial motions of $p$. Since $R(p)$ has max rank, no $3$ points of $p$ are colinear. Hence, we can pin $2$ points of $p$ to factor out trivial motions: one point at the origin and another along the $x$-axis at a distance from the origin consistent with all constraints. This yields a pinned framework $q$ that lives in $\mathbb^$. This can be done for all frameworks in a neighborhood $N(p)$ of $p$ to obtain a neighborhood $N(q)$ of $q$ of pinned frameworks. The set of such frameworks is still a smooth manifold, so the rigidity map and rigidity matrix can be redefined on the new domain. Specifically, the rigidity matrix $R(q)$ of a pinned framework $q$ has $2, V, -3$ columns and rank equal to $R(p)$, where $p$ is the unpinned framework corresponding to $q$. In this pinned setting, a framework is rigid if it is the only nearby solution to the rigidity map.

Now, assume an unpinned framework $p$ is not infinitesimally rigid, so that $rank(R(p)) = k < 2, V, - 3$. Then the $rank(R(q))=k$, where $q$ is the pinned version of $p$. We now set up to apply the implicit function theorem. Our continuously differentiable function is the rigidity map $\rho:\mathbb^ \rightarrow \mathbb^$. The Jacobian of $\rho$ is the rigidity matrix. Consider the subset of edges $E' \subset E$ corresponding to the $k$ independent rows of $R(q)$, yielding the submatrix $R(q)_$. We can find $k$ independent columns of $R(q)_$. Denote the entries in these columns by the vectors $y=y_1,\dots,y_k$. Denote the entries of the remaining columns by the vectors $x=x_1,\dots,x_$. The $k \times k$ submatrix of $R(q)_$ induced the $y_1,\dots,y_k$ is invertible, so by the implicit function theorem, there exists a continuously differentiable function $g$ such that $y=g(x)$ and $\rho(x,y)_ = \rho(q)_$. Hence, the framework $q_)$ of the subgraph $G'=(V,E')$ is not rigid, and since the rows of $R(q)_$ span the row space of $R(q)$, $q$ is also not rigid. This contradicts our assumption, so $p$ is infinitesimally rigid.

Proposition 5. Rigidity is a generic property of graphs.

''Proof.'' Let $p$ be a rigid framework of $G$ that is generic with respect to rigidity. By definition, there is a neighborhood of rigid frameworks $N(p)$ of $p$. By Proposition 1, there is a framework $q$ in $N(p)$ that is generic with respect to infinitesimal rigidity, so by Proposition 4, $q$ is infinitesimally rigid. Hence, by Proposition 2, all frameworks that are generic with respect to infinitesimal rigidity are infinitesimally rigid, and by Proposition 3 they are also rigid. Finally, every neighborhood $N(p')$ of every framework $p'$ that is generic with respect to rigidity contains a framework $q'$ that is generic with respect to infinitesimal rigidity, by Proposition 1. Thus, if $p$ is rigid then $p'$ is rigid.

Theorem 1. A graph $G$ is generically rigid if and only if it is generically infinitesimally rigid.

''Proof.'' The proof follows a similar argument to the proof of Proposition 5. If $G$ is generically rigid, then there exists a generic framework $p$ with respect to rigidity that is rigid by definition. By Propositions 1 and 4, in any neighborhood of $p$ there is a framework $q$ that is generic with respect to infinitesimal rigidity and infinitesimally rigid. Hence, by Proposition 2, $G$ is generically infinitesimally rigid.

For the other direction, assume to the contrary that $G$ is generically infinitesimally rigid, but not generically rigid. Then there exists a generic framework $p$ with respect to rigidity that is not rigid by definition. By Proposition 1, in any neighborhood of $p$ there is a framework $q$ that is generic with respect to infinitesimal rigidity. By assumption $q$ is infinitesimally rigid, and by Proposition 3, $q$ is also rigid. Thus, $p$ must be rigid and, by Proposition 5, all frameworks that are generic with respect to rigidity are rigid. This contradicts our assumption that $G$ is not generically rigid.

Maxwell direction

The Maxwell Direction of the Geiringer-Laman theorem follows from a simple counting argument on the rigidity matrix.

Maxwell Direction. If a graph $G$ has a generic infinitesimally rigid framework, then $G$ has a Geiringer-Laman subgraph.

''Proof.'' Let $p$ be a generic infinitesimally rigid framework of $G$. By definition, $R(p)$ has max rank, i.e., $rank(R(p))=2, V, -3$. In particular, $R(p)$ has $2, V, -3$ independent rows. Each row of $R(p)$ corresponds to an edge of $G$, so the submatrix $R(p)_$ with just the independent rows corresponds to a subgraph $G'=(V,E')$ such that $, E', = 2, V, -3$. Furthermore, any subgraph $H=(V',F)$ of $G'$ corresponds to a submatrix $R(p)_H$ of $R(p)_$. Since the rows of $R(p)_$ are independent, so are the rows of $R(p)_H$. Hence, $rank(R(p)_H) = , F,$, which clearly satisfies $, F, \leq 2, V(F), - 3$.

Equivalence of generic infinitesimal rigidity and Henneberg constructions

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 Henneberg graph $G$ has the following recursive definition:

# $G$ is a single edge or
# $G$ can be obtained from a Henneberg graph $G'$ via one of the following operations
## add a vertex to $G'$ and connect it to $2$ distinct vertices of $G'$
## For an edge $(u,v)$ and a vertex $w$ of $G'$, add a vertex to $G'$, connect it to $u,v,$ and $w$, and then remove $(u,v)$.

The two operations above are called a $0$-extension and a $1$-extension respectively.

The following propositions are proved in:

Proposition 6. A generically minimally rigid graph has no vertex with degree $1$ and at least one vertex with degree less than $4$

Proposition 7. If $G$ is a generically minimally rigid graph with a vertex $v$ of degree $3$, connected to vertices $u_1,u_2,$ and $u_3$, then for at least one pair of the neighbors of $v$, without loss of generality say $(u_1,u_2)$, there is no subgraph $G'=(V',E')$ of $G$ that contains $u_1$ and $u_2$ and satisfies $, E', =2, V', -3$.

Theorem 2. A generically minimally rigid graph $G$ with at least $2$ vertices has a Henneberg construction.

''Proof.'' We proceed by induction on the number of vertices $, V,$. The base case of $, V, =2$ is the base case Henneberg graph. Assume $G=(V,E)$ has a Henneberg construction when $, V, =k$ and we will prove it for $, V, =k+1$. When $, V, =k+1$, $G$ has a vertex $v$ with degree $2$ or $3$, by Proposition 6.

Case 1: $v$ has degree 2.

Let $G'=(V',E')$ be the subgraph of $G$ obtained by removing $v$, so $, V', =, V, -1$ and $, E', =, E, -2$. Since $G$ is minimally rigid, we have

$, E', =, E, -2=2, V, -3-2=2, V', -3.$

Furthermore, any subgraph $H=(V' ',F)$ of $G'$ is also a subgraph of $G$, so $, F, \leq 2, V' ', - 4,$ by assumption. Hence, $G'$ is minimally rigid, by the Maxwell Direction, and $G'$ has a Henneberg construction by the inductive hypothesis. Now simply notice that $G$ can be obtained from $G'$ via a $0$-extension.

Case 2: $v$ has degree 3.

Let the edges incident to $v$ be $(v,u_1),(v,u_2),$ and $(v,u_3)$. By Proposition 7, for one pair of the neighbors of $v$, without loss of generality say $(u_1,u_2)$, there is no subgraph $H=(U,F)$ of $G$ that contains $u_1$ and $u_2$ and satisfies $, F, =2, U, -3$. Note that $(u_1,u_2)$ cannot be an edge, or else the subgraph on just that edge satisfies the previous equality. Consider the graph $G'=(V',E')$ obtained by removing $v$ from $G$ and adding the edge $(u_1,u_2)$. We have

$, E', =, E, -3+1=2, V, -3 - 2 = 2, V', - 3$.

Furthermore, as with Case 1, any subgraph of $G'$ that does not contain $(u_1,u_2)$ satisfies the second condition for minimal rigidity by assumption. For a subgraph of $G' '=(V' ',E' ')$ that does contain $(u_1,u_2)$, removing this edge yields a subgraph $G' ' '=(V' ' ',E' ' ')$ of $G$. By Proposition 7, $, E' ' ', \leq 2, V' ' ', - 2$, so $, E' ', \leq 2, V' ', - 3$. Hence, $G'$ is minimally rigid, and $G'$ has a Henneberg construction by the inductive hypothesis. Finally, notice that $G$ can be obtained from $G'$ via a $1$-extension.

Combining Cases 1 and 2 proves the theorem by induction.

It is also easy to the converse of Theorem 2 by induction.

Proposition 8. A graph with a Henneberg construction is generically minimally rigid.

Henneberg constructible graphs are generically infinitesimally 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. The proof of this result relies on the following proposition from.

Proposition 9. If $p_1,p_2,p_3$ are three non-colinear $2$-dimensional points and $u_1,u_2,u_3$ are three $2$-dimensional vectors, then the following statements are equivalent:

* $(p_i - p_j) \cdot (u_i - u_j)=0$ for all $i,j \in \$
* The function

$f(p)= \begin p-p_1 & (p - p_1) \cdot u_1 \\ p-p_2 & (p - p_2) \cdot u_2 \\ p-p_3 & (p - p_3) \cdot u_3 \end$

vanishes at every point $p$.

Theorem 3. If a graph $G$ with at least $3$ vertices has a Henneberg construction, then $G$ is generically infinitesimally rigid.

''Proof.'' We proceed by induction on the number of vertices $, V,$. The graph in the base case $, V, =3$ is a triangle, which is generically infinitesimally rigid. Assume that when $, V, =k$ $G$ is generically infinitesimally rigid and we will prove it for $k+1$. For $, V, =k+1$, consider the graph $G'=(V',E')$ that $G$ was obtained from via $0$- or $1$-extension. By the inductive hypothesis, $G'$ is generically infinitesimally rigid. Hence, $G'$ has a generic infinitesimally rigid framework $p' \in \mathbb^$ such that the kernel of $R(p')$ has dimension $3$. Let $v$ be the vertex added to $G'$ to obtain $G$. We must choose a placement $p_v$ in $2$-dimensions such that $p=p' \cup p_v$ is a generic infinitesimally rigid framework of $G$.

Case 1: $G$ is obtained from $G'$ via a $0$-extension.

Choosing such a placement for $p_v$ is equivalent to adding rows corresponding to the equations

$\begin & (p_v - p_u) \cdot (q_v - q_u) = 0\\ & (p_v - p_w) \cdot (q_v - q_w) = 0 \end$

to the rigidity matrix $R(p')$, where $u$ and $w$ are the neighbors of $v$ after the $0$-extension and $q_v$ is the velocity assigned to $p_v$ by an infinitesimal motion. Our goal is to choose $p_v$ such the dimension of the space of infinitesimal motions of $R(p)$ is the same as that of $R(p')$. We can choose $p_v$ such that it is not colinear to $p_u$ and $p_w$, which ensures that there is only one solution to these equations. Hence, the kernel of $R(p)$ has dimension $3$, so $p$ is a generic infinitesimally rigid framework of $G$.

Case 2: $G$ is obtained from $G'$ via a $1$-extension.

Let the neighbors of $v$ after the $1$-extension be the edges $(v,u_1),(v,u_2)$, and $(v,u_3)$, and let $(u_1,u_2)$ be the edge that was removed. Removing the edge $(u_1,u_2)$ from $G'$ yields the subgraph $G' '$. Let $p' '$ be the framework of $G' '$ that is equivalent to $p'$, except for the removed edge. The rigidity matrix $R(p' ')$ can be obtained from $R(p')$ by removing the row corresponding to the removed edge. By Proposition 8, $G'$ is generically minimally rigid, so the rows of $R(p')$ are independent. Hence, the rows of $R(p' ')$ are independent and its kernel has dimension $4$. Let $\lambda_1,\lambda_2,\lambda_3,\lambda_4$ be a basis vector for the space of infinitesimal motions of $p' '$ such that $\lambda_1,\lambda_2,\lambda_3$ is a basis for the space of trivial infinitesimal motions. Then, any infinitesimal motion of $p' '$ can be written as a linear combination of these $4$ basis vectors. Choosing a placement for $p_v$ that results in a generic infinitesimally rigid framework of $G$ is equivalent to adding rows corresponding to the equations

$\begin & (p_v - p_) \cdot (q_v - q_) = 0\\ & (p_v - p_) \cdot (q_v - q_) = 0\\ & (p_v - p_) \cdot (q_v - q_) = 0 \end$

to the rigidity matrix $R(p' ')$. Our goal is to choose $p_v$ such the dimension of the space of infinitesimal motions of $R(p)$ is $1$ less than that of $R(p' ')$. After rearranging, these equations have a solution if and only if

$\begin p_v-p_ & (p_v-p_) \cdot q_ \\ p_v-p_ & (p_v-p_) \cdot q_ \\ p_v-p_ & (p_v-p_) \cdot q_ \end =0.$

Note that $q_$ can be written as $\sum_i^4$, for constants $c_1,c_2,c_3,c_4$. Furthermore, we can move the summation outside of the determinant to obtain

$\sum_i^4 c_i \begin p_v-p_ & (p_v-p_) \cdot \lambda_ \\ p_v-p_ & (p_v-p_) \cdot \lambda_ \\ p_v-p_ & (p_v-p_) \cdot \lambda_ \end =0.$

Since $\lambda_1,\lambda_2,\lambda_3$ form a basis for the trivial infinitesimal motions, the first three terms in the summation are $0$, leaving only

$c_4 \begin p_v-p_ & (p_v-p_) \cdot \lambda_ \\ p_v-p_ & (p_v-p_) \cdot \lambda_ \\ p_v-p_ & (p_v-p_) \cdot \lambda_ \end =0.$

Solutions to this equation form a curve in $2$-dimensions. We can choose $p_v$ not along this curve so that $c_4=0$, which ensures that there is only one solution to this equation. Hence, by Proposition 9, the kernel of $R(p)$ has dimension $3$, so $p$ is a generic infinitesimally rigid framework of $G$.

Combining Cases 1 and 2 proves the theorem by induction.

See also

* Laman graph

References

{{DEFAULTSORT:Geiringer-Laman theorem
Theorems in graph theory
Mathematics of rigidity