Generic combinatorial rigidity of periodic frameworks (Q1931845)

The authors give a combinatorial characterization of generic minimal rigidity for planar periodic frameworks which is similar to the Maxwell-Laman theorem [\textit{G. Laman}, J. Eng. Math. 4, 331--340 (1970; Zbl 0213.51903)] from rigidity theory in the sense that it is formulated in terms of a finite combinatorial object and the conditions are checkable by polynomial time combinatorial algorithms. The authors define a periodic framework as a triple \((\widetilde{G}, \varphi, \widetilde{\ell})\), where \(\widetilde{G}\) is a simple infinite graph; \(\varphi\) is a free \(\mathbb Z^2\)-action on \(\widetilde{G}\) by automorphisms such that the quotient is finite; and \(\widetilde{\ell}=(\widetilde{\ell_{ij}})\) assigns a length to each edge of \(\widetilde{G}\). They define a realization \(\widetilde{G}(p,L)\) of a periodic framework \((\widetilde{G}, \varphi, \widetilde{\ell})\) as a pair consisting of a mapping \(p\) of the vertex set \(V\widetilde(G)\) into \(\mathbb R^2\) and a representation \(\mathbb Z^2\to\mathbb R^2\) encoded by a \(2\times 2\)-matrix \(L\) such that: (1) the representation is equivariant with respect to the \(\mathbb Z^2\)-actions on \(\widetilde{G}\) and the plane; and (2) the specified edge lengths are preserved by \(p\). A realization \(\widetilde{G}(p,L)\) is called rigid if the only allowed continuous motions of \(p\) and \(L\) that preserve the action \(\varphi\) and the edge lengths are rigid motions of the plane. If \(\widetilde{G}(p,L)\) is rigid but ceases to be so if any \(\mathbb Z^2\)-orbit of edges in \(\widetilde{G}\) is removed it is minimally rigid. One of the main results reads as follows: A generic realization \(\widetilde{G}(p,L)\) of a generic periodic framework \((\widetilde{G}, \varphi, \widetilde{\ell})\) is minimally rigid if and only if its colored quotient graph is colored-Laman. The definitions of colored-Laman and colored quotient graphs are too technical to be given in this review, but we observe that (i) every colored quotient graph is a finite combinatorial object; (ii) the property `to be colored-Laman' is checkable in polynomial time; and (iii) using the notions of colored-Laman and colored quotient graphs, the authors also prove an analogue of Whiteley's Parallel Redrawing Theorem [\textit{W. Whiteley}, SIAM J. Discrete Math. 1, No. 2, 237--255 (1988; Zbl 0671.05026)].