Draft:Structural rigidity

In discrete geometry and combinatorics, structural, or combinatorial, rigidity is a theory for determining if almost all geometric constraint systems (GCSs) with the same constraint graph $G$ have finitely many solutions by analyzing the structure of $G$. A graph with this property is called generically rigid. The focus of structural rigidity is developing methods to identify generically rigid graphs. Some types of GCSs do not admit such structural characterizations of their constraint graphs, and instead rely on geometric rigidity theory to analyze the algebraic systems of these GCSs. Moreover, a constraint graph may be generically rigid, but have a flexible framework. Structural rigidity can only be used to determine the rigidity of representative, i.e., generic, frameworks of graphs.

The Geiringer-Laman theorem gives a combinatorial characterization of generically rigid graphs in $2$-dimensional Euclidean space. Such a characterization in $3$-dimensions, and higher, is an important open problem that goes back to a conjecture posed by James Clerk Maxwell in the mid-1800s that provides necessary but not sufficient conditions for a graph to be generically rigid in any dimension. Structural rigidity has many applications in mechanics, molecular physics, and computer-aided design.

Definitions

The definitions below are with respect to bar-joint frameworks in $d$-dimensional Euclidean space, and will be generalized for other frameworks and metric spaces as needed. Several definitions build off of those given in the geometric rigidity page. Consider a linkage $(G,\delta )$, i.e. a constraint graph $G=(V,E)$ with distance constraints $\delta$ assigned to its edges, and its $d$-dimensional configuration space ${\mathcal {C}}(G,\delta )$, which is an algebraic set of frameworks $(G,p)$ that are solutions to the system of quadratic equations $\|p(u)-p(v)\|^{2}=\delta _{uv},$ for all edges $(u,v)$ of $G$.

Local rigidity. A $d$-dimensional framework $(G,p)$ of a linkage $(G,\delta )$ is locally rigid, or just rigid, in $d$-dimensions if any continuous motion path in the configuration space ${\mathcal {C}}(G,\delta )$ starting from $(G,p)$ is a trivial motion, i.e., a composition of the translations and rotations of the Euclidean group. Equivalently, $(G,p)$ is an isolated solution to the system of equations above, modulo the ${d+1 \choose 2}$ translations and rotations of $d$-dimensional space.

Testing for local rigidity is co-NP hard.

Rigidity map. The rigidity map $\rho :\mathbb {R} ^{d|V|}\rightarrow \mathbb {R} ^{|E|}$ takes a framework $(G,p)$ and outputs the squared-distances $\|p(u)-p(v)\|^{2}$ between all pairs of points that are connected by an edge.

Rigidity matrix. The Jacobian, or derivative, of the rigidity map yields a system of linear equations of the form $(p(u)-p(v))\cdot (p'(v)-p'(u))=0,$ for all edges $(u,v)$ of $G$. The rigidity matrix $R(G,p)$ is an $|E|\times d|V|$ matrix that encodes the information in these equations. Each edge of $G$ corresponds to a row of $R(G,p)$ and each vertex corresponds to $d$ columns of $R(G,p)$. The row corresponding to the edge $(u,v)$ is defined as follows.

${\begin{bmatrix}\,&\dots &{\text{columns for }}u&\dots &{\text{columns for }}v&\dots \\\vdots &\,&\,&\vdots &\,&\,\\{\text{row for }}(u,v)&0\dots 0&p(u)-p(v)&0\dots 0&p(v)-p(u)&0\dots 0\\\vdots &\,&\,&\vdots &\,&\,\end{bmatrix}}$

The rigidity matrix is a fundamental tool for studying generic rigidity. See geometric rigidity for various physical interpretations of the rigidity matrix as a linear transformation. One crucial physical interpretation is that the kernel of the rigidity matrix is the space of infinitesimal motions of a framework.

Infinitesimal rigidity. A framework is infinitesimally rigid if all its infinitesimal motions are trivial.

Infinitesimal rigidity is linearization of the concept of rigidity. If a framework is infinitesimally rigid, then it is rigid. The converse of this statement is false in general, see Figure 1; however, it is true under certain conditions defined now.

File:Generic wrt rig vs inf.jpg

Figure 1. Two frameworks of the same GCS. The top framework is generic with respect to rigidity and rigid, but not infinitesimally rigid as the red infinitesimal motion demonstrates. The bottom framework is generic with respect to infinitesimal rigidity and infinitesimally rigid.

Generic framework with respect to rigidity. A framework $(G,p)$ is generic with respect to rigidity if there exists a neighborhood $N(G,p)$ in the configuration space ${\mathcal {C}}(G,\delta )$ such that $(G,p)$ is rigid if and only if every framework in $N(G,p)$ is rigid.

Generic framework with respect to infinitesimal rigidity. The following definitions of a generic framework $(G,p)$ with respect to infinitesimal rigidity are equivalent:

• there exists a neighborhood $N(G,p)$ in the configuration space ${\mathcal {C}}(G,\delta )$ such that $(G,p)$ is infinitesimally rigid if and only if every framework in $N(G,p)$ is infinitesimally rigid;
• no $n\geq 2$ points of $(G,p)$ lie in any $(n-2)$-dimensional affine subspace;
• the rigidity matrix $R(G,p)$ has maximum rank over all frameworks in the configuration space ${\mathcal {C}}(G,\delta )$; and
• no sub-determinant of $R(G,p)$ is $0$ unless the corresponding rows are identically $0$.

Generically rigid graph. A graph $G$ is generically rigid in $d$-dimensions with respect to (resp. infinitesimal) rigidity if there exists a $d$-dimensional generic framework $(G,p)$ with respect to (resp. infinitesimal) rigidity that is (resp. infinitesimally) rigid in $d$-dimensions.

Another fundamental combinatorial tool for studying generic rigidity is the matroid defined on the rows of the rigidity matrix for a generic framework.

Generic rigidity matroid. The $d$-dimensional rigidity matroid ${\mathcal {M}}_{d}(G,p)$ of a $d$-dimensional framework $(G,p)$ is a matroid on the rows of the rigidity matrix $R(G,p)$. The independent sets of ${\mathcal {M}}(G,p)$ are the sets of rows of $R(G,p)$ that are linearly independent, i.e., no edge length is implied by the other edges in the set. The closure of a set of edges $E$ in ${\mathcal {M}}(G,p)$ is the set of edges whose lengths are implied by $E$. Consider the equivalence relation $e\sim f$ if the edges $e$ and $f$ are both contained in some circuit, i.e., minimally dependent set, of ${\mathcal {M}}_{d}(G,p)$. The resulting equivalence classes are called the components of ${\mathcal {M}}_{d}(G,p)$. The matroid ${\mathcal {M}}_{d}(G,p)$ is the direct-sum of its components and ${\mathcal {M}}_{d}(G,p)$ is connected if it has exactly $1$ component.

A $d$-dimensional framework $(G,p)$ is rigid in $d$-dimensions if the closure of its edges in ${\mathcal {M}}_{d}(G,p)$ is a complete graph on the vertex set of the edges. Any two $d$-dimensional generic frameworks $(G,p)$ and $(G,q)$ define the same rigidity matroid, which is the $d$-dimensional generic rigidity matroid ${\mathcal {M}}_{d}(G)$. If ${\mathcal {M}}_{d}(G)$ is connected, then the graph $G=(V,E)$ is said to be ${\mathcal {M}}_{d}$ connected. If $E$ is a circuit in ${\mathcal {M}}_{d}(G)$, then the graph $G$ is said to be a ${\mathcal {M}}_{d}$-circuit.

Abstract rigidity matroid. A matroid ${\mathcal {A}}_{d}$ defined on the edges of the complete graph $K_{n}$ with closure operator $<\cdot >$ is a $d$-dimensional abstract rigidity matroid if it satisfies the four closure conditions as well the following two conditions. Let $E$ and $F$ be subsets of edges of $K_{n}$, let $V(E)$ denote the vertex set of a set of edges $E$, and let $K(V(E))$ be the complete graph of this vertex set.

• if $\left|V(E)\cap V(F)\right|<d$, then $<E\cup F>\subseteq \left(K(V(E))\cup K(V(F))\right)$; and
• if $<E>=K(V(E))$, $<F>=K(V(F))$, and $\left|V(E)\cap V(F)\right|\geq d$, then $<E\cup F>=K(V(E\cup F))$.

The first condition says that if the graphs $G(E)$ and $G(F)$, with edge sets $E$ and $F$ respectively, are connected by less than $d$ vertices, then the closure of each edge set is contained within its respective vertex set. In particular, neither closure adds more edges between $G(E)$ and $G(F)$, so there is a hinge motion at the shared vertices. The second condition says that if $G(E)$ and $G(F)$ are connected by at least $d$ vertices, then the graph $G(E\cup F)$ is generically rigid in $d$-dimensions.

Combinatorial characterizations of generically rigid graphs

Many results on the generic rigidity of graphs for various types of GCSs build off of the following key results about generic bar-joint frameworks and infinitesimal rigidity. Asimow and Roth showed that both rigidity and infinitesimal rigidity are generic properties of graphs. Furthermore, they proved the following relationship between these two forms of rigidity.

Theorem. A $d$-dimensional framework $(G,p)$ is infinitesimally rigid in $d$-dimensions if and only if $(G,p)$ is generic with respect to infinitesimal rigidity and rigid in $d$-dimensions.

Note that genericity is with respect to infinitesimal rigidity. A rigid framework that is generic with respect to only rigidity is not necessarily infinitesimally rigid, see Figure 1. Here is a very useful corollary of this theorem.

Corollary. A $d$-dimensional framework that is generic with respect to infinitesimal rigidity has an infinitesimal motion if and only if it has a continuous motion.

The next result ties generically rigid graphs to generically infinitesimally rigid graphs.

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

Another key result that goes back to Maxwell shows that independence of the edges of a graph $G=(V,E)$ in a sparsity matroid defined on the set $V\times V$ is necessary for $G$ to be generically rigid. A graph $G=(V,E)$ is $(k,l)$-sparse if for every subset $E'\subset E$, $|E'|\leq k|V(E')|-l$, where $V(E')$ is the vertex set of $E$. If $G$ additionally satisfies $|E|=k|V|-l$, then $G$ is called $(k,l)$-tight.

Theorem. If a graph $G$ is generically rigid in $d$-dimensions, then $G$ is $\left(d,{d+1 \choose 2}\right)$-tight.

For other types of frameworks, a result like the theorem above is called a Maxwell direction, or condition.

Rigidity theorems

