Generic Rigidity with Forced Symmetry and Sparse Colored Graphs

Abstract

We review some recent results in the generic rigidity theory of planar frameworks with forced symmetry, giving a uniform treatment to the topic. We also give new combinatorial characterizations of minimally rigid periodic frameworks with fixed-area fundamental domain and fixed-angle fundamental domain.

1 Introduction

The Maxwell-Laman Theorem is the prototypical result of combinatorial rigidity theory.

Theorem 1 ([19, 29]).

A generic bar-joint framework in the plane is minimally rigid if and only if the graph defined by the frameworks edges has n vertices $m = 2n - 3$ edges, and, for all subgraphs on n ^′ vertices and m ^′ edges, $m^{{\prime}}\leq 2n^{{\prime}}- 3$ .

The key feature of this, and all such “Maxwell-Laman-type results” is that, for almost all geometric data, rigidity is determined by the combinatorial type and can be decided by efficient combinatorial algorithms.

1.1 Some Generalizations

Finding generalizations of the Maxwell-Laman Theorem has been the motivation for a lot of progress in the field. The body-bar [49], body-bar-hinge [49, 51], and panel-hinge [17] frameworks have a rich generic theory in all dimensions. Here the “sparsity counts” are of the form $m^{{\prime}}\leq Dn^{{\prime}}- D$, where D is the dimension of the d-dimensional Euclidean group. On the other hand, various elaborations of the planar bar-joint model via pinning [6, 22, 35], slider-pinning [18, 46], direction-length frameworks [44], and other geometric restrictions like incident vertices [8] or, of more relevance here symmetry [41, 42], have all shed more light on the Maxwell-Laman Theorem itself.

In another direction, various families of graphs and hypergraphs defined by heriditary sparsity counts of the form $m^{{\prime}}\leq kn^{{\prime}}-\ell^{{\prime}}$ have been studied in terms of combinatorial structure [20], inductive constructions [7, 20], sparsity-certifying decompositions [45, 51] and linear representability [47], [52, Appendix A] properties. Running through much of this work is a matroidal perspective first introduced by Lovász-Yemini [23].

While much is known about (k, ℓ)-sparse graphs and hypergraphs, the parameter settings that yield interesting rigidity theorems seem to be somewhat isolated, despite the uniform combinatorial theory and many operations connecting different sparsity families.

1.2 Forced Symmetry

For the past several years, the rigidity and flexibility of frameworks with additional symmetry has received much attention,¹ although it also goes back further. Broadly speaking, there are two approaches to this: incidental symmetry, in which one studies a framework that may move in unrestricted ways but starts in a symmetric position [10, 15, 16, 32, 41, 42]; and forced symmetry [4, 24–26, 37, 39] where a framework must maintain symmetry with respect to a specific group throughout its motion. Forced symmetry is particularly useful as a way to study infinite frameworks² arising in applications to crystallography [36, 50].

In a sequence of papers [24–26], we pioneered much of the generic and combinatorial rigidity theory for the forced-symmetric frameworks in the plane. The basic setup we consider is as follows: we are given a group Γ that acts discretely on the plane by Euclidean isometries, a graph $\tilde{G} = (\tilde{V },\tilde{E})$, and a Γ-action $\varphi$ on $\tilde{G}$ with finite quotient that is free on the vertices and edges. A (realized) Γ-framework $\tilde{G}(\mathbf{p},\varPhi )$ is given by a point set $\mathbf{p} = (\mathbf{p}_{i})_{i\in \tilde{V }}$ and a representation Φ of Γ by Euclidean isometries, with the compatibility condition

$$\displaystyle{ \mathbf{p}_{\gamma \cdot i} =\varPhi (\gamma ) \cdot \mathbf{p}_{i} }$$

(1)

holding for all γ ∈ Γ and $i \in \tilde{ V }$.

Intuitively, the allowed continuous motions through $\tilde{G}(\mathbf{p},\varPhi )$ are those that preserve the lengths and connectivity of the bars, and symmetry with respect to Γ, but the particular representation Φ is allowed to flex. When the only allowed motions are induced by Euclidean isometries, a framework is rigid, and otherwise it is flexible.

The combinatorial model for Γ-frameworks is colored graphs, which we describe in Sect. 2. These efficiently capture some canonical Γ-framework invariants relating to how much flexibility from the group representation Φ a sub-framework constrains. Our combined theorems can be described uniformly as follows:

Theorem 2 ([24–26]).

Let Γ be one of:

• $\mathbb{Z}^{2}$ , acting on the plane by translation

• $\mathbb{Z}/k\mathbb{Z}$ , for $k \in \mathbb{N}$ , k ≥ 2 acting on the plane by an order k rotation around the origin

• $\mathbb{Z}/2\mathbb{Z}$ , acting on the plane by a reflection

• A crystallographic group generated by translations and a rotation.

A generic Γ-framework $\tilde{G}(\mathbf{p},\varPhi )$ is minimally rigid if and only if the associated colored quotient graph $(G,\boldsymbol{\gamma })$ has n vertices, m edges and:

• $m = 2n + \text{teich}_{\Gamma }(\varGamma ) -\text{cent }(\varGamma )$

• For all subgraphs G ^′ on n ^′ vertices, m ^′ edges, with connected components G _i that have ρ-image Γ _i,

  $$\displaystyle{ m^{{\prime}}\leq 2n^{{\prime}} + \text{teich}_{ \Gamma }(\varLambda (G^{{\prime}})) -\sum _{ i}\text{cent}(\varGamma _{i}^{{\prime}}) }$$

  (2)

  where Λ(G ^′ ) is the translation subgroup associated with $\varGamma _{i}^{{\prime}}$ .

(See Sect. 2 for definitions of $\text{teich}_{\Gamma }$ and cent.) Theorem 2 gives a generic rigidity theory that is: (1) Combinatorial; (2) Computationally tractable; (3) Applicable to almost all frameworks; (4) Applicable to a small geometric perturbation of all frameworks. In other words, it carries all of the key properties of the Maxwell-Laman-Theorem to the forced symmetry setting.

1.3 Results and Roadmap

The classes of colored graphs appearing in Theorem 2 are a new, non-trivial, extension of the (k, ℓ)-sparse families that had not appeared before. The proof of Theorem 2 relies on a direction network method (cf. [46, 51]), and the papers [24–26] develop the required combinatorial theory for direction networks. In this paper, we focus more on frameworks, describing the colored graph invariants that correspond to “Maxwell-type heuristics” and showing how to explicitly compute them. Additionally, we study periodic frameworks in a bit more detail, and derive several new consequences of Theorem 2: conditions for a periodic framework to fix the representation of $\mathbb{Z}^{2}$ (Propositions 5 and 9), and, as a consequence, the Maxwell-Laman-type Theorem 4 for periodic frameworks with fixed area fundamental domain.

1.4 Some Related Works

We remark that Theorem 2 has subsequently been shown to hold in the case where Γ is any dihedral group of order 2k where k is odd [14]. From examples in the same preprint, it appears that the above heriditary sparsity condition, while necessary, fails to be sufficient when k is even. Another subsequent preprint of note by Tanigawa provides somewhat different characterizations of generic rigidity for the above frameworks in Theorem 2 when Γ is orientation-preserving [48]. Note that all these results are restricted to the plane, and in fact the problem of characterizing generic rigidity of symmetric bar-joint frameworks in higher dimensions is no easier than that in the nonsymmetric setting, a difficult and unsolved problem. However, some partial results in the periodic case in higher dimensions have been obtained [5].

1.5 Notation and Terminology

