Combinatorial Rigidity

7 Rigidity preservation under Henneberg moves (dimension 2)

We show that both Henneberg moves (section 5) preserve injective generic rigidity in the plane (definition 6.8). This is the inductive step in the proof that every Laman graph is generically rigid in the plane (theorem 9.2). That induction is on the number of vertices and starts from \(K_2\) (theorem 6.20). By the reverse decomposition (theorem 5.12), every Laman graph on at least three vertices is obtained, up to isomorphism, from a smaller Laman graph by a move.

Jordán  [ Jor16 ] calls the two moves the \(0\)-extension and the \(1\)-extension. His Lemmas 1.2.2 and 1.2.3 (p. 38) state that in \({\mathbb {R}}^{d}\), if the points involved are in general position, each of these moves raises the rank of the rigidity matrix of a framework by \(d\). He cites Whiteley’s Vertex \(d\)-Addition Lemma 11.1.1 and Edge \(d\)-Split Theorem 11.1.7  [ Whi96 ] . In the plane our theorems assume the same general-position conditions. We prove the half of the conclusion that rigidity needs: the kernel of the rigidity map does not grow. By rank–nullity, this means that the rank grows by at least \(2\).

Let \(p\) be an infinitesimally rigid framework of \(G\), and let \(G'\) be obtained from \(G\) by a move with new vertex \(v\). We extend \(p\) to \(G'\) by placing \(v\) at a point \(q\), and we restrict each infinitesimal motion of \(G'\) to the vertices of \(G\). We show that the restriction is an infinitesimal motion of \(G\), and that it determines the velocity of \(v\). It does so when two new edges at \(v\) have linearly independent directions. Then the kernel of the rigidity map of \(G'\) has dimension at most that of \(G\), so the extended framework is again infinitesimally rigid.

For the Type I move at \(a\) and \(b\), every edge of \(G\) is an edge of \(G'\), and we place \(v\) off the line through \(p_a\) and \(p_b\). The Type II move on \(ab\) and \(c\) deletes the edge \(ab\), so the restriction must also satisfy the constraint of \(ab\). As in Whiteley’s proof of his Theorem 11.1.7, we place \(v\) on the line through \(p_a\) and \(p_b\), distinct from both. The new edges \(va\) and \(vb\) then point along this line, and together they imply the constraint of \(ab\). The new edges \(va\) and \(vc\) determine the velocity of \(v\) if \(p_a\), \(p_b\) and \(p_c\) are not collinear. For each move we first prove that the extended framework is infinitesimally rigid for a given point \(q\), and then choose \(q\).

Throughout, frameworks are in \({\mathbb {R}}^{2}\). A framework \(p\) on a finite set \(V\) is infinitesimally rigid for a graph \(G\) on \(V\) when \(\dim \ker R(G, p) \le 3\) (definition 6.5). An infinitesimal motion \(x\), an element of this kernel, gives each vertex \(u\) a velocity \(x_u \in {\mathbb {R}}^{2}\). As in section 5, \(v\) is the new vertex of a move, and the graph that the move produces has vertex set \(V \cup \{ v\} \). Formalization note 5.3 describes how the new vertex is encoded formally.

7.1 The Type I move

To choose a point \(q\) off the line through \(p_a\) and \(p_b\), we need \(p_a \ne p_b\). An injective framework has \(p_a \ne p_b\) when \(a \ne b\), and this is why we work with injective frameworks.

Theorem 7.1 Infinitesimal rigidity under the Type I move
✓

Let \(G\) be a graph on a finite set \(V\), let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{2}\) that is infinitesimally rigid for \(G\), and let \(G'\) be obtained from \(G\) by the Type I move at vertices \(a\) and \(b\), with new vertex \(v\). Let \(q \in {\mathbb {R}}^{2}\) be a point such that \(q - p_a\) and \(q - p_b\) are linearly independent, that is, \(q\), \(p_a\) and \(p_b\) are not collinear. Let \(\hat p\) be the framework on \(V \cup \{ v\} \) that agrees with \(p\) on \(V\) and places \(v\) at \(q\). Then \(\hat p\) is infinitesimally rigid for \(G'\).

Proof ▶