In $1$-dimension, it is trivial to show that the class of generically rigid graphs is exactly the class of connected graphs. Also, the generic rigidity matroid ${\mathcal {M}}_{1}(G)$ is the unique abstract rigidity matroid ${\mathcal {A}}$, also called the connectivity or graphic matroid.

The Geiringer-Laman theorem characterizes generically rigid graphs in $2$-dimensions and is the inspiration for many subsequent results. This theorem was first proved by Geiringer in 1927 and later by Laman in 1970.

File:Laman subgraph.jpg

Figure 2. This graph is generically rigid. Removing the red edge yields a spanning $(2,3)$-tight subgraph.

Theorem. A graph $G=(V,E)$ is generically rigid in $2$-dimensions if and only if it has a $(2,3)$-tight spanning subgraph.

In particular, the converse of the Maxwell direction holds for $d=2$. A $(2,3)$-tight graph is also called a Geiringer-Laman graph or a generically minimally rigid graph. Figure 2 shows an example of a generically rigid graph in $2$-dimensions with a Geiringer-Laman subgraph. As another example, all wheel graphs are generically minimally rigid in $2$-dimensions.

Theorem. In $2$-dimensions, the generic rigidity matroid ${\mathcal {M}}_{2}(G)$ is the unique maximal abstract rigidity matroid ${\mathcal {A}}_{2}$.

There is no known combinatorial characterization of generically rigid graphs in $3$-dimensions or higher. The $d$-dimensional analogue of the Geiringer-Laman theorem is false for $d\geq 3$; in particular, the converse of the Maxwell direction is false for $d\geq 3$, see Figure 3.

File:Double banana.jpg

Figure 3. This graph, called the double banana, is $(3,6)$-tight but not generically minimally rigid in $3$-dimensions. One continuous motion involves rotating both bananas about the axis determined by the dotted line.

Global rigidity theorems

Consider a $d$-dimensional generic framework of a graph $G=(V,E)$ with an equilibrium stress $\omega$. The rank of the corresponding stress matrix $\Omega$ is at most $|V|-d-1$. Such a stress matrix is said to have maximum rank.

Theorem. A $d$-dimensional generic framework of a graph $G=(V,E)$, with $|V|\geq d+2$, is globally rigid in $d$-dimensions if and only if there exists an equilibrium stress $\omega$ whose corresponding stress matrix $\Omega$ has maximum rank.

Sufficiency was proved in and necessity was proved in . This theorem can be used to show that global rigidity is a generic property of graphs .

The following results are complete combinatorial characterizations of generically globally rigid graphs in dimensions $1$ and $2$. The result for $1$-dimension is easily verified.

Theorem. A graph $G$ is generically globally rigid in $1$-dimension if and only if it is a complete graph on at most $2$ vertices or $2$-connected.

Theorem. A graph $G$ is generically globally rigid in $2$-dimensions if and only if is a complete graph on at most $3$ vertices or $3$-connected and generically redundantly rigid in $2$-dimensions.

An alternate sufficient condition for generic global rigidity using vertex-redundant rigidity was given in , which led to a simpler proof of this theorem. Another characterization shows that a graph being generically redundantly rigid is equivalent to the graph being ${\mathcal {M}}_{2}$-connected .

The next results are sufficient conditions for a graph to be generically globally rigid.

Theorem. A graph $G$ is generically globally rigid in $2$-dimensions if any of the following are true:

• $G$ is $3$-connected and a ${\mathcal {M}}_{2}$-circuit
• $G$ is $6$-connected
• $G$ has at least $n\geq 4$ vertices and each vertex has minimum degree of at least ${\frac {n+1}{2}}$

The first condition follows from the fact that graphs that are $3$-connected and ${\mathcal {M}}_{2}$-circuits can be obtained from $K_{4}$ via a sequence of $1$-extensions, see Constructing generically rigid graphs. The graph in Figure 2 has $5$ vertices and each vertex has degree at least $3$, so it is generically globally rigid in $2$-dimensions.

The following is a sufficient condition in an arbitrary dimension.

Theorem. If a graph $G$ is generically vertex-redundantly rigid $d$-dimensions, then $G$ is generically globally rigid in $d$-dimensions.

Finally, the following is a necessary condition for generic global rigidity.

Theorem. If a graph $G$ is generically globally rigid in $d$-dimensions, then $G$ is either the complete graph on at most $d+1$ vertices or $G$ is $(d+1)$-connected and generically redundantly rigid in $d$-dimensions.

The converse of this theorem holds for dimensions $d\leq 2$, but not for $d\geq 3$. A graph that satisfies the necessary conditions of the theorem but is not generically globally rigid in $d$-dimensions is called a Hendrickson graph. The complete bipartite graph $K_{5,5}$ is a Hendrickson graph in $3$-dimensions. Other examples of Hendrickson graphs, including an infinite family for dimensions $d\geq 5$, can be found in .

Constructing generically rigid graphs

This section gives results on constructing generically rigid graphs via various operations.

Operations

Let $G$ be a graph. For any dimension $d$, the following operations transform $G$ into a new graph $G'$.

File:Elipse-ops.jpg

Figure 4.

• $0$-extension: $G'$ is obtained by adding a new vertex $u$ to $G$ with $d$ edges incident to $u$ and $d$ distinct vertices in $G$.

This operation is also called a Henneberg-1 move or vertex addition. If a graph $G$ is generically rigid in $d$-dimensions, then a graph $G'$ obtained by performing a $0$-extension on $G$ is generically rigid in $d$-dimensions, i.e. $0$-extensions preserve generic rigidity. This is easily verified by considering the rank of the rigidity matrices. However, this operation does not preserve generic global rigidity in $d$-dimensions.

• $1$-extension: $G'$ is obtained by removing an edge $(v,w)$ from $G$ and adding a new vertex $u$ to $G$ with edges $(u,v)$, $(u,w)$, and $d-1$ other edges incident to $u$ and $d-1$ distinct vertices in $G$.

This operation is also called a Henneberg-2 move or edge splitting. Additionally, this operation preserves generic rigidity and generic global rigidity in $d$-dimensions.

• Cone: $G'$ is obtained by adding a new vertex $u$ to $G$ with an edge between $u$ and every other vertex of $G$.

This operation preserves generic global rigidity in $d$-dimensions.

• $X$-replacement: $G'$ is obtained by removing two non-adjacent edges $(v_{1},w_{1})$ and $(v_{2},w_{2})$ from $G$ and adding a vertex $u$ with edges $(u,v_{1}),(u,v_{2}),(u,w_{1}),(u,w_{2})$, and $d-1$ other edges incident to $u$ and $d-1$ distinct vertices in $G$.

This operation preserves generic rigidity in $2$-dimensions. This property is false in $4$-dimensions and conjectured in $3$-dimensions. Additionally, this operation does not preserve generic global rigidity in any dimension $d$. This is because it does not always preserve $(d+1)$-connectivity, which is a necessary condition for generic global rigidity, see Combinatorial characterizations of generically rigid graphs.

The following operation only applies in $3$-dimensions.

• $V$-replacement: $G'$ is obtained by removing two adjacent edges $(v,w)$ and $(w,z)$ from $G$ and adding a vertex $u$ with edges $(u,v),(u,w),(u,z)$, and $2$ other edges incident to $u$ and $2$ distinct vertices in $G$.

This operation does not preserve generic rigidity, but a variant called a double $V$-replacement is conjectured to preserve generic rigidity in $3$-dimensions. If either the $X$-replacement or double $V$-replacement operations are proven to preserve generic rigidity in $3$-dimensions, then a combinatorial characterization of generically rigid graphs in $3$-dimensions is immediately obtained.

File:Other-ops.jpg

Figure 5.

• Vertex splitting: Consider a vertex $u$ of $G$ that is adjacent to the vertices $v_{1},\dots ,v_{m}$. $G'$ is formed by removing $u$ from $G$ and adding vertices $u_{1}$ and $u_{2}$ with edges $(u_{1},v_{1}),(u_{2},v_{1}),\dots ,(u_{1},v_{d-1}),(u_{2},v_{d-1}),(u_{1},u_{2})$ and, for each vertex $v_{i}$ with $i\in \{d,\dots ,m\}$, an edge $(u_{j},v_{i})$, where $j\in \{1,2\}$. A vertex splitting is non-trivial if $u_{1}$ and $u_{2}$ have degrees at least $d+1$.

This operation preserves generic rigidity, but it does not preserve generic global rigidity, because it can create a degree $d$ vertex. A degree restricted vertex split is a variant of a vertex split that can only create vertices of degree at least $d+1$. This restricted operation preserves generic global rigidity in $2$-dimensions, and the problem is open in higher dimensions. Proving the result for general dimensions is equivalent to showing that if $G'$ is a graph obtained from a generically globally rigid graph $G$ in $d$-dimensions via a degree restricted vertex split, then $G'$ is generically redundantly rigid in $3$-dimensions. It is known that graphs obtained from the complete graph $K_{d+2}$ via a sequence of degree restricted vertex splits are generically globally rigid in $d$-dimensions.

The following operation only applies in $2$-dimensions.

• vertex-to-4-cycle: Let a vertex $u$ of $G$ be adjacent to the vertices $v_{1},\dots ,v_{m}$. $G'$ is formed by removing $u$ from $G$ and adding vertices $u_{1}$ and $u_{2}$ with edges $(v_{1},u_{1}),(u_{1},v_{2}),(v_{2},u_{2}),(u_{2},v_{1})$ and, for each vertex $v_{i}$ with $i\in \{3,\dots ,m\}$, an edge $(u_{j},v_{i})$, where $j\in \{1,2\}$.

This operation preserves generic rigidity in $2$-dimensions.

Finally, there are several techniques for combining generically globally rigid graphs to obtain another generically globally rigid graph.

Rigidity theorems

The following is an alternative characterization of generically rigid graphs in $2$-dimensions based on $0$- and $1$-extensions.

Theorem. A graph $G$ is generically minimally rigid in $2$-dimensions if it can be obtained from the complete graph $K_{2}$ via a sequence of $0$- and $1$-extensions.

Graphs constructed in this manner are called Henneberg-2 graphs. This theorem was strengthened to show that any generically minimally rigid graph $G$ can be obtained from another generically minimally rigid graph $G'$ via a sequence of $0$- and $1$-extensions. Another strengthening of this theorem shows that $G$ is additionally planar if the $1$-extensions are restricted to preserve planarity. A similar result shows that $G$ is additionally planar if the operation is replaced with a restricted vertex splitting operation that preserves planarity. If the base graph $K_{2}$ in the theorem is replaced with $K_{4}$, then $G$ is a graph that contains an edge $e$ such that $G\setminus e$ is generically minimally rigid.