We use some standard terminology for (k, ℓ)-sparse graphs: a finite graph G = (V, E) is (k,ℓ)-sparse if for all subgraphs on n ^′ vertices and m ^′ edges, $m^{{\prime}}\leq kn^{{\prime}}-\ell$. If equality holds for all of G, then G is a (k,ℓ)-graph; a subgraph for which equality holds is a (k,ℓ)-block and maximal (k, ℓ)-blocks are (k,ℓ)-components. Edge-wise minimal violations of (k, ℓ)-sparsity are (k, ℓ)-circuits. If G contains a (k, ℓ)-graph as a spanning subgraph it is (k,ℓ)-spanning. A (k,ℓ)-basis of G is a maximal subgraph that is (k, ℓ)-sparse. We refer to (2, 3)-sparse graphs by their more conventional name: Laman-sparse graphs.

In the sequel, we will define a variety of hereditarily sparse colored graph families. We generalize the concepts of “sparse”, “block”, “component”, “basis” and “circuit” in the natural way for any family of colored graphs defined by a sparsity condition.

2 The Model and Maxwell Heuristic

We now briefly review the degree of freedom heuristic that leads to the sparsity condition (2). As is standard, we begin with the desired form:

$$\displaystyle{ \#(\text{constraints}) \leq \#(\text{total d.o.f.}) - \#(\text{trivial motions}) }$$

(3)

What distinguishes the forced symmetric setting is that the r.h.s. depends, in an essential way, on the representation Φ of the symmetry group. Thus, we modify (3) to

$$\displaystyle{ \#(\text{constraints}) \leq \#(\text{total non-trivial d.o.f.}) - \#(\mbox{ rigid motions preserving $\varPhi $}) }$$

(4)

2.1 Flexibility of Symmetry Groups and Subgroups

Let Γ be a group as in Theorem 2. We define the representation space Rep(Γ) to be the set of all faithful representations Φ of Γ by Euclidean isometries. The Teichmüller space ³ Teich(Γ) is the quotient Rep(Γ)∕Euc(2) of the representation space by Euclidean isometries. We define teich(Γ) to be the dimension of Teich(Γ). For frameworks, the Teichmüller space plays a central role, since teich(Γ) gives the total number of non-trivial degrees of freedom associated with representations of Γ.

Now let Γ ^′ < Γ be a subgroup of Γ. The restricted Teichmüller space $\text{Teich}_{\Gamma }(\varGamma ^{{\prime}})$ is the image of the restriction map from Γ → Γ ^′ modulo Euclidean isometries. Equivalently it is the space of representations of Γ ^′ that extend to representations of Γ. Its dimension is defined to be $\text{teich}_{\Gamma }(\varGamma ^{{\prime}})$.

The invariant $\text{teich}_{\Gamma }(\varGamma ^{{\prime}})$ measures how much of the flexibility of Γ can be “seen” by Γ ^′. In general, the restricted Teichmüller space of Γ ^′ is not the same as its (unrestricted) Teichmüller space. For instance, the Teichmüller space $\text{Teich}(\mathbb{Z}^{2})$ has dimension 3, but the restricted Teichmüller space $\text{Teich}_{\Gamma }(\mathbb{Z}^{2})$ has dimension 1 if Γ contains a rotation of order 3.

2.2 Isometries of the Quotient

Now let Φ be a representation of Γ. The centralizer of Φ is the subgroup of Euclidean isometries commuting with Φ(Γ). We define cent(Γ) to be the dimension of the centralizer, which is independent of Φ (see e.g. [24, Lemma 6.1]). An alternative interpretation of the centralizer is that it is the isometry group of the quotient orbifold $\mathbb{R}^{2}/\varGamma$.

2.3 Colored Graphs

The combinatorial model for a Γ-framework is a colored graph $(G,\boldsymbol{\gamma })$,⁴ which is a finite, directed graph G = (V, E) and an assignment $\boldsymbol{\gamma }= (\gamma _{ij})_{ij\in E}$ of a group element in Γ to each edge of G. The correspondence between colored graphs $(G,\boldsymbol{\gamma })$ and graphs with a Γ-action $(\tilde{G},\varphi )$ is a straightforward specialization of covering space theory, and we have described the dictionary in detail in [24, Section 9]. The important facts are:

• The data $(\tilde{G},\varphi )$ and a selection of a representative from each vertex and edge orbit determine a colored graph $(G,\boldsymbol{\gamma })$.

• Each colored graph $(G,\boldsymbol{\gamma })$ lifts to a graph $\tilde{G}$ with a free Γ-action by a natural construction.

Together these mean that the colored graph $(G,\boldsymbol{\gamma })$ captures all the information in $(\tilde{G},\varphi )$.

2.4 The Homomorphism ρ

Let $(G,\boldsymbol{\gamma })$ be a connected colored graph, and select a base vertex b of G. The coloring on the edges then induces a natural homomorphism $\rho:\pi _{1}(G,b) \rightarrow \varGamma$. For a closed path P defined by the sequence of edges $bi_{2},i_{2}i_{3},\ldots,i_{\ell-1}b$, we have

$$\displaystyle{\rho (P) =\gamma _{bi_{2}}\gamma _{i_{2}i_{3}}\ldots \gamma _{i_{\ell-1}b},}$$

where γ _ji is taken to be $\gamma _{ij}^{-1}$. The key properties of ρ are [24, Lemmas 12.1 and 12.2]:

• The quantities $\text{teich}_{\Gamma }(\rho (\pi _{1}(G,b)))$ and cent(ρ(π ₁(G, b))) depend only on the lift $(\tilde{G},\varphi )$, so, in particular, they are independent of the choice of b.

• If $G_{1},G_{2},\ldots,G_{c}$, are the connected components of a disconnected colored graph $(G,\boldsymbol{\gamma })$, there is a well-defined translation subgroup Λ(G) of G.

2.5 Derivation of the Maxwell Heuristic

We are now ready to derive the degree of freedom heuristic for Γ-frameworks. Let $(G,\boldsymbol{\gamma })$ be a Γ-colored graph with n vertices, m edges, connected components $G_{1},G_{2},\ldots,G_{i}$, with ρ-images $\varGamma _{i}^{{\prime}}$. We fill in the template (4) for the associated Γ-framework $\tilde{G}(\mathbf{p},\varPhi )$:

Non-trivial degrees of freedom. There are two sources of flexibility:

• (A) The group representation Φ has, by definition, $\text{teich}_{\Gamma }(\varLambda (G))$ degrees of freedom, up to Euclidean isometries. These are the non trivial degrees of Φ “seen” by G.

• (B) The coordinates of the vertices are determined by the location of one representative of each Γ-orbit and Φ. There are n such orbits, for a total of 2n degrees of freedom

Here is the guiding intuition for (A). We want to understand how the edge lengths can constrain the representation Φ. It is intuitively clear that if there is no pair of points $\tilde{\mathbf{p}}_{i}$ and $\tilde{\mathbf{p}}_{\gamma \cdot i}$ in the same Γ-orbit that are also connected in the lift $(\tilde{G},\varphi )$, the framework cannot constrain Φ at all. Thus, we are interested in accounting for constraints arising from paths in $(\tilde{G},\varphi )$ between pairs of points $\tilde{\mathbf{p}}_{i}$ and $\tilde{\mathbf{p}}_{\gamma \cdot i}$; in $(G,\boldsymbol{\gamma })$, this corresponds to a closed path P with ρ(P) = γ.

This reasoning leads us to consider $\text{teich}_{\Gamma }(\cdot )$ of a subgroup generated by the ρ-images of some closed paths in $(G,\boldsymbol{\gamma })$. After some technical analysis, the correct subgroup is discovered to be Λ(G).

Rigid motions independent of Φ. For each connected component of $\tilde{G}(\mathbf{p},\varPhi )$ induced by G _i : there is a $\text{cent}(\varGamma _{i}^{{\prime}})$-dimensional space of these for each G _i , since any element of the centralizer of $\varGamma _{i}^{{\prime}}$ preserves all the edge lengths and compatibility with Φ. Because the components are disconnected, these motions are independent of each other.

3 Periodic Frameworks

A Γ-framework with symmetry group $\mathbb{Z}^{2}$ is called a periodic framework [4]. In this section, we specialize (2) to this case, and relate it to an alternate counting heuristic from [26, Section 3].

3.1 Invariants for $\mathbb{Z}^{2}$

Representations of $\mathbb{Z}^{2}$ by translations have very simple coordinates: they are given by mapping each of the generators (1, 0) and (0, 1) to a vector in $\mathbb{R}^{2}$. Thus, the space of (possibly degenerate) representations is isomorphic to the space of 2 × 2 matrices with real entries. Given such a matrix L and $\gamma \in \mathbb{Z}^{2}$, the translation representing γ is simply L ⋅ γ. Because of this identification, we denote realizations of periodic frameworks by $\tilde{G}(\mathbf{p},\mathbf{L})$, and call L the lattice representation.

Subgroups of $\mathbb{Z}^{2}$ are always generated by k = 0, 1, 2 linearly independent vectors; given a subgroup, we define its rank to be the minimum size of a generating set. To specify a representation of a subgroup $\varGamma ^{{\prime}} < \mathbb{Z}^{2}$, we assign a vector in $\mathbb{R}^{2}$ to each of the k generators of Γ ^′. Such a representation always extends to a faithful representation of $\mathbb{Z}^{2}$. Thus, we see that the dimension of the space of representations of $\mathbb{Z}^{2}$ restricted to Γ ^′ is 2k.

The quotient of the representation space of $\mathbb{Z}^{2}$ by Euc(2) is also straightforward to describe. Each point has a representative L such that L ⋅ (1, 0) = (λ, 0) for some real scalar λ. From this, we get:

Proposition 1.

Let $\varGamma ^{{\prime}} < \mathbb{Z}^{2}$ be a subgroup of $\mathbb{Z}^{2}$ with rank k. Then $\text{teich}_{\mathbb{Z}^{2}}(\varGamma ^{{\prime}}) =\max \{ 2k - 1,0\}$ .

Finally, we compute the dimension of the centralizer of a subgroup Γ ^′. If Γ ^′ is trivial, then the centralizer is the entire 3-dimensional Euclidean group. If Γ ^′ is rank 1, then it is represented by a translation $t_{1}(\mathbf{p}) = \mathbf{p} + \mathbf{t}_{1}$, which commutes with other translations and reflections or glides fixing a line in the direction t ₁. For the rank 2 case, the centralizer is just the translation subgroup of Euc(2). We now have:

Proposition 2.

Let $\varGamma ^{{\prime}} < \mathbb{Z}^{2}$ be a subgroup of $\mathbb{Z}^{2}$ with rank k. Then

$$\displaystyle{\text{cent}(\varGamma ^{{\prime}}) = \left \{\begin{array}{@{}l@{\quad }l@{}} 3\quad &\mbox{ if $k$ = 0} \\ 2\quad &\mbox{ if $k \geq 1$} \end{array} \right.}$$

3.2 The Homomorphism ρ for $\mathbb{Z}^{2}$

Now we turn to associating a colored graph $(G,\boldsymbol{\gamma })$ with a subgroup of $\mathbb{Z}^{2}$. This is simpler than the general case because $\mathbb{Z}^{2}$ is abelian, so we may define it as a map $\rho: H_{1}(G, \mathbb{Z}) \rightarrow \mathbb{Z}^{2}$, as was done in [26]. Here are the relevant facts:

Proposition 3.

Let $(G,\boldsymbol{\gamma })$ be a colored graph. Then the rank of the ρ-image is determined by the values of ρ on any homology (alternatively, cycle) basis of G, and thus ρ is well-defined when G has more than one connected component.

3.3 Colored-Laman Graphs

With Propositions 1–3, the colored graph sparsity counts (2) from Theorem 2 specializes, for a $\mathbb{Z}^{2}$-colored graph to:

$$\displaystyle{ m^{{\prime}}\leq 2n^{{\prime}} +\max \{ 2k - 1,0\} - 3c_{ 0}^{{\prime}}- 2c_{ \geq 1}^{{\prime}} }$$

(5)

where k is the rank of the $\mathbb{Z}^{2}$-image of $(G,\boldsymbol{\gamma })$, $c_{0}^{{\prime}}$ is the number of connected components with trivial $\mathbb{Z}^{2}$-image and $c_{\geq 1}^{{\prime}}$ is the number of connected components with non-trivial $\mathbb{Z}^{2}$-image (i.e., k ≥ 1). This gives a matroidal family [26, Lemma 7.1], and we define the bases to be colored-Laman graphs.

3.4 An Alternative Sparsity Function

A slightly different counting heuristic for a periodic framework with colored quotient graph $(G,\boldsymbol{\gamma })$ having n vertices, m edges, c connected components and ρ-image with rank k is as follows:

• There are 2n variables specifying the points, and 2k variables giving a representation of the ρ-image.

• To remove Euclidean isometries that move the points and the lattice representation together, we pin down a connected component.

• Each of the remaining connected components may translate independently of each other.

Adding up the degrees of freedom and subtracting three degrees of freedom for pinning down one connected components and two each for translations of each other connected component yields the sparsity condition from [26, Section 3, p. 14]

$$\displaystyle{ m^{{\prime}}\leq 2(n^{{\prime}} + k) - 3 - 2(c^{{\prime}}- 1) }$$

(6)

which is equivalent to the colored-Laman counts (5) by the following.

Proposition 4.

Let $(G,\boldsymbol{\gamma })$ be a $\mathbb{Z}^{2}$ -colored graph. Then $(G,\boldsymbol{\gamma })$ satisfies(5) if and only if it satisfies (6) .

Proof.

For convenience, we define the two functions:

$$\displaystyle\begin{array}{rcl} f(G)& =& 2n +\max \{ 2k - 1,0\} - 3c_{0} - 2c_{\geq 1}{}\end{array}$$

(7)

$$\displaystyle\begin{array}{rcl} g(G)& =& 2(n + k - c) - 1{}\end{array}$$

(8)

where g is easily seen to be equal to the r.h.s. of (6). The definitions imply readily that f(G) ≤ g(G), with equality when there is either one connected component in G or all connected components have ρ-images with rank at least one. Thus, it will be sufficient to show that, if $(G,\boldsymbol{\gamma })$ has n vertices, m edges, and ρ-image of rank k, and it is minimal with the property that $f(G) = m - 1$, then $g(G) = m - 1$.

Let $(G,\boldsymbol{\gamma })$ have these properties, and let G have connected components G _i with, n _i vertices, m _i edges, and ρ-images of rank k _i . The minimality hypothesis implies that for any G _i , the number of edges in $G\setminus G_{i}$ is

$$\displaystyle{ m - m_{i} \leq f(G\setminus G_{i}) }$$

(9)

but, if k _i is zero, the rank of the ρ-image of G∖ G _i is k, and $m_{i} \leq 2n_{i} - 3$. Computing, we find that

$$\displaystyle\begin{array}{rcl} m - m_{i}& \geq & 2n +\max \{ 2k - 1,0\} - 3c_{0} - 2c_{\geq 1} + 1 - 2n_{i} + 3 {}\\ & & = 2(n - n_{i}) +\max \{ 2k - 1,0\} - 3(c_{0} - 1) - 2c_{\geq 1} + 1 {}\\ & & = f(G\setminus G_{i}) + 1 {}\\ \end{array}$$

which is a contradiction to (9). We conclude that either there is one connected component in G or that none of the k _i were zero. In either of these cases f(G) = g(G), which completes the proof. □ 

3.5 Example: Disconnected Circuits

The proof of Proposition 4 generalizes the folklore fact that, for Laman rigidity, we get the same class of graphs from “$m^{{\prime}}\leq 2n^{{\prime}}- 3$” and the more precise “$m^{{\prime}}\leq 2n^{{\prime}}- 3c^{{\prime}}$”. In the periodic setting the additional precision is required:

• There are periodic frameworks with dependent edges in different connected components of the colored quotient graph [26, Figure 20].

• There are connected $\mathbb{Z}^{2}$-colored graphs that are not colored-Laman sparse but satisfy (5) for all induced or connected subgraphs [26, Figure 8].

The intuition leading to the discovery of (6) is that connected components of a periodic framework’s colored graph interact via the representation L when they have the same ρ-image.

3.6 Example: Disconnected Minimally Rigid Periodic Frameworks

Another phenomenon associated with periodic rigidity that is not seen in finite frameworks is that although the colored quotient graph $(G,\boldsymbol{\gamma })$ must be connected [26, Lemmas 4.2 and 7.3], the periodic framework $\tilde{G}(\mathbf{p},\varPhi )$ does not need to be as in [26, Figure 9]. To see this, we simply note that (5) depends only on the rank of the ρ-image, which is unchanged by multiplying the entries of the colors γ _ij on the edges $(G,\boldsymbol{\gamma })$ by an integer q. On the other hand, this increases the number of connected components by a factor of q ². There is no paradox because periodic symmetry is being forced: once we know the realization of one connected component of $\tilde{G}(\mathbf{p},\varPhi )$, we can reconstruct the rest of them from the representation Φ of $\mathbb{Z}^{2}$.

3.7 Conditions for Fixing the Lattice

The definition of rigidity for periodic frameworks implies that a rigid framework fixes the representation L of $\mathbb{Z}^{2}$ up to a Euclidean isometry. It then follows that any periodic framework with a non-trivial rigid component must do the same. However, this is not the only possibility. Figure 1 shows a framework without a rigid component that fixes the lattice representation and its associated colored graph. The framework’s non-trivial motion is a rotation of each of the triangles. This example is an instance of a more general phenomenon.

Fig. 1

A flexible periodic framework that determines the lattice representation: (a) the associated colored graph; (b) the periodic framework

Proposition 5.

Suppose that $(G,\boldsymbol{\gamma })$ is a colored graph such that an associated generic periodic framework $\tilde{G}(\mathbf{p},\varPhi )$ fixes the lattice representation. Then $(G,\boldsymbol{\gamma })$ contains a subgraph G ^′ with m edges and rank 2 ρ-image such that m = f(G ^′ ), where f is the sparsity function defined in (7) .

Proof.

We may assume without loss of generality that $(G,\boldsymbol{\gamma })$ is colored-Laman sparse. Let $\eta \in \mathbb{Z}^{2}$ be a vector that is linearly independent of any ρ-image of any rank 1 subgraph of $(G,\boldsymbol{\gamma })$. Such an η exists since there are only finitely many subgraphs of $(G,\boldsymbol{\gamma })$. Because $\tilde{G}(\mathbf{p},\varPhi )$ is generic and fixes the lattice, Theorem 2 implies that adding a self-loop ℓ with color η leads to a colored graph that is not colored-Laman-sparse. This implies that there is a minimal subgraph $(G^{{\prime}}+\ell,\boldsymbol{\gamma })$ of $(G+\ell,\boldsymbol{\gamma })$ that is not colored-Laman sparse. The ρ-image of G ^′ must be rank 2 because, if it were not, the rank of the ρ-image of G ^′ + ℓ would be strictly larger than that of G ^′, thus $(G^{{\prime}}+\ell,\boldsymbol{\gamma })$ would again be colored-Laman sparse. It follows that G ^′ satisfies the conclusion of the Proposition. □ 

4 Specializations of Periodic Frameworks

Because Theorem 2 is quite general, we can deduce Laman-type theorems for many restricted versions of periodic frameworks from Theorem 2. In this section, we describe three of these in detail and discuss connections with some others.

4.1 The Periodic Rigidity Matrix

The proof of Theorem 2 relies on giving a combinatorial characterization of infinitesimal rigidity with forced symmetry constraints. The rigidity matrix, which is the formal differential of the length equations plays an important role. For periodic frameworks, this has the following form, which was first computed in [4]:

(10)

Here, $\eta _{ij} = \mathbf{p}_{j} + \mathbf{L} \cdot \gamma _{ij} -\mathbf{p}_{i}$ is the vector describing a representative of an edge orbit in $\tilde{G}(\mathbf{p},\mathbf{L})$, which we identify with a colored edge of the quotient $(G,\boldsymbol{\gamma })$. There is one row for each edge in the quotient graph G. The column groups L ₁ and L ₂ correspond to the derivatives with respect to the variables in the rows of $\mathbf{L} = \left (\begin{array}{*{10}c} a&b\\ c &d \end{array} \right )$. A framework is infinitesimally rigid if the rigidity matrix has corank 3, and infinitesimally flexible with d degrees of freedom if the rigidity matrix has corank 3 + d. A framework is generic if the rank of the rigidity matrix is maximal over all frameworks with the same colored quotient graph. We will require some standard facts about infinitesimal rigidity that transfer from the finite to the periodic setting.

Proposition 6.

Let $\tilde{G}(\mathbf{p},\mathbf{L})$ be a periodic framework with quotient graph $(G,\boldsymbol{\gamma })$ . Then:

• For generic frameworks, infinitesimal rigidity and flexibility coincide with rigidity and flexibility[4, 26].

• Infinitesimal rigidity and flexibility are affinely invariant[4], with non-trivial infinitesimal motions mapped to non-trivial infinitesimal motions.

4.2 One Flexible Period

A very simple restriction of the periodic model is to consider frameworks with one flexible period. The symmetry group is then $\mathbb{Z}$, acting on the plane by translations; we call such a framework a cylinder framework. We model the situation with $\mathbb{Z}$-colored graphs, and a single vector $\mathbf{l} \in \mathbb{R}^{2}$ representing the period lattice. In this case, the ρ-image of a colored graph always has rank 0 or 1.

We define a cylinder-Laman graph to be a $\mathbb{Z}$-colored graph $(G,\boldsymbol{\gamma })$ such that: G has n vertices, 2n − 1 edges, and satisfies, for all subgraphs, on n ^′ vertices, m ^′ edges, ρ-image of rank k, $c_{0}^{{\prime}}$ connected components with trivial ρ-image, and $c_{1}^{{\prime}}$ connected components with non-trivial ρ-image:

$$\displaystyle{ m^{{\prime}}\leq 2n^{{\prime}} + k - 3c_{ 0}^{{\prime}}- 2c_{ 1}^{{\prime}} }$$

(11)

Comparing (11) with (5), we see readily:

Proposition 7.

The family of cylinder-Laman graphs corresponds bijectively with the maximal colored-Laman sparse graphs that have colors of the form γ _ij = (⋅,0).

Theorem 3.

A generic cylinder framework is minimally rigid if and only if its associated colored graph is cylinder-Laman.

Proof.

The rigidity matrix for a cylinder framework has the same form as (10), except with the column group labeled L ₂ discarded. Proposition 7 and then Theorem 2 yield the desired statement. □ 

4.3 Unit Area Fundamental Domain

Next, we consider the class of unit-area frameworks, for which the allowed motions preserve the area of the fundamental domain of the $\mathbb{Z}^{2}$-action on the plane induced by the $\mathbb{Z}^{2}$-representation L.

We define a unit-area-Laman graph to be a $\mathbb{Z}^{2}$-colored graph $(G,\boldsymbol{\gamma })$ with n vertices, m = 2n edges, and satisfying, for all subgraphs on n ^′ vertices, m ^′ edges, and $c_{k}^{{\prime}}$ connected components with ρ-image of rank k

$$\displaystyle\begin{array}{rcl} m^{{\prime}}& \leq & 2n^{{\prime}}- 3c_{ 0}^{{\prime}}\qquad \qquad \qquad \quad \ \ \ \ \ \ \mbox{ if $c_{ 2}^{{\prime}} = c_{ 1}^{{\prime}} = 0$}{}\end{array}$$

(12)

$$\displaystyle\begin{array}{rcl} m^{{\prime}}& \leq & 2n^{{\prime}}- 1 - 3c_{ 0}^{{\prime}}- 2(c_{ 1}^{{\prime}}- 1)\qquad \mbox{ if $c_{ 2}^{{\prime}} = 0\mathrm{and}c_{ 1}^{{\prime}} > 0$}{}\end{array}$$

(13)

$$\displaystyle\begin{array}{rcl} m^{{\prime}}& \leq & 2n^{{\prime}}- 3c_{ 0}^{{\prime}}- 2(c_{ 1}^{{\prime}} + c_{ 2}^{{\prime}}- 1)\!\!\qquad \mbox{ if $c_{ 2}^{{\prime}} > 0$}{}\end{array}$$

(14)

Theorem 4.

A generic unit-area framework is minimally rigid if and only if its associated colored graph $(G,\boldsymbol{\gamma })$ is unit-area-Laman.

Proof of Theorem 4.

The proof is comprised of three key propositions. The first is a combinatorial equivalence.

Proposition 8.

A $\mathbb{Z}^{2}$ -colored graph $(G,\boldsymbol{\gamma })$ is unit-area-Laman if and only if it is colored-Laman-sparse and has n vertices, 2n edges, and no subgraph with rank 2 ρ-image and (5) holding with equality.

Proof of Proposition 8.

Comparing (5) with (12,13) and (14), we see that unit-area-Laman graphs are exactly those which, after following the construction used to prove Proposition 5, become colored-Laman. □ 

The Maxwell direction. For the geometric part of the proof, we first derive the rigidity matrix. If $\mathbf{L} = \left (\begin{array}{*{10}c} a&b\\ c &d \end{array} \right )$, and wecoordinatize infinitesimal motions as (v, M) with $\mathbf{M} = \left (\begin{array}{*{10}c} p&q\\ r & s \end{array} \right )$, then this has the form of (10) plus one additional row corresponding to the equation

$$\displaystyle{ \left \langle (d,-c,-b,a),(p,q,r,s)\right \rangle = 0 }$$

(15)

Violations of unit-area-Laman-sparsity come in two types, according to the rank k of the ρ-image. For k = 0, 1, these are all violations of colored-Laman sparsity, implying, by Theorem 2, a generic dependency in the unit-area rigidity matrix that does not involve the row (15). For k = 2, Proposition 8 implies a new type of violation: a subgraph $(G^{{\prime}},\boldsymbol{\gamma })$ with n ^′ vertices, ρ-image of rank 2, and f(G ^′) edges. If such a subgraph forces a generic periodic framework to fix the lattice representation L, then Eq. (15) is dependent on the equations corresponding to edge lengths. The Maxwell direction then follows from the converse of Proposition 5.

Proposition 9.

Let $(G,\boldsymbol{\gamma })$ be a colored-Laman sparse graph with ρ-image of rank 2 and (5) met with equality. Then an associated generic framework has only motions that act trivially on the $\mathbb{Z}^{2}$ -representation L .

Proof of Proposition 9.

Let $(G,\boldsymbol{\gamma })$ have n vertices, and c connected components. It is sufficient to consider $(G,\boldsymbol{\gamma })$ that is minimal with respect to the hypotheses of the proposition, which forces every connected component to have ρ-image with rank at least one. In this case, there are $m = 2n + 3 - 2c$ edges. By Theorem 2, the kernel of the rigidity matrix has dimension $2n + 4 - m = 2c + 1$. Since the connected components can translate independently, and the whole framework can rotate, there are at least 2c + 1 dimensions of infinitesimal motions acting trivially on the lattice. □ 

The Laman direction. Now let $(G,\boldsymbol{\gamma })$ be a unit-area-Laman graph. Theorem 2 implies that any generic periodic framework on $(G,\boldsymbol{\gamma })$ has a 4-dimensional space of infinitesimal motions, and that any non-trivial infinitesimal motion is a linear combination of 3 trivial ones and some other infinitesimal motion (v, M). Since the trivial infinitesimal motions act trivially on the lattice representation L, if (v, M) does as well, then a generic framework on $(G,\boldsymbol{\gamma })$ fixes the lattice representation. By Propositions 8 and 5 this is impossible, implying that (v, M) does not act trivially on the lattice representation. However, it might preserve the area of the fundamental domain, which would make (15) part of a dependency in the unit-area rigidity matrix. The Laman direction will then follow once we can exhibit a generic periodic framework on $(G,\boldsymbol{\gamma })$ for which (v, M) does not preserve the area of the fundamental domain.

To do this, we recall, from Proposition 6, that a generic linear transformation

$$\displaystyle{ \mathbf{A} = \left (\begin{array}{*{10}c} a&b\\ c &d \end{array} \right ) }$$

(16)

preserves infinitesimal rigidity and sends the non-trivial infinitesimal motion (v, M) to another non-trivial infinitesimal motion $(\mathbf{v}^{{\prime}},\mathbf{M}^{{\prime}})$, which is given by

$$\displaystyle\begin{array}{rcl} \mathbf{v}_{i}^{{\prime}} = \mathbf{A}^{{\ast}}\cdot \mathbf{v}_{ i}& \qquad \mbox{for all i} \in \mbox{V (G)}& {}\\ \mathbf{M}^{{\prime}} = \mathbf{A}^{{\ast}}\cdot \mathbf{M}& & {}\\ \end{array}$$

where

$$\displaystyle{ \mathbf{A}^{{\ast}} =\det (\mathbf{A})^{-1}\left (\begin{array}{*{10}c} d &-c \\ -b& a \end{array} \right ) }$$

(17)

is the transpose of A ⁻¹. The main step is this next proposition which says that satisfying (15) is not affinely invariant.

Proposition 10.

Let $(G,\boldsymbol{\gamma })$ be a unit-area-Laman graph, and let $\tilde{G}(\mathbf{p},\mathbf{L})$ be a generic realization with L being the identity matrix, let A be a generic linear transformation, and let the infinitesimal motions ( v, M ) and $(\mathbf{v}^{{\prime}},\mathbf{M}^{{\prime}})$ be defined as above. If ( v, M ) preserves the area of the fundamental domain, then $(\mathbf{v}^{{\prime}},\mathbf{M}^{{\prime}})$ does not.

Proof of Proposition 10.

Because L is the identity, M has the form

$$\displaystyle{ \mathbf{M} = \left (\begin{array}{*{10}c} \lambda & \mu \\ \nu &-\lambda \end{array} \right ) }$$

(18)

either by direction computation, or by observing that it is an element of the Lie algebra sl(2), as discussed above, we know that −μ ≠ ν, since (v, M) does not act trivially on L. In particular, μ and ν are not both zero. Plugging in to (17) we get

$$\displaystyle{ \mathbf{M}^{{\prime}} =\det (\mathbf{A})^{-1}\left (\begin{array}{*{10}c} d\lambda - c\nu & c\lambda + d\mu \\ a\nu - b\lambda &-a\lambda - b\mu \end{array} \right ) }$$

(19)

Plugging entries of M ^′ in to the l.h.s. of (15) to obtain:

$$\displaystyle{ \det (\mathbf{A})^{-1}\left (\lambda (d^{2} + b^{2} - a^{2} - c^{2}) - (\mu +\nu )(ab + cd)\right ) }$$

(20)

which is generically non-zero in the entries of A: the conditions for (20) to vanish are that its columns are the same length and orthogonal to each other. □ 

We now observe that, by Proposition 6, there is a generic realization $\tilde{G}(\mathbf{p},\mathbf{L})$ of a framework with unit-area-Laman colored quotient $(G,\boldsymbol{\gamma })$ in which L is the identity. If the non-trivial infinitesimal motion (v, M) does not satisfy (15), we are done. Otherwise, the hypothesis of Proposition 10 are met, and, thus, after applying a generic linear transformation, the proof is complete. □ 

4.4 Fixed-Lattice Frameworks

Another restricted class of periodic frameworks are fixed-lattice frameworks. These are periodic frameworks, with the restriction that the allowed motions act trivially on the lattice representation. This model was introduced by Whiteley [51] in the first investigation of generic rigidity with forced symmetry. More recently, Ross discovered the following⁵ complete characterization of minimal rigidity for fixed-lattice frameworks.

Theorem 5 ([37] and [38, Theorem 4.2.1]).

Let $\tilde{G}(\mathbf{p})$ be a generic fixed-lattice framework. Then $\tilde{G}(\mathbf{p})$ is minimally rigid if and only if the associated colored graph $(G,\boldsymbol{\gamma })$ has n vertices, $m = 2n - 2$ edges and, for all subgraphs G ^′ of G with n ^′ vertices, m ^′ edges, $c_{0}^{{\prime}}$ connected components with trivial ρ-image, and $c_{\geq 1}^{{\prime}}$ connected components with non-trivial ρ-image:

$$\displaystyle{ m^{{\prime}}\leq 2n^{{\prime}}- 3c_{ 0}^{{\prime}}- 2c_{ \geq 1}^{{\prime}} }$$

(21)

We define the family of graphs appearing in Theorem 5 to be Ross graphs. In [26], we gave an alternate proof based on Theorem 2. The two steps are similar to the ones used to prove Theorem 4, except we can take a “shortcut” in the argument by simulating fixing the lattice by adding self-loops to the colored graph. The geometric step is:

Theorem 6 ([26, Section 19.1]).

Let $\tilde{G}(\mathbf{p})$ be a generic fixed-lattice framework. Then $\tilde{G}(\mathbf{p})$ is minimally rigid if and only if the associated colored graph $(G,\boldsymbol{\gamma })$ plus three self-loops colored (1,0), (0,1), (1,1) added to any vertex is colored-Laman.

Theorem 5 then follows from the following combinatorial statement that generalizes an idea of Lovász-Yemini [23] and Recski [34] (cf. [12, 13]).

Proposition 11 ([26, Lemma 19.1]).

A colored graph $(G,\boldsymbol{\gamma })$ is a Ross graph if and only if adding three self-loops colored (1,0), (0,1), (1,1) to any vertex results in a colored-Laman graph.

4.5 Further Connections

Theorems 3 and 4 suggest a more general methodology for obtaining Maxwell-Laman-type theorems for restrictions of periodic frameworks:

• Add an equation that restricts the allowed lattice representations L.

• Identify which generic periodic frameworks are the maximal ones that do not imply the new restriction.

Our proof of Theorem 5 works this way as well: adding self-loops adds three equations constraining the lattice representation. Another perspective is that we are enlarging the class of trivial infinitesimal motions by forcing one or more vectors into the kernel of the periodic rigidity matrix. The most general form of this operation is known as the “Elementary Quotient” or “Dilworth Truncation”, and it preserves representability of (k, ℓ)-sparsity matroids [47], but obtaining rigidity results (e.g., [23]) requires geometric analysis specific to each case. This section gives a family of examples where we find new rigidity matroids from each other using a specialized version of Dilworth Truncation.

Ross [38, Section 5] has studied some restrictions of periodic frameworks as generalizations of the fixed-lattice model. In this section we close the circle of ideas, showing how to study them as specializations of the flexible-lattice model.

4.6 One More Variant

We end this section with one more variation of the periodic model. A fixed-angle framework is defined to be a periodic framework where the allowed motions preserve the angle between the sides of the fundamental domain.

Theorem 7.

A generic fixed angle framework is minimally rigid if and only if its associated colored graph is unit-area-Laman.

Proof Sketch.

The steps are similar to the proof of Theorem 4. The new row in the rigidity matrix corresponds to (in the same notation) the partial derivatives of the equation:

$$\displaystyle{ \left \langle \frac{(a,c)} {\vert \vert (a,c)\vert \vert }, \frac{(b,d)} {\vert \vert (b,d)\vert \vert }\right \rangle = \text{const} }$$

(22)

so the new row in the rigidity matrix corresponds to:

$$\displaystyle{ \left \langle \det (\mathbf{L})\left (c\vert \vert (b,d)\vert \vert ^{2},-d\vert \vert (a,c)\vert \vert ^{2},a\vert \vert (b,d)\vert \vert ^{2},-b\vert \vert (a,c)\vert \vert ^{2}\right ),(p,q,r,s)\right \rangle = 0 }$$

(23)

The Maxwell direction’s proof is exactly the same as for Theorem 4. For the Laman direction, we again start with a generic framework where L is the identity. If the non-trivial infinitesimal motion (v, M) does not preserve (23), then we are done. Otherwise, M has the form

$$\displaystyle{ \mathbf{M} = \left (\begin{array}{*{10}c} \mu &\lambda \\ -\lambda &\nu \end{array} \right ) }$$

(24)

with μ and ν not both zero, because M does not act trivially on L. We then construct a new generic framework by applying a linear map

$$\displaystyle{ \mathbf{A} = \left (\begin{array}{*{10}c} 1& b\\ 0 &d \end{array} \right ) }$$

(25)

A computation, similar to that for (20) yields

$$\displaystyle{ -\frac{b\left (b^{2}\mu + d^{2}\mu +\nu \right )} {\vert \vert (b,d)\vert \vert ^{3}} }$$

(26)

which is, generically, not zero. □ 

5 Cone and Reflection Frameworks

The next cases of Theorem 2 are those of $\mathbb{Z}/2\mathbb{Z}$ acting on the plane by a single reflection and $\mathbb{Z}/k\mathbb{Z}$ acting on the plane by rotation through angle 2π∕k. The sparsity invariants are particularly easy to characterize in these two cases:

• The Teichmüller space is empty, since any rotation center or reflection axis can be moved on to another by an isometry.

• The centralizer is all of Euc(2) for the trivial subgroup and otherwise consists of rotation around a fixed center or translation parallel to the reflection axis.

Since the rank k of the ρ-image of a $\mathbb{Z}/k\mathbb{Z}$-colored graph is always zero or one, we specialize (2) to obtain the sparsity condition for subgraphs on n ^′ vertices, m ^′ edges, $c_{0}^{{\prime}}$ connected components with trivial ρ-image and $c_{1}^{{\prime}}$ connected components with non-trivial ρ-image.

$$\displaystyle{ m^{{\prime}}\leq 2n^{{\prime}}- 3c_{ 0}^{{\prime}}- c_{ 1}^{{\prime}} }$$

(27)

We define the family of $\mathbb{Z}$-colored graphs $(G,\boldsymbol{\gamma })$ corresponding to minimally rigid frameworks to be cone-Laman graphs. The name cone-Laman comes from considering the quotient of the plane by a rotation through angle 2π∕k, which is a flat cone, as shown in Fig. 2. Cone-Laman graphs are closely related to (2, 1)-sparse graphs [20], and in this section we use some sparse graph machinery to obtain combinatorial results on them.

Fig. 2

Figures from [1]. (a) A cone-Laman graph. (b) A realization of (a) as a framework in a cone with opening angle 2π∕3

5.1 Some Background in (k, ℓ)-Sparse Graphs

In this section, we relate cone-Laman graphs to Laman graphs, and we will repeatedly appeal to some standard results about (k, ℓ)-sparse graphs from [20]. In addition, we will require:

Proposition 12.

Let G be a (2,1)-graph. If there is exactly one (2,2)-circuit in G, then G is (2,2)-spanning. Otherwise, G is not (2,2)-spanning and the (2,2)-circuits in G are vertex-disjoint.

Proof.

Let G have n vertices. First assume that G has exactly one (2, 2)-circuit. Then G is a (2, 2)-sparse graph G ^′ plus one edge; since G has 2n − 1 edges, G ^′ is a (2, 2)-graph. Otherwise there is more than one (2, 2)-circuit. Pick a (2, 2)-basis G ^′ of G. In this case G ^′ does not have enough edges to be a (2, 2)-graph, so it decomposes, by [20, Theorem 5], into vertex-disjoint (2, 2)-components that span all of the edges in G∖ G ^′. Because G is (2, 1)-sparse, it follows that each (2, 2)-component spans at most one edge of G ∖ G ^′, and thus at most one (2, 2)-circuit. We have now shown that the vertex sets of the (2, 2)-circuits in G are each contained in a different (2, 2)-component of G ^′. □ 

5.2 Cone-Laman vs. Cylinder-Laman

By comparing the cylinder-Laman counts (11) with the cone-Laman counts (27), we can see that every cylinder-Laman graph, interpreted as having $\mathbb{Z}/k\mathbb{Z}$ colors, is also cone-Laman for k large enough. However, the two classes are not equivalent. One can see this geometrically by considering a colored graph with two disconnected vertices and a self-loop with the color 1 on each vertex: this is evidently dependent in the cylinder, and independent in the cone. The conclusion is that the interplay between $\text{teich}_{\Gamma }(\cdot )$ and cent(⋅ ), can yield two different, geometrically interesting sparse colored families on (2, 1)-graphs. The combinatorial relation is:

Theorem 8.

A $\mathbb{Z}$ -colored graph $(G,\boldsymbol{\gamma })$ is cylinder-Laman if and only if it is cone-Laman when interpreted as having $\mathbb{Z}/k\mathbb{Z}$ -colors for a sufficiently large k and G is (2,2)-spanning.

Proof.

The only difficult thing to check is that a cylinder-Laman graph $(G,\boldsymbol{\gamma })$ is (2, 2)-spanning. Assuming that G is not (2, 2)-spanning, Proposition 12 supplies two vertex-disjoint (2, 1)-blocks. If the union spans n ^′ vertices, there are 2n ^′− 2 edges, which violates (11). □ 

5.3 Connections to Symmetric Finite Frameworks

The following theorem of Schulze is superficially similar to Theorem 2 for k = 3:

Theorem 9 ([42, Theorem 5.1]).

Let G be a Laman-graph with a free $\mathbb{Z}/3\mathbb{Z}$ action $\varphi$ . Then a generic framework embedded such that $\varphi$ is realized by a rotation through angle 2π∕3 is minimally rigid.

We highlight this result to draw a distinction between forced and incidental symmetry: while Theorem 9 is related to Theorem 2, it is not implied by it. The issue is that while infinitesimal motions of the cone-framework lift to infinitesimal motions, only symmetric infinitesimal motions of the lift project to infinitesimal motions of the associated cone-framework. Thus, from Theorem 2, we learn that the lift of a generic minimally rigid cone framework for k = 3 has no symmetric infinitesimal motion as a finite framework, but there may be a non-symmetric motion induced by the added symmetry. An interesting question is whether the natural generalization of Schulze’s Theorem holds:

Question 1.

Let k > 3, and let $(G,\varphi )$ be a graph with a free $\mathbb{Z}/k\mathbb{Z}$-action. Are generic frameworks with $Z/k\mathbb{Z}$-symmetry rigid if and only if G is Laman-spanning and its colored quotient is cone-Laman-spanning?

That G must be Laman-spanning is clear. On the other hand, the discussion above and Theorem 2 imply that to avoid a symmetric non-trivial infinitesimal motion, a generic $\mathbb{Z}/k\mathbb{Z}$-symmetric finite framework must have cone-Laman-spanning quotient. Ross, Schulze and Whiteley [39] and Schulze and Whiteley [43] use this same idea in a number of interesting 3-dimensional applications. The graphs described in the question are a family of simple (2, 0)-graphs; simple (2, 1)-graphs have recently played a role in the theory of frameworks restricted to lie in surfaces embedded in $\mathbb{R}^{3}$ [30, 31].

5.4 The Lift of a Cone-Laman Graph

The lift $(\tilde{G},\varphi )$, defined in Sect. 2.3, of a $\mathbb{Z}/k\mathbb{Z}$-colored graph is itself a finite graph $(G,\varphi )$ with a free action by $\mathbb{Z}/k\mathbb{Z}$. For k ≥ 3 prime, cone-Laman graphs have a close connection to Laman graphs.

Proposition 13 ([1, Lemma 6]).

Let k ≥ 3 be prime. A $\mathbb{Z}/k\mathbb{Z}$ -colored graph is cone-Laman if and only if its lift $(G,\varphi )$ has as its underlying graph a Laman-sparse graph G with $\tilde{n}$ vertices and $2\tilde{n} - k$ edges.

As noted in [1], this statement is false for k = 2, so while we can relax the hypothesis somewhat at the expense of a more complicated statement, they cannot all be removed.

Although it is simple, Proposition 13 is surprisingly powerful, since it shows that one can study cone-Laman graphs using all the combinatorial tools related to Laman graphs. Proposition 13 depends in a fundamental way on the fact that cone-Laman graphs have 2n − 1 edges, and it does not have a naive generalization to colored-Laman or unit-area-Laman graphs.

Question 2.

What are the $\mathbb{Z}^{2}$-colored graphs $(G,\boldsymbol{\gamma })$ with the property that every finite subgraph of the periodic lift $(\tilde{G},\varphi )$ is Laman-sparse?

We expect that this should be a more general family than unit-area-Laman graphs. On the other hand, it has been observed by Guest and Hutchinson [11] that (in our language) the lift of a colored-Laman graph is not Laman-sparse.

6 Groups with Rotations and Translations

The final case of Theorem 2 is that of crystallographic groups acting discretely and cocompactly by translations and rotations. It is a classical fact [2, 3] that all such groups other than $\mathbb{Z}^{2}$ are semi-direct products of the form

$$\displaystyle{\varGamma _{k}:= \mathbb{Z}^{2} \rtimes \mathbb{Z}/k\mathbb{Z}}$$

where k = 2, 3, 4, 6. The action on $\mathbb{Z}^{2}$ by the generator of $\mathbb{Z}/k\mathbb{Z}$ is given by the following table.

k	2	3	4	6
Matrix	$\left (\begin{array}{rr} - 1& 0\\ 0 & - 1\end{array} \right )$	$\left (\begin{array}{rr} 0& - 1\\ 1 & - 1\end{array} \right )$	$\left (\begin{array}{rr} 0& - 1\\ 1 & 0\end{array} \right )$	$\left (\begin{array}{rr} 0& - 1\\ 1 & 1\end{array} \right )$

6.1 The Quantities teich(⋅ ) and cent(⋅ ) for Subgroups

For any discrete faithful representation Φ: Γ _k  → Euc(2), it is a (non-obvious) fact that for any element $t \in \mathbb{Z}^{2}$ in Γ _k , the image Φ(t) is necessarily a translation, and for any $r \in \varGamma _{k}\setminus \mathbb{Z}^{2}$, the image Φ(r) is necessarily a rotation. Consequently, we respectively call such elements of Γ _k translations and rotations, and we call $\varLambda (\varGamma _{k}) = \mathbb{Z}^{2}$ the translation subgroup of Γ _k . For any subgroup $\varGamma ^{{\prime}} <\varGamma _{k}$, its translation subgroup is $\varLambda (\varGamma ^{{\prime}}) =\varGamma ^{{\prime}}\cap \varLambda (\varGamma _{k})$.

Let Φ be a representation of Γ _k . In the cases k ≠ 2, we must have Φ(Λ(Γ _k )) preserved by an order k rotation, and so the image of Λ(Γ _k ) is determined by the image of a single nontrivial t ∈ Λ(Γ _k ). Furthermore, by acting on Φ by a rotation in Euc(2), we can always obtain a new representation Φ ^′ such that Φ(t) has translation vector (λ, 0) for some $\lambda \in \mathbb{R}$. Consequently, we have shown the following.

Proposition 14.

Let Γ ^′ be a subgroup of Γ _k for k​ =​ 3,4,6. Then, $\text{teich}_{\varGamma _{k}}(\varLambda (\varGamma ^{{\prime}}))\! =\! 1$ if Λ(Γ ^′ ) is nontrivial and is 0 otherwise.

In the case of k = 2, it turns out that since order 2 rotations preserve all lattices, this puts no constraint on how Φ embeds Λ(Γ ₂). Consequently, we have teich values similar to the periodic case.

Proposition 15.

Let Γ ^′ be a subgroup of Γ ₂ . Then, $\text{teich}_{\varGamma _{k}}(\varLambda (\varGamma ^{{\prime}})) = \text{max}(2\ell - 1,0)$ where $\ell= \mathrm{rk}(\varLambda (\varGamma ^{{\prime}}))$ .

The dimension of the centralizer, similarly, is concrete and computable. If a subgroup contains a translation t, then Φ(t) commutes precisely with translations of Euc(2). If a subgroup Γ ^′ of Γ _k is a cyclic subgroup of rotations, then Φ(Γ ^′) is a group of rotations with the same rotation center, and it is easy to see that such a group commutes precisely with the (1-dimensional) subgroup in Euc(2) of rotations with that center. Consequently, we obtain the following characterization of cent.

Proposition 16.

Suppose that Γ ^′ is a subgroup of Γ _k . Then,

$$\displaystyle{\text{cent}(\varGamma ^{{\prime}}) = \left \{\begin{array}{rcl} 3&&\mbox{ if $\varGamma ^{{\prime}}$ is trivial} \\ 2&&\mbox{ if $\varGamma ^{{\prime}}$ contains only translations} \\ 1&&\mbox{ if $\varGamma ^{{\prime}}$ contains only rotations} \\ 0&&\mbox{ if $\varGamma ^{{\prime}}$ contains both rotations and translations} \end{array} \right.}$$

6.2 The Quantities teich(⋅ ) and cent(⋅ ) for Colored Graphs

For any Γ _k -colored graph $(G^{{\prime}},\boldsymbol{\gamma })$, we associate subgroups of Γ _k . Suppose G has components $G_{1}^{{\prime}},\ldots,G_{c}^{{\prime}}$ and choose base vertices $b_{1},\ldots,b_{c}$. We set $\varGamma _{i}^{{\prime}} =\rho (\pi _{1}(G_{i}^{{\prime}},b_{i}))$, and

$$\displaystyle{\varLambda (G_{1}) =\langle \varLambda (\varGamma _{1}^{{\prime}}),\varLambda (\varGamma _{ 2}^{{\prime}}),\ldots,\varLambda (\varGamma _{ c}^{{\prime}})\rangle }$$

The Γ-Laman sparsity counts are defined in terms of teich(Λ(G)) and $\text{cent}(\varGamma _{i}^{{\prime}})$. Since we chose base vertices b _i , one might worry that these quantities are not well-defined. However, changing the base vertex in G _i has the effect of conjugating $\varGamma _{i}^{{\prime}}$. In Γ _k , conjugates of translations are translations and conjugates of rotations are rotations, so cent(⋅ ) is then well-defined by Proposition 16, and teich(Λ(G)) for k = 3, 4, 6 by Proposition 14. Indeed, for k = 3, 4, 6, teich(Λ(G)) = 1 if any $\varLambda (\varGamma _{i}^{{\prime}})$ is nontrivial and is 0 otherwise. In Γ ₂, all translation subgroups are normal, so $\varLambda (\varGamma _{i}^{{\prime}})$ itself does not depend on the choice of base vertex.

6.3 Computing teich and cent for Γ ₂-Colored Graphs

A quick and simple algorithm exists to compute teich(Λ(G)) and $\text{cent}(\varGamma _{i}^{{\prime}})$ which relies on finding a suitable generating set for $\varGamma _{i}^{{\prime}}$. A generating set for $\pi _{1}(G_{i}^{{\prime}},b_{i})$ can be constructed as follows. Find a spanning tree T _i of component G _i . Then for each edge $jk \in G_{i} - T_{i}$, let P _jk be the path traversing the (unique) path b _i to j in T _i , then jk, and then the (unique) path k to b _i in T _i . The P _jk ranging over $jk \in G_{i} - T_{i}$ generate $\pi _{1}(G_{i}^{{\prime}},b_{i})$, and so $\eta _{jk}:=\rho (P_{jk})$ ranging over the same set generates $\varGamma _{i}^{{\prime}}$.

Next, relabel the generators of $\varGamma _{i}^{{\prime}}$ as $r_{j,i},t_{j,i}$ where the r _j, i are rotations and the t _j, i are translations. If there are only translations, no modifications are required and $\varLambda (\varGamma _{i}^{{\prime}}) =\varGamma _{ i}^{{\prime}}$. Otherwise, set $t_{j,i}^{{\prime}} = r_{1,i}r_{j,i}$ for j ≥ 2. Since all rotations are order 2, the $t_{j,i}^{{\prime}}$ are all translations and $\varGamma _{i}^{{\prime}}$ is generated by r _1, i , the $t_{j,i}^{{\prime}}$ and the t _j, i . At this point, checking $\text{cent}\varGamma _{i}^{{\prime}}$ is straightforward. Furthermore, one can show that $\varLambda (\varGamma _{i}^{{\prime}})$ is generated by the $t_{j,i}^{{\prime}}$ and t _j, i , and so Λ(G) is generated by the $t_{j,i}^{{\prime}}$ and the t _j, i over all i and j. Then, computing rk(Λ(G)) is basic linear algebra, and teich(Λ(G)) is given by Proposition 15.

6.4 Computing teich and cent for Γ _k -Colored Graphs for k ≠ 2

In this case, all that needs to be determined is whether each $\varGamma _{i}^{{\prime}}$ contains rotations, translations, or both. Compute generators $r_{j,i},t_{j,i}$ for $\varGamma _{i}^{{\prime}}$ as above. Then, $\varGamma _{i}^{{\prime}}$ contains a rotation if and only if there is at least one r _j, i . The only real difficulty is determining if $\varGamma _{i}^{{\prime}}$ contains translations when the generators are all rotations. Any group consisting entirely of rotations is cyclic (see, e.g., [24, Lemma 4.2]), and so it suffices to compute the commutators $r_{1,i}r_{j,i}r_{1,i}^{-1}r_{j,i}^{-1}$ for j ≥ 2. The group contains no translations if and only if these commutators are all trivial.