Let \(x\) be an infinitesimal motion of \(G'\) at \(\hat p\), and let \(\rho (x)\) be its restriction to \(V\). Every edge \(uw\) of \(G\) is an edge of \(G'\). The entry of the rigidity map at \(uw\) depends only on the points and the velocities of \(u\) and \(w\) (lemma 6.4). So \(\rho (x)\) is an infinitesimal motion of \(G\) at \(p\), and \(\rho \) is a linear map from \(\ker R(G', \hat p)\) to \(\ker R(G, p)\).

We show that \(\rho \) is injective. Suppose that \(\rho (x) = 0\), so that \(x_u = 0\) for every \(u \in V\). The entries of \(R(G', \hat p)(x)\) at the new edges \(va\) and \(vb\) vanish:

\[ \langle q - p_a,\, x_v - x_a \rangle \; =\; 0 \quad \text{and}\quad \langle q - p_b,\, x_v - x_b \rangle \; =\; 0. \]

Since \(x_a = x_b = 0\), the velocity \(x_v\) is orthogonal to \(q - p_a\) and to \(q - p_b\). These two vectors are linearly independent, so they span \({\mathbb {R}}^{2}\), and hence \(x_v = 0\). So \(x = 0\).

Since \(\rho \) is injective and \(p\) is infinitesimally rigid for \(G\),

\[ \dim \ker R(G', \hat p) \; \le \; \dim \ker R(G, p) \; \le \; 3. \]
Theorem 7.2 Type I preserves injective generic rigidity in dimension 2
✓

Let \(G\) be a graph on a finite set \(V\) that is injectively generically rigid in dimension \(2\), and let \(a \ne b\) be vertices of \(G\). Let \(G'\) be obtained from \(G\) by the Type I move at \(a\) and \(b\). Then \(G'\) is injectively generically rigid in dimension \(2\).

Proof ▶

Let \(p\) be an injective framework on \(V\) in \({\mathbb {R}}^{2}\) that is infinitesimally rigid for \(G\). Since \(p\) is injective and \(a \ne b\), the points \(p_a\) and \(p_b\) are distinct. The line through them and the finitely many points \(p_u\), for \(u \in V\), do not cover \({\mathbb {R}}^{2}\). So we can choose a point \(q\) off this line that is none of the points \(p_u\). Since \(q\) is off the line through \(p_a\) and \(p_b\), the vectors \(q - p_a\) and \(q - p_b\) are linearly independent.

Let \(\hat p\) be the framework that extends \(p\) by placing the new vertex at \(q\). It is infinitesimally rigid for \(G'\) (theorem 7.1). It is injective, since \(p\) is injective and \(q\) is none of the points \(p_u\).

7.2 The Type II move

Here the point \(q\) lies on the line through \(p_a\) and \(p_b\). We choose it first when \(p_a\), \(p_b\) and \(p_c\) are not collinear. We then remove this assumption by moving \(p_c\) slightly, which keeps the framework infinitesimally rigid (section 6.5).

Theorem 7.3 Infinitesimal rigidity under the Type II move
✓

Let \(G\) be a graph on a finite set \(V\), let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{2}\) that is infinitesimally rigid for \(G\), and let \(a, b, c \in V\). Let \(G'\) be obtained from \(G\) by the Type II move on \(ab\) and \(c\), with new vertex \(v\). Let \(q = p_a + \alpha (p_b - p_a)\) for a real number \(\alpha \ne 0, 1\), suppose that \(q - p_a\) and \(q - p_c\) are linearly independent, and let \(\hat p\) be the framework on \(V \cup \{ v\} \) that agrees with \(p\) on \(V\) and places \(v\) at \(q\). Then \(\hat p\) is infinitesimally rigid for \(G'\).

Proof ▶

As in the proof of theorem 7.1, let \(\rho (x)\) be the restriction to \(V\) of an infinitesimal motion \(x\) of \(G'\) at \(\hat p\). We first show that \(\rho (x)\) is an infinitesimal motion of \(G\) at \(p\). Every edge of \(G\) other than \(ab\) is an edge of \(G'\), so \(\rho (x)\) satisfies the constraint of each such edge, as before.

If \(ab\) is an edge of \(G\), the move deletes it, and we recover its constraint from the new edges \(va\) and \(vb\). We have \(q - p_a = \alpha (p_b - p_a)\) and \(q - p_b = (\alpha - 1)(p_b - p_a)\). The entries of \(R(G', \hat p)(x)\) at \(va\) and \(vb\) vanish (lemma 6.4). Dividing them by \(\alpha \) and by \(\alpha - 1\), which are not zero, gives

\[ \langle p_b - p_a,\, x_v - x_a \rangle \; =\; 0 \quad \text{and}\quad \langle p_b - p_a,\, x_v - x_b \rangle \; =\; 0. \]

Subtracting the first equation from the second gives \(\langle p_b - p_a,\, x_a - x_b \rangle = 0\). This is the constraint \(\langle p_a - p_b,\, x_a - x_b \rangle = 0\) of the edge \(ab\), up to sign.

It remains to show that \(\rho \) is injective. If \(\rho (x) = 0\), the entries at the new edges \(va\) and \(vc\) show that \(x_v\) is orthogonal to \(q - p_a\) and to \(q - p_c\). These vectors are linearly independent, so \(x_v = 0\) and \(x = 0\). As in the proof of theorem 7.1, it follows that \(\dim \ker R(G', \hat p) \le \dim \ker R(G, p) \le 3\).

Theorem 7.4 Type II preserves injective generic rigidity, non-collinear case
✓

Let \(G\) be a graph on a finite set \(V\), and let \(p\) be an injective framework on \(V\) in \({\mathbb {R}}^{2}\) that is infinitesimally rigid for \(G\). Let \(a, b, c \in V\) be such that \(p_b - p_a\) and \(p_c - p_a\) are linearly independent, that is, \(p_a\), \(p_b\) and \(p_c\) are not collinear. Let \(G'\) be obtained from \(G\) by the Type II move on \(ab\) and \(c\). Then \(G'\) is injectively generically rigid in dimension \(2\).

Proof ▶

For \(\alpha \in {\mathbb {R}}\), let \(q_\alpha = p_a + \alpha (p_b - p_a)\). Since \(p_b - p_a \ne 0\), different values of \(\alpha \) give different points \(q_\alpha \). So all but finitely many \(\alpha \) satisfy \(\alpha \ne 0, 1\) and \(q_\alpha \ne p_u\) for every \(u \in V\). Choose such an \(\alpha \), and let \(q = q_\alpha \). The vectors \(q - p_a = \alpha (p_b - p_a)\) and \(q - p_c = \alpha (p_b - p_a) - (p_c - p_a)\) are linearly independent, since \(p_b - p_a\) and \(p_c - p_a\) are and \(\alpha \ne 0\).

Let \(\hat p\) be the framework that extends \(p\) by placing the new vertex at \(q\). It is infinitesimally rigid for \(G'\) (theorem 7.3). It is injective, since \(p\) is injective and \(q\) is none of the points \(p_u\).

The placement of the new vertex \(v\) on the line through \(p_a\) and \(p_b\) needs \(p_c\) off this line. If \(p_c\) lies on the line, then all three new edges at \(v\) point along it. Moving \(v\) perpendicular to the line, and no other vertex, is then an infinitesimal motion of \(G'\). This motion is not trivial, since a trivial motion that vanishes at two distinct points vanishes everywhere. Jordán also uses openness, in his proof of Laman’s theorem (Theorem 2.2.1, p. 45), to make the three neighbours of the new vertex of a \(1\)-extension non-collinear.

Theorem 7.5 Type II preserves injective generic rigidity in dimension 2
✓

Let \(G\) be a graph on a finite set \(V\) that is injectively generically rigid in dimension \(2\), and let \(a\), \(b\) and \(c\) be distinct vertices of \(G\). Let \(G'\) be obtained from \(G\) by the Type II move on \(ab\) and \(c\). Then \(G'\) is injectively generically rigid in dimension \(2\).

Proof ▶

Let \(p\) be an injective framework on \(V\) in \({\mathbb {R}}^{2}\) that is infinitesimally rigid for \(G\). If \(p_b - p_a\) and \(p_c - p_a\) are linearly independent, then theorem 7.4 applies to \(p\).

Otherwise, since \(p_b \ne p_a\) (as \(p\) is injective and \(a \ne b\)), we have \(p_c - p_a = \delta (p_b - p_a)\) for some \(\delta \in {\mathbb {R}}\). Choose a vector \(w \in {\mathbb {R}}^{2}\) such that \(w\) and \(p_b - p_a\) are linearly independent. For \(t \in {\mathbb {R}}\), let \(p^t\) be the framework that agrees with \(p\) except at \(c\), where \(p^t_c = p_c + t w\). The map \(t \mapsto p^t\) is continuous, and \(p^0 = p\). Infinitesimal rigidity is an open condition on the framework (lemma 6.17). So is injectivity, since \(V\) is finite. Hence \(p^t\) is injective and infinitesimally rigid for \(G\) for every \(t\) close enough to \(0\).

Since \(c\) is neither \(a\) nor \(b\), the points of \(a\) and \(b\) do not move, and

\[ p^t_b - p^t_a \; =\; p_b - p_a, \qquad p^t_c - p^t_a \; =\; \delta (p_b - p_a) + t w. \]

For \(t \ne 0\) these two vectors are linearly independent, because \(w\) and \(p_b - p_a\) are. Choose such a \(t \ne 0\) close enough to \(0\), and apply theorem 7.4 to \(p^t\).