A graph $G=(V,E)$ is a $(2,3)$-circuit if $|E|=2|V|-2$ and, for every subset of edges $E'\subset E$, $|E'|\leq 2|V(E')|-3$.

Theorem. A graph $G$ is a $(2,3)$-circuit if and only if $G$ can be obtained from disjoint copies of $K_{4}$ by applying $1$-extensions and $2$-sums to connected components.

Global rigidity theorems

The following are necessary and sufficient methods for constructing generically globally rigid graphs. From the well-known ear-decomposition characterization of $2$-connected graphs, we have:

Theorem. A graph $G$ is $2$-connected, or equivalently generically globally rigid in $1$-dimension, if and only it can be obtained from the complete graph $K_{3}$ via a sequence of $1$-extensions and edge additions.

Theorem. A graph $G$ is $3$-connected and generically redundantly rigid in $2$-dimensions, or equivalently generically globally rigid in $2$-dimensions, if and only if it can be obtained from the complete graph $K_{4}$ via a sequence of $1$-extensions and edge additions.

The next results give sufficient methods for constructing generically globally rigid graphs.

Theorem. If $G$ can be obtained from $K_{d+2}$ via a sequence of $1$-extensions and edge additions, then $G$ is generically globally rigid in $d$-dimensions.

Example. By the theorem above, every wheel graph is generically globally rigid in $2$-dimensions.

Rigidity for other types of frameworks

This section presents structural rigidity results for various types of frameworks, see Geometric Constraint System. A graph $G$ is said to be generically (resp. globally) rigid with respect to frameworks of type $X$ if there exists a (resp. globally) rigid generic framework of type $X$ whose constraint graph is $G$.

Body-bar-hinge frameworks

This section concerns body-bar-hinge frameworks. This type of framework is a special case of a bar-joint framework, so the corresponding results carry over, see Types of frameworks. When a body-bar-hinge framework consists of only bars or only hinges, it is called a body-bar or body-hinge framework respectively.

Definitions

Body-bar frameworks

Let the pair $(G,b)$ be a $d$-dimensional body-bar framework, where $G=(V,E)$ is a multigraph and $b$ is a map $b:(v,e_{v})\rightarrow b_{v,e}\in \mathbb {R} ^{d}$ that describes the rigid bodies corresponding to the vertices of $G$ and the connections between them. Each vertex $v$ is mapped to a set of points, one for each edge $e_{v}$ incident to $v$, that represent where bars are attached to the body. The map $b$ must satisfy the distance constraints on the bars. The rigidity matrix of $R(G,b)$ is defined using the Plücker coordinates of the edges and has dimensions $|E|\times {d+1 \choose 2}|V|$. All other definitions pertaining to body-bar frameworks are analogous to those for bar-joint frameworks.

Infinitesimal rigidity condition. Similarly to bar-joint frameworks, a body-bar framework is infinitesimally rigid if and only if the rank of its rigidity matrix is ${d+1 \choose 2}|V|-{d+1 \choose 2}$.

From the rank condition above we get the following Maxwell Condition.

Maxwell Condition. If a body-bar framework $(G,b)$ is infinitesimally rigid, with $G=(V,E)$, then

• $G$ contains ${d+1 \choose 2}$ edge-disjoint spanning trees
• $G$ has a spanning $\left({d+1 \choose 2},{d+1 \choose 2}\right)$-tight subgraph

The two statements above are equivalent by the Tutte and Nash-Williams theorem. The Maxwell Condition leads to the following test for infinitesimal rigidity.

Infinitesimal rigidity test. A body-bar framework is not infinitesimally rigid is there is a partition ${\mathcal {P}}$ of the vertices $V$ such that $|E({\mathcal {P}})|<{d+1 \choose 2}(|{\mathcal {P}}|-1)$, where $|E({\mathcal {P}})|$ is the number of edges between different sets of ${\mathcal {P}}$.

Body-hinge frameworks

Let the pair $(G,h)$ be a $d$-dimensional body-hinge framework, where $G=(V,E)$ is a multigraph and $h$ maps edges to $(d-2)$-dimensional subspaces. Motions of two bodies connected by a hinge are constrained to be rotations about the $(d-2)$-dimensional subspace. As with body-bar frameworks, the rigidity matrix $R(G,h)$ is defined using the Plücker coordinates.

Maxwell Condition. If a body-hinge framework is infinitesimally rigid, then the graph $G'$ obtained by duplicating each edge of $G$ ${d+1 \choose 2}-1$ times contains ${d+1 \choose 2}$ edge-disjoint spanning trees.

Body-bar-hinge frameworks

A body-bar-hinge framework is a triple $(G,b,h)$ of a multigraph $G=(V,E_{b}\cup E_{h})$, a set of bars $b$, and a set of hinges $h$. The usual definitions are obtained by combining the definitions for body-bar and body-hinge frameworks. A Maxwell Condition for rigidity is obtained by combining the Maxwell Conditions for body-bar and body-hinge frameworks.

Maxwell Condition. If a body-bar-hinge framework $(G,b,h)$ is infinitesimally rigid, with $G=(V,E_{b}\cup E_{h})$, then the graph $G'$ obtained by duplicating each edge in $E_{H}$ of $G$ ${d+1 \choose 2}-1$ times contains ${d+1 \choose 2}$ edge-disjoint spanning trees.

Generic rigidity theorems

Unlike bar-joint frameworks, there is a combinatorial characterization of generically rigid multigraphs with respect to body-bar-hinge frameworks in any dimension. In particular, the converse of the Maxwell direction is true for any dimension.

Theorem. A multigraph $G$ is generically rigid in $d$-dimensions with respect to body-bar frameworks if and only if

• $G$ contains ${d+1 \choose 2}$ edge-disjoint spanning trees; or equivalently
• $G$ is $\left({d+1 \choose 2},{d+1 \choose 2}\right)$-tight.

Theorem. A multigraph $G$ is generically rigid in $d$-dimensions with respect to body-hinge frameworks if and only if the graph $G'$ obtained by duplicating each edge of $G$ ${d+1 \choose 2}-1$ times contains ${d+1 \choose 2}$ edge-disjoint spanning trees.

File:Body-bar-hinge-multigraph.jpg

Figure 6. (a) is generically rigid in $2$-dimensions with respect to body-hinge frameworks and (b) is gen erically rigid in $2$-dimensions with respect to body-bar frameworks.

File:Body-bar-hinge-frameworks.jpg

Figure 7. (a) and (b) are $2$-dimensional rigid body-hinge and body-bar frameworks of the multigraph in Figure 6b respectively.

Example. The multigraph in Figure 6a does not have $3$ edge-disjoint spanning trees, so it is not generically rigid in $2$-dimensions with respect to body-bar frameworks. However, it is generically rigid in $2$-dimensions with respect to body-hinge frameworks, because duplicating each edge $2$ times yields the multigraph in Figure 6b, which has $3$ edge-disjoint spanning trees. Furthermore, the multigraph in Figure 6b is generically rigid in $2$-dimensions with respect to body-bar frameworks. Figure 7 shows a $2$-dimensional rigid body-hinge and body-bar framework of the multigraph in Figure 6b respectively.

The following is a combinatorial method to determine the rank of the rigidity matrix for a body-bar-hinge framework.

Theorem. Let $G=(V,E_{b}\cup E_{h})$ be the multigraph of a $d$-dimensional generic body-bar-hinge framework $(G,b,h)$ and let $G'$ be the graph obtained by duplicating each edge in $E_{h}$ ${d+1 \choose 2}-1$ times. The rank of the rigidity matrix of $(G,b,h)$ is $\min \left\{{d+1 \choose 2}(|V(G)|-|{\mathcal {P}}|)+E_{h}({\mathcal {P}})|{\mathcal {P}}{\text{ is a partition of }}V(G')\right\}.$

The following results concern variants of body-bar-hinge frameworks. Consider a $k$-plate-bar framework. These are similar to body-bar frameworks, except that motions that fix the plates are factored out. When $k=d$ these frameworks are body-bar frameworks and when $k=0$ these frameworks are bar-joint frameworks.

Theorem. A multigraph $G$ is generically rigid in $d$-dimensions with respect to $(d-2)$-plate-bar frameworks if and only if $G$ contains a $\left({d+1 \choose 2}-1,{d+1 \choose 2}\right)$-tight spanning subgraph.

An alternative proof was given in , and a method for constructing $\left(k-1,k\right)$-tight graphs was given in .

An identified body-hinge framework is a body-hinge framework where each hinge is a $(d-2)$-plate, so this type of framework can viewed as a multigraph $G=(V_{b}\cup V_{h},E)$, where $V_{b}$ are bodies, $V_{h}$ are $(d-2)$-plates, and $E$ are bars connecting bodies to plates. Hence, the results for plate-bar frameworks extend to this class of frameworks as follows.

Theorem. A multigraph $G=(V_{b}\cup V_{h},E)$ is generically rigid in $d$-dimensions with respect to identified body-hinge frameworks if and only if the graph $G'$ obtained by duplicating each edge of $G$ ${d+1 \choose 2}-1$ times satisfies

• $|E(G')|={d+1 \choose 2}|V_{b}|+\left({d+1 \choose 2}-1\right)|V_{h}|-{d+1 \choose 2}$
• for any nonempty subgraph $H$ of $G'$, $|E(H)|\leq {d+1 \choose 2}|V_{b}\cap V(H)|+\left({d+1 \choose 2}-1\right)|V_{h}\cap V(H)|-{d+1 \choose 2}$.

A panel-hinge framework can be viewed as a body-hinge framework with the added restriction that for each panel, i.e., each $(d-1)$-plate, the hinges attached to it all lie in a $(d-1)$-dimensional subspace. The Maxwell direction still applies for these frameworks, but the other direction is not immediately clear. The following theorem was conjectured in :

Molecular theorem. A multigraph $G$ is generically rigid in $d$-dimensions with respect to panel-hinge frameworks if and only if it is generically rigid in $d$-dimensions with respect to body-hinge frameworks.

The theorem was proved in $2$-dimensions using $0$- and $1$-extensions and for general dimensions using an inductive construction. A global rigidity version of the theorem is conjectured.

Molecular frameworks are used to study ideal molecules in $3$-dimensions. Let $G^{2}$ be the squared graph of a graph $G$.

Theorem. For a graph $G$, the following statements are equivalent:

• $G$ is generically rigid in $3$-dimensions with respect to molecular frameworks;
• $G$ is generically rigid in $3$-dimensions with respect to panel-hinge frameworks;
• $G^{2}$ is generically rigid in $3$-dimensions with respect to bar-joint frameworks; and
• The graph obtained by duplicating the edges of $G$ $5$ times contains six edge-disjoint spanning trees.

Several important consequences of this theorem can be found in .

Generic global rigidity theorems

The following results are complete combinatorial characterizations of generically rigid graphs with respect to body-bar-hinge frameworks.

Theorem. A multigraph $G$ is generically globally rigid in $d$-dimensions with respect to body-bar frameworks, if and only if for every edge $e$ of $G$, $G\setminus e$ contains ${d+1 \choose 2}$ edge-disjoint spanning trees.

Theorem. A multigraph $G$ is generically globally rigid in $2$-dimensions with respect to body-hinge frameworks, if and only if $G$ is $3$-edge-connected.

Example. The multigraph in Figure 6b is $3$-edge-connected and removing any single edge results in a subgraph with $3$ edge-disjoint spanning trees. Hence, by the above theorems, the multigraph is generically globally rigid in $2$-dimensions with respect to both body-bar and body-hinge frameworks. The multigraph in Figure 6a is not generically globally rigid in $2$-dimensions with respect to either type of framework.

Theorem. Let $G=(V,E_{b}\cup E_{h})$ be a multigraph and let $G'$ be the graph obtained by duplicating each edge in $E_{h}$ $\left({d+1 \choose 2}-1\right)$ times. $G$ is generically globally rigid in $d$-dimensions, for $d\geq 3$, with respect to body-bar-hinge frameworks if and only if for every edge $e$ of $G'$, $G'\setminus e$ contains ${d+1 \choose 2}$ edge-disjoint spanning trees.

Rigidity of point-line frameworks

This section concerns the rigidity of point-line frameworks in $2$-dimensions, where each geometric object is either a point or a line and each constraint is either the distance between two points, the (shortest) distance between a point and a line, or the angle between two lines.

Definitions

Let $(G=(V_{p}\cup V_{l},E),p)$ be a point-line framework. The map $p$ maps vertices $u$ in $V_{p}$ to points $(x_{u},y_{u})$ in the plane and vertices $u$ in $V_{l}$ to pairs $(a_{u},b_{u})$ that define lines $y=a_{u}x+b_{u}$.

Rigidity map. $\rho :\mathbb {R} ^{2|V|}\rightarrow \mathbb {R} ^{|E|}$ is defined as follows. For each edge $(u,v)$ of $G$, set $\rho _{uv}={\begin{cases}(x_{u}-x_{v})^{2}+(y_{u}-y_{v})^{2}&{\text{if }}u,v\in V_{p}\\(x_{u}-y_{u}a_{v}-b_{v})(1+a_{v}^{2})^{-{\frac {1}{2}}}&{\text{if }}u\in V_{p}{\text{ and }}v\in V_{l}\\\tan ^{-1}a_{u}-\tan ^{-1}a_{v}&{\text{if }}u,v\in V_{l}\end{cases}}.$

Rigidity matrix. Similarly to bar-joint frameworks, the rigidity matrix $R(G,p)$ of a point-line framework $(G,p)$ is obtained from the Jacobian of the rigidity map. A row of the rigidity matrix corresponding to an edge $(u,v)$ has entries according to the following cases:

• $x_{u}-x_{v},y_{u}-y_{v},x_{v}-x_{u}$, and $y_{v}-y_{u}$ in the columns corresponding to the vertices $u$ and $v$ respectively, if $u,v\in V_{p}$;
• $1,-a_{v}.-x_{u}a_{v}-y_{u}$, and $-1$ in the columns corresponding to the vertices $u$ and $v$ respectively, if $u\in V_{p}$ and $v\in V_{l}$;
• $1$ and $-1$ in the columns corresponding to $u_{a}$ and $v_{a}$ respectively, if $u,v\in V_{l}$;
• $0$, otherwise.

The remaining definitions of rigidity concepts for a point-line framework are analogous to those for bar-joint frameworks. A point-line framework is degenerate if some trivial motion does not alter the framework.

Theorems

Theorem. If a point-line framework $(G=(V_{p}\cup V_{l},E),p)$ is nondegenerate, then

• the rank of the rigidity matrix is $R(G,p)\leq 2|V_{p}\cup V_{l}|-3$;
• if the rank of the rigidity matrix is $R(G,p)=2|V_{p}\cup V_{l}|-3$, then $p$ is rigid; and
• if $(G,p)$ is a generic point-line framework and the rank of the rigidity matrix is $R(G,p)<2|V_{p}\cup V_{l}|-3$, then $(G,p)$ is not rigid.

Rigidity of body-cad frameworks

This section concerns the rigidity of body-cad frameworks in $3$-dimensions. These frameworks consist of rigid bodies with various types of constraints between pairs of bodies. There are $21$ types of constraints for body-cad frameworks that fall into the categories of coincidence, angular, and distance constraints; hence the abbreviation "cad."

File:Body-cad.jpg

Figure 8. A rigid body-cad framework with $3$ constraints between bodies $A$ and $B$: a point-point distance constraint between $p_{1}$ and $p_{2}$, a point-line incidence constraint between $p_{4}$ and the line $L_{1}$ determined by $p_{2}$ and $p_{3}$, and a perpendicular constraint between $L_{1}$ and the line $L_{2}$ determined by $p_{4}$ and $p_{5}$.

Definitions

Consider a body-cad GCS $(G,c,L_{1},\dots ,L_{21})$ with a primitive cad graph $G'=(V,R\cup B)$. The graph $G$ is $(k_{1},l_{1},k_{2},l_{2})$-nested sparse if $G$ is $(k_{1},l_{1})$-sparse and the subgraph $G_{R}=(V,R)$ of $G'$ is $(k_{2},l_{2})$-sparse. The graph $G$ is $(k_{1},l_{1},k_{2},l_{2})$-nested tight if, additionally, $G$ is $(k_{1},l_{1})$-tight.

Maxwell Condition. If a multigraph $G$ is generically minimally rigid in $d$-dimensions with respect to body-cad frameworks, then the primitive constraint graph of $G$ is $\left({d+1 \choose 2},{d+1 \choose 2},{d \choose 2},{d \choose 2}\right)$-nested tight.

Infinitesimal motion. Using ideas from screw theory, an instantaneous motion can be defined as a $1\times {d+1 \choose 2}$ vector $s=(\omega ,v)$, where $\omega$ is a $1\times {d \choose 2}$ vector that describes the angular component of $s$ and $v$ is a $1\times ({d+1 \choose 2}-{d \choose 2})$ vector that provides the remaining information. As with other types of frameworks, the kernel of the rigidity matrix is the space of infinitesimal motions.

Rigidity matrix. The rigidity matrix of a body-cad framework has a row for each edge in the primitive cad graph of the framework, i.e., for each primitive constraint, and ${d+1 \choose 2}$ columns for each rigid body.

Theorems

The following are complete characterizations of generically minimally rigid multipgraphs in dimensions $2$ and $3$, with respect to body-cad frameworks. A primitive cad graph $G=(V,R\cup B)$ is $[a,b]$-sparse if there exists a subset $B'\subset B$ such that the subgraph $G'=(V,R\cup B')$ is $(a,a)$-sparse and the subgraph $G''=(V,B\setminus B')$ is $(b,b)$-sparse. The graph $G$ is $[a,b]$-tight if, additionally, $|R\cup B|=(a+b)|V|-(a+b)$. By the Tutte and Nash Williams theorem, $G$ is $[a,b]$-tight if $G'$ is the union of $a$ edge-disjoint spanning trees and $G''$ is the union of $b$ edge-disjoint spanning trees.

Theorem. A multigraph $G$ is generically minimally rigid in $2$-dimensions with respect to body-cad frameworks if and only if the primitive cad graph of $G$ is $[1,2]$-tight.

Theorem. A multigraph $G$ is generically minimally rigid in $3$-dimensions with respect to body-cad frameworks, with no coincident points, if and only if the primitive cad graph of $G$ is $[3,3]$-tight.

The added restriction in $3$-dimensions that body-cad frameworks cannot not have coincident points is because they coincident points create degenerate frameworks, i.e., they cause the rank of the rigidity matrix to drop.

Pinned subspace-incidence frameworks

A combinatorial characterization of pinned subspace-incidence frameworks can be found in , along with the definitions of the main rigidity concepts.

Sticky-disk packings

This section concerns the rigidity of [[Geometric Constraint System#Sticky-disk systems|sticky-disk packings. A sticky-disk GCS is a triple $P=(V,R,E)$, where $V$ is a set of disks, $R$ is the set of radii of the disks, and $E$ is the set of pairs of disks that are mutually tangent. A sticky disk packing $(P,p)$ is a placement $p$ of the disks in $2$-dimensions such that the tangencies of $P$ are satisfied. The contact framework of $(P,p)$ is the bar-joint framework GCS $(G,p)$, where $G=(V,E)$ is the constraint graph between the centers of the disks and $p$ is a placement of the vertices of $G$ in $d$ dimensions that satisfies the distance constraints induced by $R$: for each edge $(u,v)$ of $E$, $R$ gives the constraint $\delta _{uv}=r_{u}+r_{v}$, where $r_{u}$ and $r_{v}$ are the radii of $u$ and $v$. These radii-based constraints cause sticky-disc packings to have $|V|$ degrees of freedom, instead of the usual $2|V|-3$ for a bar-joint frameworks. Hence, even with a set of generic radii, i.e, radii that are algebraically independent over the rational numbers, bar-joint frameworks corresponding to sticky-disk packings are non-generic.

File:Sticky-disk.jpg

Figure 9. A rigid $2$-dimensional sticky-disk packing.

The following theorem gives a complete combinatorial characterization of sticky-disk packings.

Theorem. If $(P=(V,R,E),p)$ is a sticky-disk packing with generic radii, or just generic radii ratios, then the graph of the contact framework is a planar Geiringer-Laman graph. Furthermore, if $|E|=2|V|-3$, then $(P,p)$ is rigid and infinitesimally rigid.

Results for $3$-dimensions, where sticky-disks are replaced by sticky-spheres, are unknown.

Rigidity of symmetric and periodic frameworks

This section concerns the rigidity of $\Gamma$-symmetric bar-joint frameworks, for some group $\Gamma$, and periodic frameworks. There are two types of infinitesimal rigidity for a $\Gamma$-symmetric framework $(G,p)$: fully, or forced, $\Gamma$-symmetric infinitesimal rigidity, which requires that there is no non-trivial infinitesimal motion path starting from $(G,p)$ along which all frameworks are $\Gamma$-symmetric, and incidental $\Gamma$-symmetric infinitesimal rigidity, which requires that $(G,p)$ has no non-trivial infinitesimal motions of any kind. The latter form of symmetric infinitesimal rigidity is different from general infinitesimal rigidity, because a $\Gamma$-symmetric infinitesimally rigid framework does not typically have a spanning $\Gamma$-symmetric minimally rigid subframework; hence, Geringer-Laman type results cannot be used in this setting.

Definitions

A graph $G$ is $\Gamma$-symmetric if there exists a group action $\theta :\Gamma \rightarrow Aut(G)$, where $Aut(G)$ is the automorphism group of $G$. A bar-joint framework $(G,p)$ is $\Gamma$-symmetric if there exists a homomorphism $\tau :\Gamma \rightarrow O(\mathbb {R} ^{d})$, where $O(\mathbb {R} ^{d})$ is the orthogonal group of $\mathbb {R^{d}}$, such that $\tau (\gamma )(p_{i})=p_{\theta (\gamma )(i)},$ for all $\gamma$ in $\Gamma$ and points $p(i)$. The subgroup $\tau (\Gamma )$ of $O(\mathbb {R} ^{d})$ is called the symmetry group of the framework $(G,p)$, and $(G,p)$ is said to be $\Gamma$-symmetric with respect to $\theta$ and $\tau$. The equation above requires that mapping each point $p_{i}$ of the framework $(G,p)$ to another point $p_{j}$ via an automorphism $\theta (\gamma )$ is equivalent to applying an element of the symmetry group $\tau (\Gamma )$ to the framework $(G,p)$.

Consider the group representation $P_{E}:\Gamma \rightarrow GL(\mathbb {R} ^{|E|})$ that assigns each element $\gamma$ in $\Gamma$ the permutation matrix corresponding to the permutation $\theta (\gamma )$ of the edges of $G$, i.e., $P_{E}(\gamma )=\left[\delta _{i,\theta (\gamma )(j)}\right]_{i,j\in V}$, where $\delta$ is the Kronecker delta. Likewise, consider the group representation $P_{V}:\Gamma \rightarrow GL(\mathbb {R} ^{d|V|})$ that assigns each element $\gamma$ in $\Gamma$ the permutation matrix corresponding to the permutation $\theta (\gamma )$ of the vertices of $G$. Also, let $A\otimes B$ denote the Kronecker product of the matrices $A$ and $B$.

Types of symmetric infinitesimal motion / rigidity:

• Incidentally symmetric infinitesimal rigidity - A $\Gamma$-symmetric framework $(G,p)$ is incidentally $\Gamma$-symmetric infinitesimally rigid if all of its infinitesimal motions are trivial.
• Phase symmetric infinitesimal motion - Let $\Gamma =\mathbb {Z} _{k}$ and let $\rho _{j}:\Gamma \rightarrow \mathbb {C} \setminus 0$, for $j\in \{1,\dots ,k\}$, be the irreducible representations of $\Gamma$ given by $\rho _{j}(\gamma )=\lambda ^{j\gamma }$, where $\lambda$ denotes the roots of unity $e^{\frac {2\pi i}{k}}$. An infinitesimal motion $p':V\rightarrow \mathbb {R} ^{d}$ of a $\Gamma$-symmetric framework $(G,p)$ is $\rho _{j}$-symmetric if it lives in a $(\tau \otimes P_{V})$-invariant subspace $V_{j}$ corresponding to $\rho _{j}$, i.e., $p'$ satisfies

$\tau (\gamma )p'_{l}=\lambda ^{j\gamma }p'_{\theta (\gamma )(l)},$ for all $\gamma$ in $\Gamma$ and velocities $p'_{l}$.

• Phase symmetric infinitesimal rigidity - Let $\Gamma =\mathbb {Z} _{k}$. A $\Gamma$-symmetric framework $(G,p)$ is $\rho _{j}$-symmetric infinitesimally rigid if all its $\rho _{j}$-symmetric infinitesimal motions are trivial.

Phase-symmetric infinitesimal rigidity is use to detect incidental symmetric infinitesimal rigidity: if $\Gamma$-symmetric framework $(G,p)$ is $\rho _{j}$-symmetric infinitesimally rigid for all irreducible representations $\rho _{j}$ of $\Gamma$, then $(G,p)$ is $\Gamma$-symmetric incidentally infinitesimally rigid.

File:Antisymmetric-inf-mot.jpg

Figure 10. $2$-dimensional $C_{s}$-symmetric frameworks that are fully symmetric infinitesimally rigid but not incidentally symmetric infinitesimally rigid.

Example. The reflection group $C_{s}$ has two distinct $1$-dimensional irreducible representations $\rho _{0}$ and $\rho _{1}$. For a $2$-dimensional $C_{s}$-symmetric framework $(G,p)$, the block rigidity matrix (see below) has two blocks: ${\tilde {R}}_{0}(G,p)$ and ${\tilde {R}}_{1}(G,p)$ corresponding to $\rho _{0}$ and $\rho _{1}$ respectively. The block ${\tilde {R}}_{0}(G,p)$ is the orbit rigidity matrix (see below) and the block ${\tilde {R}}_{1}(G,p)$ is the antisymmetric orbit rigidity matrix that describes the $rho_{1}$-symmetric rigidity of $(G,p)$. Specifically, the kernel of ${\tilde {R}}_{1}(G,p)$ is the space of antisymmetric infinitesimal motions $p'$ that satisfy $\tau (\gamma )p'_{l}=-p'_{\theta (\gamma )(l)},$ for all $\gamma$ in $\Gamma$ and velocities $p'_{l}$, i.e. the reflection reverses the velocities assigned to the points of $(G,p)$. Figure 10 shows two $C_{s}$-symmetric frameworks that have antisymmetric infinitesimal motions; thus, these frameworks are not incidentally infinitesimally rigid. Notice that the framework in Figure 10a has an underlying Geiringer-Laman graph, which is generically minimally rigid in $2$-dimensions, but this is not sufficient for incidental infinitesimal rigidity.

• Fully symmetric infinitesimal motion - A fully $\Gamma$-symmetric infinitesimal motion of the $\Gamma$-symmetric framework $(G,p)$ is an infinitesimal motion $p':V\rightarrow \mathbb {R} ^{d}$ such that

$\tau (\gamma )p'_{i}=p'_{\theta (\gamma )(i)},$ for all $\gamma$ in $\Gamma$ and velocities $p'_{i}$.

• Fully symmetric infinitesimal rigidity - A $\Gamma$-symmetric framework $(G,p)$ is fully infinitesimally rigid if all its fully $\Gamma$-symmetric infinitesimal motions are trivial.

Example. The frameworks in Figure 10 are fully symmetric infinitesimally rigid, even though the framework in Figure 10b is not rigid in general. These frameworks have no fully symmetric infinitesimal motions. The theorems below will verify this.

Symmetric rigidity matrices:

The bar-joint rigidity matrix takes on special forms for $\Gamma$-symmetric frameworks.

Theorem. The bar-joint rigidity matrix $R(G,p)$ satisfies $R(G,p)(\tau \otimes P_{V})(\gamma )=P_{E}(\gamma )R(G,p)$.

This theorem allows the bar-joint rigidity matrix to be written as a block matrix, as the following corollary demonstrates.

Corollary. Let $\rho _{0},\dots ,\rho _{m}$ be the irreducible representations of $\Gamma$. There exist invertible matrices $S$ and $T$ such that

$T^{T}R(G,p)S:={\tilde {R}}(G,p)={\begin{bmatrix}{\tilde {R}}_{0}(G,p)&\,&0\\\,&\ddots &\,\\0&\,&{\tilde {R}}_{m}(G,p)\\\end{bmatrix}}.$

The block ${\tilde {R}}_{i}(G,p)$ has dimensions $dim(W_{i})\times dim(V_{i})$, where $W_{i}$ and $V_{i}$ are the $P_{E}$-invariant and $(\tau \otimes P_{V})$-invariant subspaces corresponding to the irreducible representation $\rho _{i}$ respectively.

$\Gamma$-generic framework. The framework $(G,p)$ is $\Gamma$-generic if its rigidity matrix has max rank over all $\Gamma$-symmetric frameworks with constraint graph $G$.

This form of the rigidity matrix is useful for studying symmetric rigidity, and can be further refined by considering the quotient gain graph of a $\Gamma$-symmetric framework $(G,p)$, see Types of systems. Let $(G,p)$ be a $\Gamma$-symmetric framework such that $\theta$ is a free group action on the vertices of $G$ and let $({\tilde {G}},\psi )$ be the quotient gain graph of $(G,p)$.

Orbit rigidity matrix. The $d$-dimensional orbit rigidity matrix $O({\tilde {G}},\psi ,p)$ has dimensions $|{\tilde {E}}|\times d|{\tilde {V}}|$. The row corresponding to the edge ${\tilde {e}}=({\tilde {u}},{\tilde {v}})$ is $0$ everywhere, except in the columns corresponding to ${\tilde {u}}$ and ${\tilde {v}}$, which have the form $p_{\tilde {u}}-\tau (\psi ({\tilde {e}}))p_{\tilde {v}}$ and $p_{\tilde {v}}-\tau (\psi ({\tilde {e}}))^{-1}p_{\tilde {u}}$ respectively, if ${\tilde {u}}\neq {\tilde {v}}$, and $2p_{\tilde {u}}-\tau (\psi ({\tilde {e}}))p_{\tilde {u}}-\tau (\psi ({\tilde {e}}))^{-1}p_{\tilde {u}}$, otherwise.

The kernel of the orbit rigidity matrix is isomorphic to the space of fully $\Gamma$-symmetric infinitesimal motions of $(G,p)$. Likewise, the cokernel of the orbit rigidity matrix is isomorphic to the space of fully $\Gamma$-symmetric self-stresses of $(G,p)$.

$\rho _{0}$-generic framework. The framework $(G,p)$ is $\rho _{0}$-generic if its orbit rigidity matrix has max rank over all $\Gamma$-symmetric frameworks with constraint graph $G$.

Phase symmetric orbit rigidity matrix. Let $\Gamma =\mathbb {Z} _{k}$. The $d$-dimensional $\rho _{j}$-symmetric orbit rigidity matrix $O({\tilde {G}},\psi ,p)$ has dimensions $|{\tilde {E}}|\times d|{\tilde {V}}|$. The row corresponding to the edge ${\tilde {e}}=({\tilde {u}},{\tilde {v}})$ is $0$ everywhere except in the columns corresponding to ${\tilde {u}}$ and ${\tilde {v}}$, which have the form $p_{\tilde {u}}-\tau (\psi ({\tilde {e}}))p_{\tilde {v}}$ and $\lambda ^{j\psi ({\tilde {e}})}(p_{\tilde {v}}-\tau (\psi ({\tilde {e}}))^{-1}p_{\tilde {u}})$ respectively, if ${\tilde {u}}\neq {\tilde {v}}$, and $p_{\tilde {u}}-\tau (\psi ({\tilde {e}}))p_{\tilde {u}}+\lambda ^{j\psi ({\tilde {e}})}(p_{\tilde {u}}-\tau (\psi ({\tilde {e}}))^{-1}p_{\tilde {u}})$, otherwise.

The kernel of the $\rho _{j}$-symmetric orbit rigidity matrix is isomorphic to the space of $\rho _{j}$-symmetric infinitesimal motions of $(G,p)$. Likewise, the cokernel of the $\rho _{j}$-symmetric orbit rigidity matrix is isomorphic to the space of $\rho _{j}$-symmetric self-stresses of $(G,p)$.

$\rho _{j}$-generic framework. The framework $(G,p)$ is $\rho _{j}$-generic if its orbit rigidity matrix has max rank over all $\Gamma$-symmetric frameworks with constraint graph $G$.

Theorems

Incidentally symmetric rigidity.

A Maxwell Condition for incidentally symmetric infinitesimal rigidity can be obtained for a $\Gamma$-symmetric framework $(G,p)$ as follows. Let ${\mathcal {T}}(G,p)$ denote the set of infinitesimal motions of the framework $(G,p)$. The set ${\mathcal {T}}(G,p)$ is a $(\tau \otimes P_{V})$-invariant subspace of $\mathbb {R} ^{d|V|}$, so consider the subrepresentation $(\tau \otimes P_{V})^{({\mathcal {T}})}$ of $\tau \otimes P_{V}$, i.e., the restriction of the homomorphism $\tau \otimes P_{V}$ to the subspace ${\mathcal {T}}(G,p)$. The subspace ${\mathcal {T}}(G,p)$ can be written as a direct sum of $(\tau \otimes P_{V})$-invariant subspaces $T_{1},\dots ,T_{m}$. Hence, if a $\Gamma$-symmetric framework is incidentally minimally rigid, then it must satisfy $dim(W_{i})=dim(V_{i})-dum(T_{i})$ for all $i\in \{1,\dots ,m\}$. These conditions can be written in terms of characters of representations of the group $\Gamma$. For such a representation $\pi$, its character is denoted by $\chi (\pi )$ and is a vector whose $i^{th}$ entry is the trace of $\pi (\gamma _{i})$, for some ordering $\gamma _{1},\dots ,\gamma _{|\Gamma |}$ of the elements of $\Gamma$.

Incidentally symmetric Maxwell Condition. If a framework $(G,p)$ is incidentally symmetric infinitesimally rigid in $d$-dimensions, then $\chi (P_{E})=\chi (\tau \otimes P_{V})-\chi \left((\tau \otimes P_{V})^{({\mathcal {T}})}\right)$.

This condition can be written in terms of the numbers of vertices and edges of a framework as follows. Let $V_{\gamma }$ and $E_{\gamma }$ be the vertices and edges fixed by the element $\gamma$ of $\Gamma$.

Alternate incidentally symmetric Maxwell Condition. If a framework $(G,p)$ is incidentally symmetric infinitesimally rigid in $d$-dimensions, then for each $\gamma$ in $\Gamma$, $|E_{\gamma }|=trace(\tau (\gamma ))\cdot |V_{\gamma }|-trace((\tau \otimes P_{V})^{({\mathcal {T}})}(\gamma ))$.

Let $C_{n}$ denote the rotational symmetry groups of order $n$, $C_{s}$ denote the reflection groups, and $C_{nv}$ denote the dihedral groups, see point groups and Schoenflies notation. Also, let $Id$ denote the identity element of these groups. The following table shows calculations of characters for the representations relevant to the Maxwell Condition.

	$Id$	$C_{2}$	$C_{n>2}$	$C_{s}$
${\mathcal {X}}(P_{E})$	$|E|$	$|E_{C_{2}}|$	$|E_{C_{n}}|$	$|E_{s}|$
${\mathcal {X}}(\tau \otimes P_{V})$	$2|V|$	$2|V_{C_{2}}|$	$2\left(\cos {\frac {2\pi }{n}}\right)|V_{C_{n}}|$	$0$
${\mathcal {X}}\left(\left(\tau \otimes P_{V}\right)^{({\mathcal {T}})}\right)$	$3$	$-1$	$2\cos {\frac {2\pi }{n}}+1$	$-1$

Incidentally symmetric rigidity is a generic property of $\Gamma$-symmetric graphs. There are only $5$ non-trivial symmetry groups for which there are incidentally symmetric minimally rigid frameworks in $2$-dimensions: $C_{2}$, $C_{3}$, $C_{s}$, and $C_{2v}$ and $C_{3v}$ of order $4$ and $6$. The following results give combinatorial characterizations for generically incidentally symmetric rigid graphs.

Theorem. Let $G=(V,E)$ be a $\mathbb {Z} _{2}$-symmetric graph with at least three vertices and with respect to $\theta :\mathbb {Z} _{2}\rightarrow Aut(G)$. Let $\gamma$ generate $\mathbb {Z} _{2}$ and let $\tau :\mathbb {Z} _{2}\rightarrow O(\mathbb {R} ^{2})$ be a homomorphism so that $\tau (\mathbb {Z} _{2})={\mathcal {C}}_{2}$. The following three statements are equivalent.

• $G$ is generically incidentally $\mathbb {Z} _{2}$-symmetric generically minimally rigid in $2$-dimensions and $G$ has a $2$-dimensional ${\mathcal {C}}_{2}$-symmetric framework;
• $G$ is a Laman graph with $|V_{{\mathcal {C}}_{2}}|=0$ and $|E_{{\mathcal {C}}_{2}}|=1$, i.e., no vertices and exactly one edge are fixed by any element of ${\mathcal {C}}_{2}$; and
• $G$ can be split into $3$ edge-disjoint trees $T_{1},T_{2},$ and $T_{3}$ such that (i) each vertex of $G$ is contained in exactly $2$ trees, (ii) no $2$ subtrees have the same span, (iii) $\theta (\gamma )T_{2}=T_{3}$, and (iv) $T_{0}$ is a spanning tree with $\theta (\gamma )T_{1}=T_{1}$.

Theorem. Let $G=(V,E)$ be a $\mathbb {Z} _{3}$-symmetric graph with at least three vertices and with respect to $\theta :\mathbb {Z} _{3}\rightarrow Aut(G)$. Let $\gamma$ generate $\mathbb {Z} _{3}$ and let $\tau :\mathbb {Z} _{3}\rightarrow O(\mathbb {R} ^{2})$ be a homomorphism so that $\tau (\mathbb {Z} _{3})={\mathcal {C}}_{3}$. The following three statements are equivalent.

• $G$ is generically incidentally $\mathbb {Z} _{3}$-symmetric minimally rigid in $2$-dimensions and $G$ has a $2$-dimensional ${\mathcal {C}}_{3}$-symmetric framework;
• $G$ is a Laman graph and $|V_{{\mathcal {C}}_{3}}|=0$, i.e., no vertices are fixed by any element of ${\mathcal {C}}_{3}$; and
• $G$ can be split into $3$ edge-disjoint trees $T_{1},T_{2},$ and $T_{3}$ such that (i) each vertex of $G$ is contained in exactly $2$ trees, (ii) no $2$ subtrees have the same span, and (iii) $\theta (\gamma )T_{i}=T_{i+1}$, for $i\in \{1,2,3\}$.

Theorem. Let $G=(V,E)$ be a $\mathbb {Z} _{2}$-symmetric graph with at least three vertices and with respect to $\theta :\mathbb {Z} _{2}\rightarrow Aut(G)$. Let $\gamma$ generate $\mathbb {Z} _{2}$ and let $\tau :\mathbb {Z} _{2}\rightarrow O(\mathbb {R} ^{2})$ be a homomorphism so that $\tau (\mathbb {Z} _{2})={\mathcal {C}}_{s}$. The following three statements are equivalent.

• $G$ is generically incidentally $\mathbb {Z} _{2}$-symmetric generically minimally rigid in $2$-dimensions and $G$ has a $2$-dimensional ${\mathcal {C}}_{s}$-symmetric framework;
• $G$ is a Laman graph with $|E_{{\mathcal {C}}_{s}}|=1$, i.e., exactly one edge is fixed by any element of ${\mathcal {C}}_{s}$; and
• $G$ can be split into $3$ edge-disjoint trees $T_{1},T_{2},$ and $T_{3}$ such that (i) each vertex of $G$ is contained in exactly $2$ trees, (ii) no $2$ subtrees have the same span, (iii) $\theta (\gamma )T_{1}=T_{1}$, and (iv) either either $\theta (\gamma )T_{2}=T_{3}$ or there exists an edge $(i,j)$ whose vertices are fixed by $\gamma$ with $\theta (\gamma )(T_{2}-i)=T_{3}$.

Analogous results for the dihedral groups are open problems.

Example. The frameworks in Figure 10 are $C_{s}$-symmetric. Let $G=(V,E)$ $G'=(V',E')$ be the graphs underlying these frameworks respectively. We have $|E_{C_{2}}|=3$ and $|E'_{C_{2}}|=2$, so neither framework is incidentally symmetric infinitesimally rigid.

File:Incidental-symmetric.jpg

Figure 11. Incidentally symmetric infinitesimally rigid frameworks where (a) is $C_{2}$-symmetric, (b) is $C_{3}$-symmetric, and (c) is $C_{s}$-symmetric. Removing the blue edge in each yields a framework with a fully symmetric infinitesimal motion.

Example. The frameworks in Figure 11 are incidentally symmetric infinitesimally rigid in $2$-dimensions with respect to the half-turn symmetry group $C_{2}$, the $3$-fold symmetry group $C_{3}$, and the reflection symmetry group $C_{s}$ respectively. The framework in Figure 10a has a single edge fixed by $C_{2}$, shown in blue, and no fixed vertices. The framework in Figure 10b has no vertices fixed by $C_{3}$. The framework in Figure 10c has a single edge fixed by $C_{2}$, shown in blue. Thus, these frameworks incidentally symmetric infinitesimally rigid in $2$-dimensions by the theorems above.

Theorem. Generically minimally rigid graphs in $2$-dimensions of the following types may be constructed from $K_{3}$ as follows.

• ${\mathcal {C}}_{3}$-symmetric: via a sequence of symmetric $0$- and $1$-extensions (i.e. symmetric Henneberg construction steps) and a symmetric $K_{3}$-addition operation that symmetrically connects each vertex of a $K_{3}$ graph to a vertex in the current graph;
• ${\mathcal {C}}_{2}$-symmetric: via a sequence of symmetric $0$- and $1$-extensions; and
• ${\mathcal {C}}_{s}$-symmetric: via a sequence of symmetric $0$- and $1$-extensions and symmetric $X$-replacements.

Fully symmetric rigidity.

Fully symmetric infinitesimal rigidity is a generic property of $\Gamma$-symmetric graphs. A Maxwell Condition can be obtained as follows. Let $({\tilde {G}},psi)$ be the quotient gain graph of $(G,p)$ and let $\theta$ be a free group action action of the vertices of $G$. Also, let ${\mathcal {T}}^{f}(G,p)$ and ${\mathcal {T}}^{f}\left(G,p,<{\tilde {E}}'>_{\psi ,{\tilde {u}}}\right)$ denote the set of trivial fully symmetric infinitesimal motions of $(G,p)$ and the subset of those motions that are $\left(<{\tilde {E}}'>_{\psi ,{\tilde {u}}}\right)$-symmetric, induced by the subset of edges ${\tilde {E}}'$ and a vertex ${\tilde {u}}$ incident on an edge in ${\tilde {E}}'$, respectively.

Fully symmetric Maxwell Condition. If a framework $(G,p)$ is fully symmetric infinitesimally rigid in $d$-dimensions and $G$ has at least $d$ vertices, then $({\tilde {G}},\psi )$ has a spanning subgraph $({\tilde {G}}'=({\tilde {V}}',{\tilde {E}}'),\psi )$ such that

• $|{\tilde {E}}'|=d|{\tilde {V}}|-dim({\mathcal {T}}^{f}(p))$
• for all ${\tilde {E}}''\subset {\tilde {E}}'$ and all ${\tilde {u}}\in {\tilde {V}}({\tilde {E}}'')$, $|{\tilde {E}}''|=d|{\tilde {V}}({\tilde {E}}'')|-dim\left({\mathcal {T}}^{f}\left(p,<{\tilde {E}}''>_{\psi ,{\tilde {u}}}\right)\right)$

The following results give combinatorial characterizations of certain types of generically incidentally symmetric rigid graphs. Consider a quotient gain graph $({\tilde {G}},\psi )$. A connected subset of edges ${\tilde {E}}'$ of ${\tilde {G}}$ is balanced if $<{\tilde {E}}'>_{\psi ,{\tilde {u}}}$ is the set containing only the identity element for some vertex ${\tilde {u}}$ incident on an edge on ${\tilde {E}}'$. A quotient gain graph is $(k,l,m)$-gain-sparse, where $m\leq l$, if all non-empty subsets of edges ${\tilde {E}}'$ of ${\tilde {G}}$ satisfy $|{\tilde {E}}'|\leq k|V({\tilde {E}}')|-m$, and all balanced subsets of edges ${\tilde {E}}''$ of ${\tilde {G}}$ satisfy $|{\tilde {E}}''|\leq k|V({\tilde {E}}'')|-l$; and $(k,l,m)$-gain-tight if, additionally, $|{\tilde {E}}|=k|{\tilde {V}}|-m$.

Theorem. Let $G=(V,E)$ be a $\mathbb {Z} _{n\geq 2}$-symmetric graph with respect to a free group action $\theta :\mathbb {Z} _{n}\rightarrow Aut(G)$ and $\tau :\mathbb {Z} _{n}\rightarrow O(\mathbb {R} ^{2})$. Then $G$ is generically fully $\mathbb {Z} _{n}$-symmetric rigid if and only if the quotient gain graph of $G$ has a $(2,3,1)$-gain-tight spanning subgraph.

Let $D_{2n}$ denote the dihedral group of order $2n$.

Theorem. Let $G=(V,E)$ be a $D_{2n}$-symmetric graph, for an odd integer $n\geq 3$, with respect to a free group action $\theta :D_{2n}\rightarrow Aut(G)$ and $\tau :D_{2n}\rightarrow O(\mathbb {R} ^{2})$, where $\tau (D_{2n})={\mathcal {C}}_{nv}$. Then $G$ is generically fully $\mathbb {D} _{2n}$-symmetric rigid if and only if the quotient gain of $G$ graph has a spanning subgraph with edge set ${\tilde {E}}'$ such that

• $|{\tilde {E}}'|=2|{\tilde {V}}|$
• for all non-empty subsets ${\tilde {E}}''\subset {\tilde {E}}'$, (i) ${\tilde {E}}''\leq 2|V({\tilde {E}}''|$ and (ii) if ${\tilde {E}}''$ is balanced, then ${\tilde {E}}''\leq 2|V({\tilde {E}}''|-3$; otherwise ${\tilde {E}}''\leq 2|V({\tilde {E}}''|-1$

Phase symmetric infinitesimal rigidity. Let $(G,p)$ be a $\mathbb {Z} _{k}$-symmetric framework with respect to a free group action $\theta :\mathbb {Z} _{k}\rightarrow Aut(G)$ and $\tau :\mathbb {Z} _{k}\rightarrow O(\mathbb {R} ^{2})$. $(G,p)$ is infinitesimally rigid if and only if it is $\rho _{j}$-symmetric infinitesimally rigid for all irreducible representations $\rho _{j}$ of $\Gamma$.

Phase symmetric Maxwell Condition. If $(G,p)$ is $\rho _{j}$-symmetric infinitesimally rigid, then the quotient gain graph $({\tilde {G}},\psi )$ has a spanning subgraph $({\tilde {G}}',\psi )$ such that

• for $k=2$, $({\tilde {G}}',\psi )$ is $(2,3,1)$-gain-tight if $j=0$ and $(2,3,2)$-gain-tight if $j=1$;
• for $k\geq 3$ and $j\in \{0,1,k-1\}$, $({\tilde {G}}',\psi )$ is $(2,3,1)$-gain-tight;
• for $k\geq 4$ and $j\notin \{0,1,k-1\}$, $({\tilde {G}}',\psi )$ is $(2,3,0)$-gain-tight.

Phase symmetric infinitesimal rigidity is a generic property of $\mathbb {Z} _{k}$-symmetric graphs. The following results give combinatorial characterizations of certain types of generically phase symmetric rigid graphs.

Theorem. A graph $G=(V,E)$ has a $\mathbb {Z} _{2}$-symmetric $\rho _{1}$-generic framework $(G,p)$, with respect to a free group action $\theta :\mathbb {Z} _{2}\rightarrow Aut(G)$ and $\tau :\mathbb {Z} _{2}\rightarrow O(\mathbb {R} ^{2})$, that is $\rho _{1}$-symmetric infinitesimally rigid if and only if the quotient gain graph of $G$ has a $(2,3,2)$-gain-tight spanning subgraph.

Theorem. A graph $G=(V,E)$ has a $\mathbb {Z} _{2}$-generic framework $(G,p)$, with respect to a free group action $\theta :\mathbb {Z} _{2}\rightarrow Aut(G)$ and $\tau :\mathbb {Z} _{2}\rightarrow O(\mathbb {R} ^{2})$, that is infinitesimally rigid if and only if the quotient gain graph of $G$ has a $(2,3,i)$-gain-tight spanning subgraph $({\tilde {G}}'_{i},\psi _{i})$, for each $i\in \{1,2\}$.

Theorem. A graph $G=(V,E)$ has a $\mathbb {Z} _{3}$-symmetric $\rho _{j}$-generic framework $(G,p)$, for $j\in \{0,1,2\}$, with respect to a free group action $\theta :\mathbb {Z} _{3}\rightarrow Aut(G)$ and $\tau :\mathbb {Z} _{3}\rightarrow O(\mathbb {R} ^{2})$, that is $\rho _{j}$-symmetric infinitesimally rigid if and only if the quotient gain graph of $G$ has a $(2,3,1)$-gain-tight spanning subgraph.

Theorem. A graph $G=(V,E)$ has a $\mathbb {Z} _{3}$-generic framework $(G,p)$, with respect to a free group action $\theta :\mathbb {Z} _{3}\rightarrow Aut(G)$ and $\tau :\mathbb {Z} _{3}\rightarrow O(\mathbb {R} ^{2})$, that is infinitesimally rigid if and only if the quotient gain graph of $G$ has a $(2,3,1)$-gain-tight spanning subgraph.

Periodic frameworks

This section concerns the rigidity of periodic frameworks.

Definitions.

Let $G$ be a $d$-periodic graph, i.e., an infinite $\Gamma$-symmetric graph such that $\Gamma$ is isomorphic to $\mathbb {Z} ^{d}$ and the quotient gain graph of $G$ is finite. Also, let $(G,p,L)$ be a $d$-periodic framework, where $p$ is an embedding of the vertices of $G$ in $d$-dimensions and $L:\Gamma \rightarrow {\mathcal {T}}_{d}$ is a faithful representation of $\Gamma$ that maps it to the group of $d$-dimensional translations. This framework satisfies $p_{i}+L(\gamma )=p_{\theta (\gamma )(i)},$ for all $\gamma$ in $\Gamma$ and points $p_{i}$.

For a set of vertex orbit representatives $v_{1},\dots ,v_{n}$ and the corresponding $m$ pairs of edge orbit representatives of the form $(v_{i},\theta (\gamma )v_{j})$ of $G$, let $\mu _{k}=L(\gamma _{k})$, for $k\in \{1,\dots ,d\}$, be $d$-dimensional translation vectors obtained from the standard basis $\gamma _{1},\dots ,\gamma _{d}$ of $\Gamma$. A $d$-dimensional translation vector corresponding $L(\alpha )$, for some $\alpha$ in $\Gamma$ can be written as a linear combination of the basis elements $\mu _{1},\dots ,\mu _{d}$ with coefficients $c_{\alpha ,1},\dots ,c_{\alpha ,d}$. This linear combination is denoted by $\mu (\alpha )$.

$d$-periodic infinitesimal motion. A $(dn+d^{2})$-dimensional vector $(p'_{1},\dots ,p'_{n},q_{1},\dots ,q_{d})$ is an infinitesimal motion of $(G,p,L)$ if for all edges of $G$ $\left((p_{j}+\mu (\alpha ))-p_{i}\right)\cdot \left((p'_{j}+q(\alpha )_{-}p_{i}\right)=0,$ for $\alpha =1,\dots ,m$ and where $q(\alpha )=\sum _{k=1}^{d}{c_{\alpha ,k}q_{k}}$.

As with infinitesimal motions of bar-joint frameworks, the system of equations for a $d$-periodic infinitesimal motion define the $d$-periodic rigidity matrix. A $d$-periodic framework is $d$-periodic generic if its $d$-periodic rigidity matrix has maximum rank over all $d$-periodic frameworks with the same constraint graph.

$d$-periodic infinitesimal rigidity. The framework $(G,p,L)$ is $d$-periodic infinitesimally rigid if all of its $d$-periodic infinitesimal motions are trivial.

Figure 12. (a) and (c) show portions of $2$-dimensions infinite periodic frameworks, and (b) and (d) show their respective quotient $\mathbb {Z} ^{2}$-gain graphs. The framework in (a) is infinitesimally flexible under a fully flexible lattice representation, and the framework in (b) is minimally rigid under a fixed lattice representation.

Theorems.

Note that a $d$-periodic framework $(G,p,L)$ defines a $d$-dimensional lattice, and hence $L(\mathbb {Z} ^{d})$ is a lattice representation. Motions of $d$-periodic frameworks must preserve periodicity of frameworks, but not necessarily of the corresponding lattices, i.e., the lattice representations can have varying levels of flexibility. A $d$-periodic framework with a fixed lattice has an infinitesimal motion if and only if it has a continuous motion . This result can be adapted for $d$-periodic frameworks with other types of lattices, such as a fixed lattice . The following Maxwell Conditions are based on the flexibility of the lattice.

$d$-periodic Maxwell Conditions. If the $d$-periodic framework $(G,p,L)$ is $d$-periodic infinitesimally rigid, then the quotient gain graph of $G$ has a spanning subgraph ${\tilde {G'}}=({\tilde {V}}',{\tilde {E}}')$ such that

• for a flexible $L(\mathbb {Z} ^{d})$, $|{\tilde {E}}'|=d|{\tilde {V}}'|+{d \choose 2}$;
• for translation vectors in $L(\mathbb {Z} ^{d})$ that can scale independently, $|{\tilde {E}}'|=d|{\tilde {V}}'|$; and
• for a fixed $L(\mathbb {Z} ^{d})$, $|{\tilde {E}}'|=d|{\tilde {V}}'|-d$.

The following results are combinatorial characterizations of certain classes of generically $d$-periodic infinitesimally rigid graphs. Consider the subgroup of $\mathbb {Z} ^{d}$ induced by a subset of edges ${\tilde {E}}'$ of a quotient gain graph. The $\mathbb {Z} ^{d}$-rank of ${\tilde {E}}'$, denoted by $k({\tilde {E}}')$, is size of the minimum generating set of this subgroup. Also, let $c({\tilde {E}}')$ denote the number of connected components of the subgraph induced by ${\tilde {E}}'$.

Theorem A $2$-periodic graph $G$ has a $2$-periodic generic framework $(G,p,L)$, with a flexible $L(\mathbb {Z} ^{2})$, that is $2$-periodic infinitesimally rigid if and only if the quotient gain graph of $G$ has a spanning subgraph ${\tilde {G'}}=({\tilde {V}}',{\tilde {E}}')$ such that

• $|{\tilde {E}}'|=2|{\tilde {V}}'|+1$;
• for all subsets ${\tilde {E}}''\subset {\tilde {E}}'$, $|{\tilde {E}}''|\leq 2|V({\tilde {E}}'')|-3+2k({\tilde {E}}'')-2(c({\tilde {E}}'')-1)$.

Theorem A $2$-periodic graph $G$ has a $2$-periodic generic framework $(G,p,L)$, with a non-singular and fixed $L(\mathbb {Z} ^{2})$, that is $2$-periodic infinitesimally rigid if and only if the quotient gain graph of $G$ has a spanning subgraph ${\tilde {G'}}=({\tilde {V}}',{\tilde {E}}')$ such that

• $|{\tilde {E}}'|=2|{\tilde {V}}'|-2$;
• for all subsets ${\tilde {E}}''\subset {\tilde {E}}'$, $|{\tilde {E}}''|\leq 2|V({\tilde {E}}'')|-2$; and
• for all subsets ${\tilde {E}}''\subset {\tilde {E}}'$ with $\mathbb {Z} ^{2}$-rank of $0$, $|{\tilde {E}}''|\leq 2|V({\tilde {E}}'')|-3$.

Rigidity under polyhedral norms

This section concerns the rigidity of bar-joint frameworks under various polyhedral norms, i.e., a norm on $\mathbb {R} ^{2}$ whose unit ball is a convex polytope.

Definitions

The rigidity map is defined analogously to the Euclidean case. In the Euclidean case, the rigidity map is differentiable at any point corresponding to a framework $(G,p)$, but this is not the case for general polyhedral norms. Below, $(G,p)$ denotes a $d$-dimensional bar-joint framework under some polyhedral norm $\|\cdot \|_{\mathcal {P}}$.

Theorem. The rigidity map is differentiable at a framework $(G,p)$ if and only if the vector $p_{u}-p_{v}$ lies in the conical hull of exactly one facet of the polytope ${\mathcal {P}}$, for each edge $(u,v)$ of $G$.

Well-positioned framework. A framework $(G,p)$ is well-positioned if it is a differentiable point of the rigidity map.

The differential of the rigidity map at a well-positioned framework $(G,p)$ admits a matrix representation.

Rigidity matrix. The rigidity matrix $R(G,p)$ of a well-positioned $d$-dimensional framework $(G=(V,E),p)$ is an $|E|\times d|V|$ matrix with a row for each edge of $G$. For a row corresponding to the edge $(u,v)$, all entries are $0$ except in the columns corresponding to the vertices $u$ and $v$, which are ${\hat {F}}$ and $-{\hat {F}}$ respectively, where $F$ is the unique facet of the poltyope ${\mathcal {P}}$ whose conical hull contains the vectur $p_{u}-p_{v}$ and ${\hat {F}}$ is the extreme point of $F$ in the polar set of ${\mathcal {P}}$.

Regular framework. A framework $(G,p)$ is regular if it is well-positioned and its rigidity matrix has maximum rank over all well-positioned frameworks.

In the Euclidean case, regular frameworks are generic and form an open and dense set in $d$-dimensions. For general polyhedral norms, the set of regular frameworks is open in $d$-dimensions, but not dense.

Theorems

File:Polyhedral.jpg

Figure 13. (a) and (c) show $2$-dimensional frameworks under the norms in (b) and (d) respectively, where (d) is the $l_{\infty }$-norm. The edges of each framework are partitioned by the conic hulls of the polyhedral faces that contain them. For the framework in (a), the solid black edges, gray edges, and dashed edges, are contained in the conic hulls of the faces $F_{1}$, $F_{2}$, and $F_{3}$ respectively. For the framework in (c), the solid black edges and gray edges are contained in the conic hulls of the faces $F_{1}$ and $F_{2}$ respectively.

As in the Euclidean case, the kernel of the rigidity matrix, for a well-positioned framework $(G,p)$, is the space of infinitesimal flexes of $(G,p)$. Furthermore, a framework has an infinitesimal motion if and only if it has a continuous motion .

Theorem. For a well-positioned $d$-dimensional framework $(G,p)$,

• $rank(R(G,p))\leq d|V|-d$; and
• $(G,p)$ is rigid in $d$-dimensions if and only if $rank(R(G,p))=d|V|-d$.

The change to $d$ from the usual ${d+1 \choose 2}$ in the above theorem is because rotations are not trivial motions under general polyhedral norms.

Maxwell Condition. If a graph $G=(V,E)$ has a well-positioned $d$-dimensional framework $(G,p)$ that is rigid in $d$-dimensions, then $|E|\geq d|V|-d$. Furthermore, if $(G,p)$ is minimally rigid, then $G$ is $(d,d)$-tight.

Rigidity for the $l_{\infty }$-norm has a complete combinatorial characterization. Let ${\mathcal {F}}$ be the set of facets of a polytope ${\mathcal {P}}$ and let $(G=(V,E),p)$ be a framework. Consider the map, or coloring, $c:E\rightarrow {\mathcal {F}}$ that assigns the edge $(u,v)$ of $G$ the facet $F$ if the vector $p_{u}-p_{v}$ is in the conic hull of $F$. A subgraph of $G$ is monochrome if all its edges have the same color.

Theorem. For a $d$-dimensional well-positioned framework $(G,p)$ under the $l_{\infty }$-norm, the following statements are equivalent:

• $(G,p)$ is minimally rigid in $d$-dimensions
• Each maximal monochrome subgraph of $G$ spans $G$

Theorem. For a graph $G$, the following statements are equivalent:

• $G$ has a well-positioned $2$-dimensional framework $(G,p)$ that is minimally rigid in $2$-dimensions;
• $G$ is $(2,2)$-tight; and
• $G$ is the union of two edge-disjoint spanning trees.

Example. Consider the framework in Figure 13c. The gray maximal monochrome subgraph does not span the entire graph, so the framework is not rigid by the theorem above. However, the underlying graph is $(2,2)$-tight, so it is generically minimally rigid in $2$-dimensions. Thus, this particular framework is not regular. By the same reasoning, the graph underlying the framework in Figure 13a is generically minimally rigid in $2$-dimensions, and has a well-positioned minimally rigid framework. Additionally, the framework in Figure 13a is minimally rigid.

Theorem. If a graph $G$ has a $d$-dimensional framework $(G,p)$ that is rigid in $d$-dimensions, then $G$ is connected and any subgraph $G'$ obtained by removing fewer than $d$ maximal monochrome subgraphs of $G$ is connected and spans $G$.

Theorem. If a graph $G$ has a well-positioned $d$-dimensional framework $(G,p)$ that is minimally rigid in $d$-dimensions if and only if each maximal monochrome subgraph of $G$ is a spanning tree of $G$.

Symmetry theorems.

Let $G$ be a graph with a well-positioned $d$-dimensional $\Gamma$-symmetric framework $(G,p)$ such that $\Gamma$ has a free group action on the vertices of $G$. The maximal monochrome subgraphs of $G$ are also $\Gamma$-symmetric, and so the induced maximal monochrome subgraphs of the quotient gain graph $({\tilde {G}},\psi )$ of $G$ are edge-disjoint.

Theorem. If $\Gamma$ is the half-turn rotational symmetry group or the reflection symmetry group with respect to a coordinate axis, then $(G,p)$ is rigid in $d$-dimensions if and only if the induced maximal monochrome subgraphs of the quotient gain graph of $G$ contain connected unbalanced spanning map subgraphs.