# Realizable Dimension of Periodic Frameworks

Ryoshun Oba Department of Mathematical Informatics, Graduate School of
Information Science and Technology, University of Tokyo, Tokyo 113-8656,
Japan. Email<EMAIL_ADDRESS>Shin-ichi Tanigawa Department
of Mathematical Informatics, Graduate School of Information Science and
Technology, University of Tokyo, Tokyo 113-8656, Japan. Email:
<EMAIL_ADDRESS>
###### Abstract

Belk and Connelly introduced the realizable dimension $\operatorname{rd}(G)$
of a finite graph $G$, which is the minimum nonnegative integer $d$ such that
every framework $(G,p)$ in any dimension admits a framework in
$\mathbb{R}^{d}$ with the same edge lengths. They characterized finite graphs
with realizable dimension at most $1$, $2$, or $3$ in terms of forbidden
minors. In this paper, we consider periodic frameworks and extend the notion
to $\mathbb{Z}$-symmetric graphs. We give a forbidden minor characterization
of $\mathbb{Z}$-symmetric graphs with realizable dimension at most $1$ or $2$,
and show that the characterization can be checked in polynomial time for given
quotient $\mathbb{Z}$-labelled graphs.

##  1 Introduction

A _framework_ in the Euclidean space $\mathbb{R}^{d}$ is a graph in which each
vertex is a point in $\mathbb{R}^{d}$ and each edge is a straight line
connecting the endvertices. It is denoted by a pair $(G,p)$, where $G$ is the
underlying (possibly infinite) undirected graph and
$p:V(G)\rightarrow\mathbb{R}^{d}$ is a map called a point configuration. The
_affinie dimension_ of a framework $(G,p)$ is defined to be the affine
dimension of $p(V(G))$. Two frameworks $(G,p)$ and $(G,q)$, possibly in
different dimensions, are _equivalent_ if $\|p(i)-p(j)\|=\|q(i)-q(j)\|$ for
all $ij\in E(G)$, where $\|\cdot\|=\|\cdot\|_{2}$ is the Euclidean norm. Belk
and Connelly [2] introduced a minor monotone parameter called the realizable
dimension of finite graphs. A finite graph $G$ is _$d$ -realizable_ if every
framework $(G,p)$ in any dimension admits an equivalent framework with the
affine dimenision at most $d$. The _realizable dimension_
$\operatorname{rd}(G)$ of a finite graph $G$ is the smallest nonegative
integer $d$ such that $G$ is $d$-realizable. Belk and Connelly characterized
finite graphs satisfying $\operatorname{rd}(G)\leq d$ in terms of forbidden
minors for $d=1,2,3$ [1, 2]. The lists of forbidden minors are $\\{K_{3}\\}$
when $d=1$, $\\{K_{4}\\}$ when $d=2$, and $\\{K_{5},K_{2,2,2}\\}$ when $d=3$.

In this paper, we extend the notion of realizable dimension to a periodic
setting. The rigidity of periodic frameworks has been widely investigated in
the past decade [3, 11, 14, 15]. See [16] for further reference. Since our aim
in this paper is to examine the extendability of the concept to periodic
frameworks, here we focus on the simplest setting, where frameworks have one
dimensional periodicity (see Figure 1) and motions of frameworks are subject
to a given fixed periodicity. An infinite graph $G$ is _$\mathbb{Z}$
-symmetric_ if an additive group $\mathbb{Z}$ acts freely on
$\operatorname{Aut}(G)$ and the number of vertex orbits is finite. We fix an
action and the action of $\gamma\in\mathbb{Z}$ on $V(G)$ is denoted by
$+\gamma$. Two $\mathbb{Z}$-symmetric graphs are isomorphic if there is an
ordinary graph isomorphism compatible with the $\mathbb{Z}$-actions. For a
nonzero vector $\ell\in\mathbb{R}^{d}$, a framework $(G,p)$ in
$\mathbb{R}^{d}$ is called _$\ell$ -periodic_ if $G$ is a
$\mathbb{Z}$-symmetric graph and $p(v+1)-p(v)=\ell$ for all $v\in V(G)$. The
vector $\ell$ is called the _lattice vector_ of $(G,p)$. A
$\mathbb{Z}$-symmetric graph $G$ is _$d$ -realizable_ if every $\ell$-periodic
framework $(G,p)$ in any dimension with any lattice vector $\ell$ admits an
equivalent $\ell$-periodic framework with the affine dimension at most $d$.
The _realizable dimension_ $\operatorname{rd}(G)$ of a $\mathbb{Z}$-symmetric
graph $G$ is defined to be the smallest nonnegative integer $d$ such that $G$
is $d$-realizable. We show that the parameter $\operatorname{rd}(\cdot)$ is
minor monotone, where a minor operation of a $\mathbb{Z}$-symmetric graph is
defined as a deletion or contraction of a vertex orbit or an edge orbit which
does not destroy $\mathbb{Z}$-symmetry. Our main theorem is a forbidden minor
characterization of $\mathbb{Z}$-symmetric graphs with realizable dimension at
most $1$ or $2$. Our proof of the characterizations leads to a polynomial time
algorithm to check the $1$-realizability or $2$-realizability of
$\mathbb{Z}$-symmetric graphs when a $\mathbb{Z}$-symmetric graph is given in
terms of its quotient $\mathbb{Z}$-labelled graph.

$\ell$

$+0$$+1$$+0$$+1$$+0$

Figure 1: An affine $2$-dimensional periodic framework with the lattice vector
$\ell$ (left) and the quotient $\mathbb{Z}$-labelled graph of its underlying
$\mathbb{Z}$-symmetric graph (right)

In the case of finite graphs, the characterization of $d$-realizable graphs is
done by first enumerating obstacles of $d$-realizability, that is, graphs
whose realizable dimension is more than $d$, and then by showing that graphs
that avoid these obstacles as a minor have a nice inductive construction [2].
For proving that $G$ is an obstacle of $d$-realizability, it is enough to find
a $d+1$-dimensional globally rigid realization $(G,p)$ of $G$, i.e., $(G,p)$
has no equivalent but non-congruent framework in $\mathbb{R}^{d+1}$. A useful
sufficient condition of the global rigidity of frameworks is super stability
by Connelly [4], which actually guarantees stronger rigidity property called
universal rigidity. A modern exposition on the connection between universal
rigidity and super stability is given through a semidefinite programming (SDP)
formulation [20]. Motivated by this background, in this paper we extend the
super stability condition to the periodic setting based on an unpublished work
[7]. Then periodic super stability is used to construct obstacles of
$d$-realizability in the periodic setting.

The paper is organized as follows. In Section 2, we give preliminary facts on
$\mathbb{Z}$-labelled graphs. In Section 3, we formally introduce periodic
frameworks and the periodic extension of realizable dimension. In Section 4,
we investigate affine images of frameworks as a tool to find lower affine
dimensional equivalent frameworks. In Section 5, equilibrium stresses of
periodic frameworks are introduced and a relationship between periodic
universal rigidity and periodic super stability is discussed. In Section 6, we
determine the realizable dimension of $\mathbb{Z}$-symmetric graphs such that
for every pair of vertex orbits there is an edge orbit between them. In
Section 7, we introduce two operations to obtain $d$-realizable
$\mathbb{Z}$-labelled graphs from smaller $d$-realizable $\mathbb{Z}$-labelled
graphs. Then we characterize $\mathbb{Z}$-symmetric graphs with realizable
dimension at most $1$ or $2$, and give a polynomial time algorithm.

##  2 $\mathbb{Z}$-labelled Graphs

Throughout the paper we assume that $\mathbb{Z}$ is an additive group. For two
edges of a directed multigraph, we say that they are parallel if they have the
same set of endvertices. For two parallel edges $e,f$ of a directed
multigraph, we say that $e$ and $f$ have the same direction if the heads of
$e$ and $f$ coincide, and have the inverse directions if the head of $e$ and
the tail of $f$ coincide. Let $K_{n}$ be a simple undirected complete graph on
$n$ vertices. By abuse of notation, a directed graph obtained by orienting
each edge of $K_{n}$ is also denoted as $K_{n}$.

###  2.1 $\mathbb{Z}$-symmetric graphs and $\mathbb{Z}$-labelled graphs

Let $G=(V,E)$ be a $\mathbb{Z}$-symmetric graph. A vertex (resp. edge) orbit
is an orbit of the $\mathbb{Z}$-action on $V$ (resp. $E$), and the set of
vertex (resp. edge) orbits is denoted as $V/\mathbb{Z}$ (resp.
$E/\mathbb{Z}$). We always assume that $V/\mathbb{Z}$ and $E/\mathbb{Z}$ are
finite sets. In a $\mathbb{Z}$-symmetric graph $G$, a vertex subset $\hat{V}$
is called a _representative vertex set_ if it is a transversal of the set of
vertex orbits of $G$, i.e., $\hat{V}$ has exactly one element from each vertex
orbit. The unique element of a vertex orbit is called the _representative
vertex_ of the orbit (in $\hat{V}$). Observe that a $\mathbb{Z}$-symmetric
graph can be represented as a directed multigraph with an edge
$\mathbb{Z}$-labelling as follows. For a vertex representative set $\hat{V}$,
each edge orbit is written as
$\\{\\{i+\beta,j+\beta+\gamma\\}:\beta\in\mathbb{Z}\\}$ for some
$i,j\in\hat{V}$ and $\gamma\in\mathbb{Z}$. Regard this edge orbit as a
directed edge from $i$ to $j$ with a label $\gamma$. The resulting pair of a
directed multigraph and an edge $\mathbb{Z}$-labelling is called the _quotient
$\mathbb{Z}$-labelled graph_ of $G$ with respect to $\hat{V}$ (see Figure 1
for an example).

In general, a _$\mathbb{Z}$ -labelled graph_ (or _$\mathbb{Z}$ -gain graph_)
is a pair $(\hat{G},z)$ of a finite directed multigraph
$\hat{G}=(\hat{V},\hat{E})$ and a map $z:\hat{E}\rightarrow\mathbb{Z}$. We
allow $\hat{G}$ to have selfloops. $z$ is called an _(edge) labelling_ , and
it is _simple_ if selfloops have nonzero labels and no pair of parallel edges
has the same direction and the same label nor has the inverse directions and
inverse labels. We always assume that the edge labelling of a
$\mathbb{Z}$-labelled graph is simple, and we write an edge $e$ from $i$ to
$j$ with a label $z(e)$ as $(i,j;z(e))$. A vertex (resp. edge) set of
$\mathbb{Z}$-labelled graph $(\hat{G},z)$ is denoted by $\hat{V}(\hat{G})$
(resp. $\hat{E}(\hat{G})$). For a $\mathbb{Z}$-labelled graph $(\hat{G},z)$,
its _lift graph_ (or _covering graph_) is an undirected graph $G=(V,E)$, where
$V=\hat{V}(\hat{G})\times\mathbb{Z}=\\{i+\gamma:i\in\hat{V}(\hat{G}),\gamma\in\mathbb{Z}\\}$
and

$\displaystyle
E=\\{\\{i+\gamma,j+(\gamma+z(e))\\}:(i,j;z(e))\in\hat{E}(\hat{G}),\gamma\in\mathbb{Z}\\}.$

The lift graph of $\mathbb{Z}$-labelled graph is $\mathbb{Z}$-symmetric. We
remark that the edge set of a $\mathbb{Z}$-labelled graph is identified with
the set of edge orbits of a $\mathbb{Z}$-symmetric graph.

We define the notion of isomorphism of $\mathbb{Z}$-labelled graphs. An _edge
inversion_ of a $\mathbb{Z}$-labelled graph is an operation in which an
orientation of an edge is inverted and its label is also inverted. For a
$\mathbb{Z}$-labelled graph $(\hat{G},z)$, a _switching_ of $i\in\hat{V}$ by
$\gamma\in\mathbb{Z}$ changes each edge $(i,j;z(e)))$ to $(i,j;z(e)+\gamma)$,
and each edge $(j,i;z(e))$ to $(j,i;z(e)-\gamma)$. The labels of selfloops
incident to $i$ are unchanged. $\mathbb{Z}$-labelled graphs $(\hat{G},z)$ and
$(\hat{H},w)$ are _isomorphic_ if after a sequence of edge inversions and
switchings, there is a bijection
$\varphi:\hat{V}(\hat{G})\rightarrow\hat{V}(\hat{H})$ such that
$(i,j;\gamma)\in\hat{E}(\hat{G})$ if and only if
$(\varphi(i),\varphi(j);\gamma)\in\hat{E}(\hat{H})$. $\mathbb{Z}$-labelled
graphs are isomorphic if and only if their lift graphs are isomorphic
$\mathbb{Z}$-symmetric graphs. To see an example, let $K_{2}^{\bullet}$ be a
directed multigraph on $\\{1,2\\}$ with a pair of parallel edges $e,f$ from
$1$ to $2$. Then, $(K_{2}^{\bullet},z)$ and $(K_{2}^{\bullet},z^{\prime})$ are
isomorphic if and only if $z(e)-z(f)=\pm(z^{\prime}(e)-z^{\prime}(f))$.

We introduce minor operations for $\mathbb{Z}$-labelled graphs. Let
$(\hat{G},z)$ be a $\mathbb{Z}$-labelled graph. An _edge (resp. vertex)
deletion_ is an operation in which an edge $e$ (resp. a vertex $i$) is deleted
and the labelling is restricted to the remaining edges. The resulting
$\mathbb{Z}$-labelled graph is denoted as $(\hat{G}-e,z)$ (resp.
$(\hat{G}-i,z)$). An _edge contraction_ of an edge $e=(i,j;0)$ is an operation
in which endvertices $i$ and $j$ are identified and the labelling is
restricted to the remaining edges, and if any, selfloops with zero label or
some parallel edges are deleted to make the edge labelling simple111Although
there may be multiple ways to delete parallel edges, the resulting
$\mathbb{Z}$-labelled graphs are isomorphic, so one may delete any edges.. The
resulting $\mathbb{Z}$-labelled graph is denoted as $(\hat{G}/e,z)$. Note that
we define an edge contraction only along an edge with $0$ label. Note also
that one can always convert the labelling of an edge, which is not a selfloop,
to $0$ by a switching. A deletion or contraction of a vertex and an edge in a
$\mathbb{Z}$-labelled graph is interpreted in terms of the lift graph as was
described in the introduction. Let $(\hat{G},z)$ and $(\hat{H},w)$ be
$\mathbb{Z}$-labelled graphs. $(\hat{G},z)$ is a subgraph of $(\hat{H},w)$ if
a $\mathbb{Z}$-labelled graph isomorphic to $(\hat{G},z)$ is obtained from
$(\hat{H},w)$ by a sequence of edge deletions and vertex deletions.
$(\hat{G},z)$ is a _minor_ of $(\hat{H},w)$ if a $\mathbb{Z}$-labelled graph
isomorphic to $(\hat{G},z)$ is obtained from $(\hat{H},w)$ by a sequence of
edge deletions, vertex deletions and edge contractions. $(\hat{G},z)$ is a
minor of $(\hat{H},w)$ if and only if the lift graph of $(\hat{G},z)$ is a
minor of the lift graph of $(\hat{H},w)$ as a $\mathbb{Z}$-symmetric graph.

A _walk_ in a $\mathbb{Z}$-labelled graph $(\hat{G},z)$ is an alternating
sequence $v_{1}e_{1}v_{2}\cdots e_{k}v_{k+1}$ of vertices and edges of
$\hat{G}$ such that $v_{i}$ and $v_{i+1}$ are the endvertices of $e_{i}$, and
it is _closed_ if $v_{k+1}=v_{1}$. A closed walk $v_{1}e_{1}v_{2}\cdots
e_{k}v_{1}$ is a _cycle_ if $v_{1},\ldots,v_{k}$ are distinct. For a closed
walk $v_{1}e_{1}v_{2}\cdots e_{k}v_{1}$, its _gain_ is defined as
$\sum_{i=1}^{k}\operatorname{sign}(e_{i})z(e_{i})$, where
$\operatorname{sign}(e_{i})=1$ if $e_{i}$ is forward direction and
$\operatorname{sign}(e_{i})=-1$ otherwise. Note that the gain of a closed walk
is well-defined as it is invariant by edge inversions or switchings. A closed
walk with zero (resp. nonzero) gain is called _balanced_ (resp. _unbalanced_).
A $\mathbb{Z}$-labelled graph is _balanced_ if every closed walk, or
equivalently every cycle, is balanced. Balancedness is preserved by minor
operations. A balanced $\mathbb{Z}$-labelled graph is isomorphic to a
$\mathbb{Z}$-labelled graph with all labels equal to $0$. See, e.g., [11] for
more details.

##  3 Periodic Frameworks and the Realizable Dimension of
$\mathbb{Z}$-symmetric Graphs

In this secton we introduce basic notation for periodic frameworks. Note that
throughout the paper we distinguish an affine $d$-dimensional framework and a
framework in $\mathbb{R}^{d}$.

###  3.1 Fixed-lattice model

Recall that in this paper we consider frameworks with one-dimensional
periodicity and assume that the underlying lattice is fixed. In order to
visualize the effect of the fixed lattice, we introduce additional notations
which are special in this paper.

Let $(\hat{G}^{\circ},z)$ be a $\mathbb{Z}$-labelled graph obtained from
$(\hat{G},z)$ by adding a new vertex $L$ not in $\hat{V}$ and a selfloop
$e_{L}$ incident to $L$ with a label $+1$. The edge set
$\hat{E}\cup\\{e_{L}\\}$ of $\hat{G}^{\circ}$ is denoted as $\hat{E}^{\circ}$.
The addition of the selfloop $e_{L}$ to $(\hat{G},z)$ results in the addition
of a new exceptional edge orbit to the lift graph $G$ of $(\hat{G},z)$. The
new edge orbit is denoted as $E_{L}$. Then there is an obvious correspondence
between $(E\cup E_{L})/\mathbb{Z}$ and $\hat{E}^{\circ}\cup\\{e_{L}\\}$.
Hence, in the subsequent discussion, we sometimes identify $(E\cup
E_{L})/\mathbb{Z}$ and $\hat{E}^{\circ}\cup\\{e_{L}\\}$ if it is clear from
the context.

A framework is called _periodic_ if it is $\ell$-periodic for some vector
$\ell$. Since our focus in this paper is the model in which the underlying
lattice length is fixed, we say that two periodic frameworks $(G,p)$ and
$(G,q)$ are _equivalent_ if $\|p(u)-p(v)\|=\|q(u)-q(v)\|$ for all $uv\in E(G)$
and their lattice vectors have the same lengths. Then a $\mathbb{Z}$-symmetric
graph $G$ is $d$-realizable if and only if every periodic framework $(G,p)$ in
any dimension admits an equivalent periodic framework in $\mathbb{R}^{d}$.

###  3.2 Realizable dimension of $\mathbb{Z}$-labelled graphs

We say that a $\mathbb{Z}$-labelled graph is _$d$ -realizable_ if its lift
graph is $d$-realizable, and the _realizable dimension_
$\operatorname{rd}(\hat{G},z)$ of a $\mathbb{Z}$-labelled graph $(\hat{G},z)$
is defined to be the realizable dimension of its lift graph. We verify the
minor monotonicity of the parameter.

######  Proposition 3.1.

If a $\mathbb{Z}$-labelled graph $(\hat{G},z)$ is a minor of a
$\mathbb{Z}$-labelled graph $(\hat{H},w)$, then
$\operatorname{rd}(\hat{G},z)\leq\operatorname{rd}(\hat{H},w)$.

###### Proof.

It suffices to show the statement in two cases: (i) $(\hat{G},z)$ is a
subgraph of $(\hat{H},w)$, (ii) $(\hat{G},z)=(\hat{H}/e,w)$ for an edge
$e\in\hat{E}(\hat{H})$. Let $G$ (resp. $H$) be the lift graph of $(\hat{G},z)$
(resp. $(\hat{H},w)$).

For (i), suppose that $(\hat{G},z)$ is a subgraph of $(\hat{H},w)$. Let
$(G,p)$ be a periodic framework in some dimension. Take a periodic framework
$(H,q)$ in the same dimension such that $q|_{V(G)}=p$. By definition, $(H,q)$
admits an equivalent framework $(H,q^{\prime})$ in $\mathbb{R}^{d}$, where
$d=\operatorname{rd}(H)$. Then $(G,q^{\prime}|_{V(G)})$ is equivalent to
$(G,p)$. Hence $G$ is $d$-realizable. Thus the statement holds in the case
(i).

For (ii), suppose that $(\hat{G},z)=(\hat{H}/e,w)$ for an edge
$e=(i,j;0)\in\hat{E}(\hat{H})$. Let $\hat{V}\subset V(H)$ be a representative
vertex set such that the quotient $\mathbb{Z}$-labelled graph of $H$ with
respect to $\hat{V}$ is $(\hat{H},w)$. Let $(G,p)$ be a periodic framework in
some dimension. Take a periodic framework $(H,q)$ in the same dimension such
that $q|_{V(G)}=p$ and $q(i)=q(j)$. By definition, $(H,q)$ admits an
equivalent framework $(H,q^{\prime})$ in $\mathbb{R}^{d}$ with
$d=\operatorname{rd}(H)$. Then, by the edge length constraint on $e$, we have
$q^{\prime}(i)=q^{\prime}(j)$. Then equalities on the other edge lengths in
$\hat{E}(\hat{H})$ implies that $(G,q^{\prime}|_{V(G)})$ is equivalent to
$(G,p)$. Hence $G$ is $d$-realizable. Thus the statment holds in the case
(ii). ∎

By Proposition 3.1, the set of $d$-realizable $\mathbb{Z}$-labelled graphs is
minor closed. We now state our main result in terms of $\mathbb{Z}$-symmetric
graphs. Let $(K_{k},0)$ be the balanced complete graph on $k$ vertices. Let
$K_{3}^{\bullet\bullet}$ be a directed multigraph on $\\{1,2,3\\}$ whose edge
set consists of a single edge from $1$ to $2$ and parallel edges between
$\\{1,3\\}$ and $\\{2,3\\}$.

######  Theorem 3.2.

For a $\mathbb{Z}$-symmetric graph $G$, the followings hold:

  1. (i)

$\operatorname{rd}(G)\leq 1$ if and only if $G$ has no minor isomorphic to the
lift graph of $(K_{3},0)$ nor to the lift graph of $(K_{2}^{\bullet},z)$ for
any simple labelling $z$.

  2. (ii)

$\operatorname{rd}(G)\leq 2$ if and only if $G$ has no minor isomorphic to the
lift graph of $(K_{4},0)$ nor to the lift graph of
$(K_{3}^{\bullet\bullet},z)$ for any simple labelling $z$.

The proof of Theorem 3.2 is given in Section 7. We remark that a minor closed
class of $\mathbb{Z}$-labelled graphs is not necessarily characterized by a
finite number of forbidden minors. We should remark that our definition of
minors for $\mathbb{Z}$-labelled graphs is consistent with that for
$\Gamma$-labelled graphs for a general group $\Gamma$ [10]. When the
underlying group $\Gamma$ is finite, every minor closed class of
$\Gamma$-labelled graphs is characterized by a finite number of forbidden
minors [10].

###  3.3 Quotient frameworks

For a periodic framework $(G,p)$, let $\hat{V}\subset V(G)$ be a
representative vertex set, $(\hat{G},z)$ be the quotient $\mathbb{Z}$-labelled
graph of $G$ with respect to $\hat{V}$, $\hat{p}=p|_{\hat{V}}$ be the
positions of representative vertices, and $\ell$ be the lattice vector. The
quadruple $(\hat{G},z,\hat{p},\ell)$ is called the _quotient framework_ of
$(G,p)$ with respect to $\hat{V}$. We remark that a quotient framework depends
on the choice of representative vertices.

We write $\mathrm{aff}(Y)$ for the affine span of a subset $Y$ of
$\mathbb{R}^{d}$ and $\operatorname{span}(Y)$ (or $\operatorname{span}Y$) for
its linear span. We usually denote the number of vertices of a
$\mathbb{Z}$-labelled graph $(\hat{G},z)$ as $n$ and denote
$\hat{V}(\hat{G})=\\{1,\ldots,n\\}$. A map
$\hat{p}:\hat{V}(\hat{G})\rightarrow\mathbb{R}^{d}$ is identified with a
matrix $\hat{P}\in\mathbb{R}^{d\times n}$ whose $i$th column is $\hat{p}(i)$.

For a periodic framework $(G,p)$ in $\mathbb{R}^{d}$, let
$(\hat{G},z,\hat{p},\ell)$ be the quotient framework of $(G,p)$ with respect
to $\hat{V}$. Then we have
$\mathrm{aff}(p(V))=\mathrm{aff}(\hat{p}(\hat{V}))+\operatorname{span}\\{\ell\\}$
and the affine dimension of $(G,p)$ equals to

$\rank\begin{pmatrix}\hat{P}&\ell\\\ \bm{1}_{n}^{\top}&0\end{pmatrix}-1,$

where $\bm{1}_{n}\in\mathbb{R}^{n}$ is the all one vector. In particular, the
affine dimension of a periodic framework $(G,p)$ is at most
$|\hat{V}|=|V/\mathbb{Z}|$. Thus, the realizable dimension
$\operatorname{rd}(G)$ of a $\mathbb{Z}$-symmetric graph $G$ is at most
$|V/\mathbb{Z}|$.

##  4 Lower Dimensional Affine Images and the Conic Condition

Since the seminal work by Connelly [4, 5, 6], affine transformations have
played an important role in the analysis of global or universal rigidity of
frameworks. In this section we adapt known facts on affine transformations of
frameworks to the periodic setting. Let $\mathcal{S}^{n}$ be the set of
$n\times n$ real symmetric matrices. For $A,B\in\mathcal{S}^{n}$, let $\langle
A,B\rangle=\tr(A^{\top}B)$ be the trace inner product. If a symmetric matrix
$A$ is positive semidefinite, we denote $A\succeq O$.

For a framework $(G,p)$ in $\mathbb{R}^{d}$, a matrix $A\in\mathbb{R}^{d\times
d}$, and a vector $t\in\mathbb{R}^{d}$, define an _affine image_
$q:V(G)\rightarrow\mathbb{R}^{d}$ of $p$ by $q(i)=Ap(i)+t$ for all $i\in
V(G)$. Then if $(G,p)$ and $(G,q)$ are equivalent, the equality of the length
of $uv\in E(G)$ gives

$(p(u)-p(v))^{\top}(A^{\top}A-I_{d})(p(u)-p(v))=0.$

In view of this, we say that an $\ell$-periodic framework $(G,p)$ in
$\mathbb{R}^{d}$ satisfies the _conic condition_ if the edge directions
including the lattice vector do not lie on a conic at infinity, i.e., if there
is no nonzero matrix $S\in\mathcal{S}^{d}$ satisfying

$(p(u)-p(v))^{\top}S(p(u)-p(v))=0\quad\text{ for all }uv\in E(G)\quad\text{
and }\quad\ell^{\top}S\ell=0.$ (1)

For example, for a periodic framework in $\mathbb{R}^{d}$, if there are two
hyperplanes $H_{1},H_{2}\subset\mathbb{R}^{d}$ such that every edge including
lattice vector is parallel to either $H_{1}$ or $H_{2}$, it does not satisfy
the conic condition, since $S=a_{1}a_{2}^{\top}+a_{2}a_{1}^{\top}$ satisfies
(1), where $a_{i}$ is a normal vector of $H_{i}$ for $i=1,2$. This in
particular implies that, if $(G,p)$ satisfies the conic condition, then it is
affine full dimensional.

The following proposition implies that, if $(G,p)$ does not satisfy the conic
condition, then not only it admits an equivalent affine transformation but
also has a lower affine-dimensional equivalent realization. The corresponding
statement for ordinary finite frameworks has been already discussed in [5]. We
check that the same argument works in the periodic setting for completeness.

######  Proposition 4.1.

Let $(G,p)$ be a periodic framework in $\mathbb{R}^{d}$ which does not satisfy
the conic condition. Then there exists an affine $d^{\prime}$-dimensional
periodic framework $(G,q)$ equivalent to it for some $d^{\prime}<d$.

###### Proof.

Let $S\in\mathcal{S}^{d}$ be a nonzero matrix satisfying (1). There is a real
number $t\in\mathbb{R}$ such that $I_{d}-tS\succeq O$ and
$d^{\prime}:=\rank(I_{d}-tS)\leq d-1$. Let $A\in\mathcal{S}^{d}$ be a singular
matrix satisfying $A^{2}=I_{d}-tS$, and define
$q:V(G)\rightarrow\mathbb{R}^{d}$ by $q(i)=Ap(i)$ for all $i\in V(G)$. Then
$(G,q)$ is equivalent to $(G,p)$ and its affine dimension is at most
$d^{\prime}$. As $(G,q)$ is an affine image of $(G,p)$, if $(G,p)$ is
periodic, $(G,q)$ is also periodic. ∎

##  5 Periodic Super Stability

In this section we introduce the concept of perodic super stability to prove
the lower bound of realizable dimension. Let $\bm{e}_{i}\in\mathbb{R}^{n}$ be
the $i$-th unit vector, and
$E_{i,j}=\bm{e}_{i}\bm{e}_{j}^{\top}\in\mathbb{R}^{n\times n}$. Let
$\bm{1}_{n+1}^{\prime}:=\begin{pmatrix}\bm{1}_{n}^{\top}&0\end{pmatrix}^{\top}\in\mathbb{R}^{n+1}$.
Let $\mathcal{L}^{n+1}:=\\{A\in\mathcal{S}^{n+1}:A\bm{1}_{n+1}^{\prime}=0\\}$
and $\mathcal{L}^{n+1}_{+}:=\\{A\in\mathcal{L}^{n+1}:A\succeq O\\}$.

###  5.1 Equilibrium stress and periodic super stability

Recall that for a quotient $\mathbb{Z}$-labelled graph $(\hat{G},z)$ of a
$\mathbb{Z}$-symmetric graph $G$, $(E\cup E_{L})/\mathbb{Z}$ and
$\hat{E}^{\circ}=\hat{E}\cup\\{e_{L}\\}$ are identified. A map $\omega:(E\cup
E_{L})/\mathbb{Z}\rightarrow\mathbb{R}$ can be considered as an edge weight on
$\hat{E}^{\circ}$.

For a periodic framework $(G,p)$ in $\mathbb{R}^{d}$, fix a representative
vertex set $\hat{V}\subset V$, and let $(\hat{G},z,\hat{p},\ell)$ be the
corresponding quotient framework. For an edge $e=(i,j;z(e))\in\hat{E}$, define
the indicator vector $i_{e}\in\mathbb{R}^{n+1}$ and the edge vector
$v_{e}\in\mathbb{R}^{d}$ by

$\displaystyle i_{e}:=\begin{pmatrix}\bm{e}_{j}-\bm{e}_{i}\\\
z(e)\end{pmatrix},$ $\displaystyle
v_{e}:=\begin{pmatrix}\hat{P}&l\end{pmatrix}i_{e}=\hat{p}(j)+z(e)l-\hat{p}(i),$

and for $e_{L}$, let $i_{e_{L}}:=\bm{e}_{n+1}$ and $v_{e_{L}}:=\ell$. Borcea
and Streinu [3] defined a rigidity matrix $R(\hat{G},z,\hat{p},\ell)$ of a
periodic framework by a $|\hat{E}^{\circ}|\times d(n+1)$ matrix whose row
indexed by $e=(i,j;z(e))\in E$ is

$\hbox{}\vbox{\kern 0.86108pt\hbox{$\kern 0.0pt\kern
2.5pt\kern-5.0pt\left[\kern
0.0pt\kern-2.5pt\kern-5.55557pt\vbox{\kern-0.86108pt\vbox{\vbox{
\halign{\kern\arraycolsep\hfil\@arstrut$\kbcolstyle#$\hfil\kern\arraycolsep&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep&&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep\cr
5.0pt\hfil\@arstrut$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
i$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle j$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
L\\\$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle\cdots 0\cdots$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-v_{e}^{\top}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\cdots 0\cdots$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle v_{e}^{\top}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\cdots 0\cdots$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle z(e)v_{e}^{\top}$\hfil\kern
5.0pt\crcr}}}}\right]$}},$

and a row indexed by $e_{L}$ is

$\hbox{}\vbox{\kern 0.86108pt\hbox{$\kern 0.0pt\kern
2.5pt\kern-5.0pt\left[\kern
0.0pt\kern-2.5pt\kern-5.55557pt\vbox{\kern-0.86108pt\vbox{\vbox{
\halign{\kern\arraycolsep\hfil\@arstrut$\kbcolstyle#$\hfil\kern\arraycolsep&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep&&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep\cr
5.0pt\hfil\@arstrut$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
L\\\$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle\cdots 0\cdots$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle\cdots
0\cdots$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle v_{e_{L}}^{\top}$\hfil\kern
5.0pt\crcr}}}}\right]$}},$

where each vertex has associated consecutive $d$ columns and the last $d$
columns are associated with the lattice. Note that if an edge $e$ is inverted,
the labelling becomes $-z(e)$ and the edge vector becomes $-v_{e}$, so
$R(\hat{G},z,\hat{p},\ell)$ is invariant by edge inversion. We have the
following lemma.

######  Lemma 5.1.

Let $(G,p)$ be a periodic framework and let $\hat{V},\hat{V}^{\prime}\subset
V(G)$ be representative vertex sets. Let $(\hat{G},z,\hat{p},\ell)$ (resp.
$(\hat{G}^{\prime},z^{\prime},\hat{p}^{\prime},\ell)$) be the quotient
framework of $(G,p)$ with respect to $\hat{V}$ (resp. $\hat{V}^{\prime}$).
Then for any $\omega:(E\cup E_{L})/\mathbb{Z}\rightarrow\mathbb{R}$,
$\omega\in\ker R(\hat{G},z,\hat{p},\ell)^{\top}$ if and only if $\omega\in\ker
R(\hat{G}^{\prime},z^{\prime},\hat{p}^{\prime},\ell)^{\top}$.

###### Proof.

We already checked that $R(\hat{G},z,\hat{p},\ell)$ is invariant by edge
inversion. It suffices to prove the statement when $i\in\hat{V}$ is replaced
by $i+\gamma\in\hat{V}^{\prime}$ and other representative vertices are the
same. Observe that $\omega$ is in the left kernel of
$R(\hat{G},z,\hat{p},\ell)$ if and only if

$\displaystyle-\sum_{e\in\delta_{\text{out}}(i)}\omega(e)v_{e}+\sum_{e\in\delta_{\text{in}}(i)}\omega(e)v_{e}=0$
$\displaystyle(i\in\hat{V}),$ (2)
$\displaystyle\sum_{e\in\hat{E}^{\circ}}\omega(e)z(e)v_{e}=0,$ (3)

where $\delta_{\text{out}}(i)$ (resp. $\delta_{\text{in}}(i)$) is the set of
edges outgoing from (resp. incoming to) $i$ in $\hat{G}$ (we assume that
selfloops incident to $i$ are not contained in $\delta_{\text{out}}(i)$ nor
$\delta_{\text{in}}(i)$). Suppose that $\omega$ satisfies (2) and (3). As
$v_{e}$ is independent of the choice of representative vertices, (2) remains
to hold. (3) for $(\hat{G}^{\prime},z^{\prime},\hat{p}^{\prime},\ell)$ becomes

$\displaystyle\sum_{e\in\hat{E}^{\circ}-\delta_{\text{out}}(i)-\delta_{\text{in}}(i)}\omega(e)z(e)v_{e}+\sum_{e\in\delta_{\text{out}}(i)}\omega(e)(z(e)-\gamma)v_{e}+\sum_{e\in\delta_{\text{in}}(i)}\omega(e)(z(e)+\gamma)v_{e}$
$\displaystyle=$
$\displaystyle\sum_{e\in\hat{E}^{\circ}}\omega(e)z(e)v_{e}+\gamma\left(-\sum_{e\in\delta_{\text{out}}(i)}\omega(e)v_{e}+\sum_{e\in\delta_{\text{in}}(i)}\omega(e)v_{e}\right),$

which is $0$, so (3) remains to hold. Thus we have confirmed the statement. ∎

Motivated by Lemma 5.1, a map $\omega:(E\cup
E_{L})/\mathbb{Z}\rightarrow\mathbb{R}$ is called an _equilibrium stress_ of
$(G,p)$ if, for some choice of representative vertices, it is in the left
kernel of $R(\hat{G},z,\hat{p},\ell)$ when considered as a vector in
$\mathbb{R}^{\hat{E}^{\circ}}$. We remark that the equation (2) corresponds to
an ordinary equilibrium condition if we interpret it in the periodic
framework, and the equation (3) seems a new relation which is special in the
periodic setting.

Let $(G,p)$ be a periodic framework and $(\hat{G},z)$ be a quotient
$\mathbb{Z}$-labelled graph of $G$. For an edge $e\in\hat{E}^{\circ}$, let
$F_{e}:=i_{e}i_{e}^{\top}\in\mathcal{S}^{n+1}$. As $i_{e}$ is orthogonal to
$\bm{1}_{n+1}^{\prime}$, $F_{e}\in\mathcal{L}^{n+1}$. $F_{e}$ is invariant by
edge inversion. For an equilibrium stress $\omega:(E\cup
E_{L})/\mathbb{Z}\rightarrow\mathbb{R}$ of $(G,p)$,
$L_{\hat{G},z,\omega}:=\sum_{e\in\hat{E}^{\circ}}\omega(e)F_{e}$ is called an
_equilibrium stress matrix_ of $(G,p)$. Although equilibrium stress matrix
changes by switching, the following lemma shows that the signature of it is
invariant.

######  Lemma 5.2.

Let $(\hat{G},z)$, $(\hat{G}^{\prime},z^{\prime})$ be quotient
$\mathbb{Z}$-labelled graphs of a $\mathbb{Z}$-symmetric graph $G$. Then for
$\omega:(E\cup E_{L})/\mathbb{Z}\rightarrow\mathbb{R}$, the signatures of
$L_{\hat{G},z,\omega}$ and $L_{\hat{G}^{\prime},z^{\prime},\omega}$ coincide.

###### Proof.

We have checked that $L_{\hat{G},z,\omega}$ is invariant by edge inversion.
Define the incidence matrix
$I(\hat{G},z)\in\mathbb{R}^{|\hat{E}^{\circ}|\times(n+1)}$ of $(\hat{G},z)$ as
a matrix whose row indexed by $e\in\hat{E}^{\circ}$ is $i_{e}^{\top}$. Then we
have
$L_{\hat{G},z,\omega}=I(\hat{G},z)^{\top}\operatorname{diag}(\omega)I(\hat{G},z)$.
In terms of an incidence matrix, a switching of $i$ by $\gamma$ results in
adding $\gamma$ times $i$th column of incidence matrix to the last column.
Hence, by Sylvester’s law of inertia, the signature is invariant by switching.
∎

We define the _stress signature_ $(n_{+},n_{-},n_{0})$ of an equilibrium
stress $\omega:(E\cup E_{L})/\mathbb{Z}\rightarrow\mathbb{R}$ of a periodic
framework $(G,p)$ to be the common signature of $L_{\hat{G},z,\omega}$, where
$n_{+}$ (resp. $n_{-}$, $n_{0}$) is the number of positive (resp. negative,
zero) eigenvalues of $L_{\hat{G},z,\omega}$. Since
$\omega^{\top}R(\hat{G},z,\hat{p},\ell)=0$ if and only if
$\begin{pmatrix}\hat{P}&\ell\end{pmatrix}L_{\hat{G},z,\omega}=0$,
$\bm{1}_{n+1}^{\prime}$ and the row vectors of
$\begin{pmatrix}\hat{P}&\ell\end{pmatrix}$ are always in the kernel of
$L_{\hat{G},z,\omega}$. So $n_{0}$ of the stress signature of an equilibrium
stress of $d$-dimensional periodic framework is at least $d+1$. A stress
signature of an equilibrium stress of $d$-dimensional periodic framework is
_nonnegative_ if $n_{-}=0$, and it is _full_ if $n_{0}=d+1$. We are now ready
to define periodic super stability.

######  Definition 5.3.

A periodic framework $(G,p)$ in $\mathbb{R}^{d}$ is _periodically super
stable_ if the following conditions hold:

  * (i)

It has an equilibrium stress whose stress signature is nonnegative and full.

  * (ii)

$(G,p)$ satisfies the conic condition.

Note that by (ii), a periodically super stable framework is affine full
dimensional.

######  Example 5.4.

Consider the $2$-dimensional periodic framework $(G,p)$ in Figure 2 (a). If
$\hat{V}$ is the set of white vertices in Figure 2 (a), Figure 2 (b) is the
quotient graph of $G$ with respect to $\hat{V}$ with the additional selfloop
$\\{e_{L}\\}$. An equilibrium stress $\omega:(E\cup
E_{L})/\mathbb{Z}\rightarrow\mathbb{R}$ of $(G,p)$ is shown in Figure 2 (c),
in which a number written on each edge shows a weight on the edge orbit it
belongs to. Then the equilibrium stress matrix is

$\hbox{}\vbox{\kern 0.86108pt\hbox{$\kern 0.0pt\kern
2.5pt\kern-5.0pt\left[\kern
0.0pt\kern-2.5pt\kern-5.55557pt\vbox{\kern-0.86108pt\vbox{\vbox{
\halign{\kern\arraycolsep\hfil\@arstrut$\kbcolstyle#$\hfil\kern\arraycolsep&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep&&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep\cr
5.0pt\hfil\@arstrut$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 2$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 3$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
L\\\1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-2$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
1\\\2$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-2$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
1\\\3$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle-2$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-2$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
4$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle-2\\\L$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle-2$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 1\\\$\hfil\kern 5.0pt\crcr}}}}\right]$}},$

which is positive semidefinite with rank $1$. Hence the stress signature is
$(n_{+},n_{-},n_{0})=(1,0,3)$, which is nonnegative and full. As $(G,p)$ has
at least three edge directions, it satisfies the conic condition. Hence the
periodic framework $(G,p)$ in Figure 2 (a) is periodically super stable.

(a)$x$$y$

$1$$2$$3$$+0$$+1$$+0$$+1$$+0$(b)$L$$+1$$e_{L}$

$-1$$1$$1$$-1$$1$$1$$-1$$1$$1$$1$$1$(c)$E_{L}$$-1$$-1$

Figure 2: (a) A $2$-dimensional periodic framework $(G,p)$ with a
representative vertex set $\hat{V}$ denoted by white circles. (b) The quotient
graph of $G$ with respect to $\hat{V}$ with the additional selfloop
$\\{e_{L}\\}$. (c) An equilibrium stress $\omega$ of $(G,p)$.

.

A periodic framework $(G,p)$ is _periodically universally rigid_ if every
periodic framework $(G,q)$ in any dimension equivalent to $(G,p)$ is congruent
to $(G,p)$. We have the following periodic analogue of [4]. A variant of the
following proposition for quotient frameworks has been shown in an unpublished
manuscript [7].

######  Proposition 5.5.

A periodically super stable framework is periodically universally rigid.

##  6 Obstacles

For a directed multigraph $D$ and two vertices $i,j$ of $D$, the
_multiplicity_ between $i$ and $j$ is the number of edges between $i$ and $j$
when the edge direction is forgotten. For a directed multigraph $D$, let
$\operatorname{si}(D)$ be the simple loopless undirected graph obtained from
$D$ by removing selfloops and forgetting the direction and the multiplicity.

###  6.1 Relationship with finite frameworks

The first observation for constructing obstacles is done by comparing the
realizable dimension of a $\mathbb{Z}$-labelled graph $(\hat{G},z)$ and the
realizable dimension of a finite graph $\operatorname{si}(\hat{G})$. We have
the following.

######  Proposition 6.1.

For a $\mathbb{Z}$-labelled graph $(\hat{G},z)$,
$\operatorname{rd}(\hat{G},z)\geq\operatorname{rd}(\operatorname{si}(\hat{G}))$.

The idea of the proof of Proposition 6.1 is simple. If
$(\operatorname{si}(\hat{G}),p)$ is a framework in some dimension, we
hypothetically regard this as a periodic framework $(G,p)$ with zero lattice
vector, where $G$ is a lift graph of $(\hat{G},z)$, and use the realizability
of $G$ to find a lower dimensional finite framework equivalent to
$(\operatorname{si}(\hat{G}),p)$. We make this argument more rigorous.

Let $(\hat{G},z)$ be a $\mathbb{Z}$-labelled graph. For each nonnegative
integer $d$, consider a map
$f_{d}:\mathbb{R}^{dn}\times\mathbb{R}^{d}\rightarrow\mathbb{R}^{\hat{E}^{\circ}}$
defined by $f_{d}(\hat{p},\ell):=(\|v_{e}\|^{2})_{e\in\hat{E}^{\circ}}$. Let
$\mathbb{R}^{d}_{\neq 0}:=\mathbb{R}^{d}\setminus\\{0\\}$. As the lattice
vector of a periodic framework is a nonzero vector, we have

$\\{(\hat{p},\ell):(\hat{G},z,\hat{p},\ell)\text{ is a quotient framework of a
periodic framework in
}\mathbb{R}^{d}\\}=\mathbb{R}^{dn}\times\mathbb{R}^{d}_{\neq 0}.$

Then $f_{0}(\mathbb{R}^{0}\times\mathbb{R}^{0}_{\neq 0})\subseteq
f_{1}(\mathbb{R}^{n}\times\mathbb{R}^{1}_{\neq 0})\subseteq\cdots$ is an
ascending chain of subsets of $\mathbb{R}^{\hat{E}^{\circ}}$. By definition,
$(\hat{G},z)$ is $d$-realizable if and only if
$f_{d}(\mathbb{R}^{dn}\times\mathbb{R}^{d}_{\neq
0})=f_{d+1}(\mathbb{R}^{(d+1)n}\times\mathbb{R}^{d+1}_{\neq 0})=\cdots$ holds,
and $\operatorname{rd}(\hat{G},z)$ equals to the minimum $d$ satisfying such
relation. The next lemma is a key. A similar argument can be found in [2].

######  Lemma 6.2.

For every nonnegative integer $d$, $\imaginary f_{d}$ is closed.

###### Proof.

For brevity, we denote $f:=f_{d}$. Let $\\{y_{t}\\}_{t\in\mathbb{N}}$ be a
sequence in $\imaginary f$ converging to $y$. We show that $y\in\imaginary f$.
We claim that there exists a closed ball
$B\subset\mathbb{R}^{dn}\times\mathbb{R}^{d}$ such that $B\cap
f^{-1}(y_{t})\neq\emptyset$ for all $t\in\mathbb{N}$. To see the claim, fix
vertices $v_{1},\ldots,v_{k}$ in each connected component of
$\operatorname{si}(\hat{G})$. Note that for a vertex set $\hat{U}$ of a
connected component of $\operatorname{si}(\hat{G})$, the value
$f(\hat{p},\ell)$ is invariant under a translation of $\hat{p}|_{\hat{U}}$.
Hence, there exists $(\hat{p},\ell)\in f^{-1}(y_{t})$ such that
$\hat{p}(v_{1})=\cdots=\hat{p}(v_{k})=0$. Then since $\|\ell\|$ is bounded and
$\|\hat{p}(j)+z(e)\ell-\hat{p}(i)\|$ is also bounded for all
$(i,j;e)\in\hat{E}$, one can deduce that $\|\hat{p}(j)\|$ is bounded for every
$j\in\hat{V}$ by triangle inequality. Hence $(\hat{p},\ell)$ is contained in a
ball whose radius is independent of $t$. Therefore $B\cap
f^{-1}(y_{t})\neq\emptyset$.

The rest of the argument is immediate. For each $t\in\mathbb{N}$, take
$(\hat{p}_{t},\ell_{t})\in f^{-1}(y_{t})\cap B$. Then by the compactness of
$B$, a sequence $\\{(\hat{p}_{t},\ell_{t})\\}_{t\in\mathbb{N}}$ has an
accumulation point $x=(\hat{p}^{*},\ell^{*})\in B$. Then, by the continuity of
$f$, we have $f(x)=y$. Thus $y\in\imaginary f$. ∎

We are now ready to prove Proposition 6.1.

###### Proof of Proposition 6.1.

Suppose that $(\hat{G},z)$ is $d$-realizable. Then, for any nonnegative
integer $d^{\prime}$, we have

$f_{d^{\prime}}(\mathbb{R}^{d^{\prime}n}\times\mathbb{R}^{d^{\prime}}_{\neq
0})\subseteq f_{d}(\mathbb{R}^{dn}\times\mathbb{R}^{d}_{\neq
0})\subseteq\imaginary f_{d}.$ (4)

Since the closure of
$\mathbb{R}^{d^{\prime}n}\times\mathbb{R}^{d^{\prime}}_{\neq 0}$ is
$\mathbb{R}^{d^{\prime}n}\times\mathbb{R}^{d^{\prime}}$, by the continuity of
$f_{d^{\prime}}$, the closure of
$f_{d^{\prime}}(\mathbb{R}^{d^{\prime}n}\times\mathbb{R}^{d}_{\neq 0})$
includes $\imaginary f_{d^{\prime}}$. Hence by Lemma 6.2 and (4), we get
$\imaginary f_{d^{\prime}}\subseteq\imaginary f_{d}$ for any $d^{\prime}$.

Let $(\operatorname{si}(\hat{G}),p)$ be a framework of a simple graph
$\operatorname{si}(\hat{G})$ in $\mathbb{R}^{d^{\prime}}$ for some
$d^{\prime}$. We show that there is an equivalent framework in
$\mathbb{R}^{d}$. As $\imaginary f_{d^{\prime}}\subseteq\imaginary f_{d}$,
there exists $(q,\ell)\in\mathbb{R}^{dn}\times\mathbb{R}^{d}$ such that
$f_{d}(q,\ell)=f_{d^{\prime}}(p,0)$. Then $\|\ell\|^{2}=0$, i.e., $\ell=0$.
Then the equiality $f_{d}(q,0)=f_{d^{\prime}}(p,0)$ implies that
$(\operatorname{si}(\hat{G}),q)$ is a framework in $\mathbb{R}^{d}$ equivalent
to $(\operatorname{si}(\hat{G}),p)$. Thus, $\operatorname{si}(\hat{G})$ is
$d$-realizable. ∎

Belk and Connelly [2] have shown that $\operatorname{rd}(K_{n})=n-1$ and
$\operatorname{rd}(K_{2,2,2})\geq 4$. Hence by Proposition 6.1, we obtain the
following obstacles in the periodic setting.

######  Corollary 6.3.

We have the followings.

  1. (i)

For any $\mathbb{Z}$-labelled graph $(K_{n},z)$,
$\operatorname{rd}(K_{n},z)\geq n-1$.

  2. (ii)

For any $\mathbb{Z}$-labelled graph $(K_{2,2,2},z)$,
$\operatorname{rd}(K_{2,2,2},z)\geq 4$.

###  6.2 Realizability of complete graphs

We now provide obstacles of $d$-realizability by determining
$\operatorname{rd}(\hat{G},z)$ for a $\mathbb{Z}$-labelled graph $(\hat{G},z)$
when $\operatorname{si}(\hat{G})$ is a complete graph. For a directed
multigraph $\hat{G}=(\hat{V},\hat{E})$, its _multiplicity graph_ is a simple
undirected graph on $\hat{V}$ such that distinct vertices $i,j\in\hat{V}$ are
adjacent if the multiplicity between $i$ and $j$ is at least $2$. We have the
following combinatorial statement of the linear matroid generated by
$\\{F_{e}:e\in\hat{E}^{\circ}\\}$.

######  Lemma 6.4.

Let $(\hat{G},z)$ be a $\mathbb{Z}$-labelled graph. Let
$\mathcal{F}(\hat{G},z):=\\{F_{e}:e\in\hat{E}^{\circ}\\}\subset\mathcal{L}^{n+1}$.
We have the followings:

  * (i)

The set of matrices $\mathcal{F}(\hat{G},z)$ is linearly independent if and
only if $\hat{G}$ has no selfloop, the multiplicity between any two vertices
is at most two, and the multiplicity graph of $\hat{G}$ is a forest.

  * (ii)

The set of matrices $\mathcal{F}(\hat{G},z)$ spans the whole space
$\mathcal{L}^{n+1}$ if and only if $\operatorname{si}(\hat{G})=K_{n}$ and the
multiplicity graph of $\hat{G}$ is spanning.

###### Proof.

Recall that $E_{i,j}$ denotes the square matrix of size $n+1$ whose $(i,j)$-th
entry is one and the remainig entries are zero. For $1\leq i<j\leq n$, define
$A_{i,j},B_{i,j}\in\mathcal{L}^{n+1}$ by
$A_{i,j}=E_{i,i}+E_{j,j}-E_{i,j}-E_{j,i}$ and
$B_{i,j}=E_{i,n+1}+E_{n+1,i}-E_{j,n+1}-E_{n+1,j}$. By the definition of
$\mathcal{L}^{n+1}$, $\dim\mathcal{L}^{n+1}=\binom{n+1}{2}$, and
$\\{A_{i,j}:1\leq i<j\leq n\\}\cup\\{B_{i,j}:\\{i,j\\}\in
E(T)\\}\cup\\{E_{n+1,n+1}\\}$ forms a basis of $\mathcal{L}^{n+1}$ for any
spanning tree $T$ on $\\{1,\ldots,n\\}$. Note that $F_{e_{L}}=E_{n+1,n+1}$.

Necessity of (i): Suppose that $\hat{G}$ contains a selfloop $e$, then
$\\{F_{e},F_{e_{L}}\\}$ is linearly dependent. Suppose that the multiplicity
between $i$ and $j$ is at least three. If $e_{1},e_{2}\in\hat{E}$ are two
parallel edges between $i$ and $j$, then we have

$\operatorname{span}\\{F_{e_{L}},F_{e_{1}},F_{e_{2}}\\}=\operatorname{span}\\{A_{i,j},B_{i,j},E_{n+1,n+1}\\}.$
(5)

If $e_{3}\in\hat{E}$ is another edge between $i$ and $j$, then $F_{e_{3}}$ is
in $\operatorname{span}\\{A_{i,j},B_{i,j},E_{n+1,n+1}\\}$. So, by (5),
$\\{F_{e_{L}}\\}\cup\\{F_{e_{i}}:i=1,2,3\\}$ is linearly dependent.

Suppose that the multiplicity graph contains a cycle on
$i_{1},\ldots,i_{t}\in\hat{V}$ ($t\geq 3$). Then $\hat{G}$ has parallel edges
$e_{k}^{1},e_{k}^{2}$ between $i_{k}$ and $i_{k+1}$ for $k=1,\ldots,t$
($i_{t+1}=i_{1}$). Let
$\mathcal{F}:=\\{F_{e_{L}}\\}\cup\\{F_{e_{j}^{i}}:i=1,2,j=1,\ldots,t\\}$. We
show $\mathcal{F}$ is linearly dependent. By (5), we have
$B_{i_{k},i_{k+1}}\in\operatorname{span}\\{F_{e_{L}},F_{e_{k}^{1}},F_{e_{k}^{2}}\\}\setminus\operatorname{span}\\{F_{e_{L}}\\}$
for each $k=1,\ldots,t$. Also by the definition of $B_{i,j}$, the identity
$\sum_{k=1}^{t}B_{i_{k},i_{k+1}}=0$ holds. Hence $\mathcal{F}$ are linearly
dependent. Thus the necessity of (i) follows.

Sufficiency of (i): For the sufficiency, by adding as many edges as possible,
it suffices to prove the statement when $\operatorname{si}(\hat{G})=K_{n}$,
$\hat{G}$ contains no selfloop, multiplicity between any two vertices is at
most two, and the multiplicity graph is a spanning tree $T$ on
$\\{1,\ldots,n\\}$. Then
$|\hat{E}^{\circ}|=|\hat{E}|+1=\binom{n}{2}+(n-1)+1=\binom{n+1}{2}=\dim\mathcal{L}^{n+1}$.
So, it suffices to show that the linear subspace $\mathcal{K}$, a subspace
spanned by $\\{F_{e}:e\in\hat{E}^{\circ}\\}$, contains a basis of
$\mathcal{L}^{n+1}$. By (5), $\mathcal{K}$ contains $A_{i,j},B_{i,j}$ for
$\\{i,j\\}\in E(T)$.

For $\\{i,j\\}\not\in E(T)$, we claim that $\mathcal{K}$ contains $A_{i,j}$.
To see this, let $i=i_{1},\ldots,i_{t}=j$ be a path in the multiplicity graph,
and let $e\in\hat{E}$ be an edge between $i$ and $j$. By (5), $\mathcal{K}$
contains $A_{i_{k},i_{k+1}}$ and $B_{i_{k},i_{k+1}}$ for $k=1,\ldots,t-1$.
Hence $B_{i_{t},i_{1}}=-\sum_{k=1}^{t-1}B_{i_{k},i_{k+1}}$ is contained in
$\mathcal{K}$. Since
$A_{i,j}=A_{i_{t},i_{1}}\in\operatorname{span}\\{F_{e_{L}},F_{e},B_{i_{t},i_{1}}\\}$,
$\mathcal{K}$ also contains $A_{i,j}$.

Since $F_{e_{L}}=E_{n+1,n+1}\in\mathcal{K}$, $\mathcal{K}$ contains a basis
$\\{A_{i,j}:1\leq i<j\leq n\\}\cup\\{B_{i,j}:\\{i,j\\}\in
E(T)\\}\cup\\{E_{n+1,n+1}\\}$. Thus the sufficiency of (i) follows.

Necessity of (ii): Suppose that $\mathcal{F}(\hat{G},z)$ spans
$\mathcal{L}^{n+1}$. Then there exists a subset
$\hat{E}^{\prime}\subseteq\hat{E}(\hat{G})$ containing $\\{e_{L}\\}$ such that
$\\{F_{e}:e\in\hat{E}^{\prime}\\}$ is a basis of $\mathcal{L}^{n+1}$. Define
the $\mathbb{Z}$-labelled subgraph $(\hat{H},w)$ of $(\hat{G},z)$ by
$\hat{V}(\hat{H})=\hat{V}(\hat{G})$, $\hat{E}(\hat{H})=\hat{E}^{\prime}$, and
$w:=z|_{\hat{E}^{\prime}}$. By (i), $\hat{H}$ has no selfloop and multiplicity
between any two vertices is at most two and the multiplicity graph of
$\hat{H}$ is a forest. Since $|\hat{E}(\hat{H})^{\circ}|=\binom{n+1}{2}$, this
implies that $\operatorname{si}(\hat{H})=K_{n}$ and the multiplicity graph of
$\hat{H}$ is a spanning tree. Hence $\operatorname{si}(\hat{G})=K_{n}$ and the
multiplicity graph of $\hat{G}$ is spanning.

Sufficiency of (ii): Suppose that $\operatorname{si}(\hat{G})=K_{n}$ and the
multiplicity graph of $\hat{G}$ is spanning. Then there is a
$\mathbb{Z}$-labelled subgraph $(\hat{H},w)$ of $(\hat{G},z)$ such that
$\operatorname{si}(\hat{H})=K_{n}$ and $\hat{H}$ contains no selfloop and
multiplicity between any two vertices is at most two and the multiplicity
graph is a spanning tree $T$ on $\\{1,\ldots,n\\}$. Then
$|\hat{E}(\hat{H})^{\circ}|=\binom{n+1}{2}$, so $\mathcal{F}(\hat{H},w)$ is a
basis of $\mathcal{L}^{n+1}$ by (i). Thus $\mathcal{F}(\hat{G},z)$ contains a
basis of $\mathcal{L}^{n+1}$. Hence $\mathcal{F}(\hat{G},z)$ is spanning.

∎

We are now ready to determine the realizable dimension of
$\mathbb{Z}$-labelled graphs $(\hat{G},z)$ satisfying
$\operatorname{si}(\hat{G})=K_{n}$.

######  Proposition 6.5.

Let $G$ be a $\mathbb{Z}$-symmetric graph and $(\hat{G},z)$ be its quotient
$\mathbb{Z}$-labelled graph satisfying $\operatorname{si}(\hat{G})=K_{n}$. We
have the followings:

  * (i)

If the multiplicity graph of $\hat{G}$ is not spanning,
$\operatorname{rd}(G)=n-1$.

  * (ii)

If the multiplicity graph of $\hat{G}$ is spanning, every periodic framework
$(G,p)$ in any dimension is periodically universally rigid. In particular,
$\operatorname{rd}(G)=n$.

###### Proof.

By $\operatorname{si}(\hat{G})=K_{n}$, Proposition 6.1, and Corollary 6.3 (i),
we have $n-1=\operatorname{rd}(K_{n})\leq\operatorname{rd}(G)$. Since the
realizable dimension is at most the number of vertex orbits, we also have
$\operatorname{rd}(G)\leq|V(G)/\mathbb{Z}|=n$. Let $\hat{V}\subset V$ be a
representative vertex set such that the quotient $\mathbb{Z}$-labelled graph
of $G$ with respect to $\hat{V}$ is $(\hat{G},z)$.

For (i), assume that the multiplicity graph of $\hat{G}$ is not spanning. Let
$(G,p)$ be an affine $n$-dimensional framework in $\mathbb{R}^{n}$. We show
that $(G,p)$ does not satisfy the conic condition. To see this, let
$\hat{p}=p|_{\hat{V}}$ and let $\ell$ be the lattice vector of $(G,p)$.
Observe that for a symmetric matrix $S\in\mathcal{S}^{n}$, (1) holds if and
only if

$\displaystyle\left\langle
S,\begin{pmatrix}\hat{P}&\ell\end{pmatrix}F_{e}\begin{pmatrix}\hat{P}&\ell\end{pmatrix}^{\top}\right\rangle=0$
$\displaystyle\quad\text{ for all }e\in\hat{E}^{\circ}$ (6)

holds. By Lemma 6.4 (ii), there are at most $\binom{n+1}{2}-1$ linearly
independent matrices in $\\{F_{e}:e\in\hat{E}^{\circ}\\}$. Hence there is a
nonzero matrix $S\in\mathcal{S}^{n}$ satisfying (6). Thus we have confirmed
that the conic condition does not hold. Then by Proposition 4.1, $(G,p)$
admits a $d^{\prime}$-dimensional equivalent periodic framework for some
$d^{\prime}<n$. Hence we have $\operatorname{rd}(G)\leq n-1$, so
$\operatorname{rd}(G)=n-1$.

For (ii), suppose that the multiplicity graph of $\hat{G}$ is spanning and
$(G,p)$ is a periodic framework in $\mathbb{R}^{d}$. Since every framework can
be considered as an affine full-dimensional framework in some dimension, and a
periodic framework is periodically universally rigid if and only if a periodic
framework congruent to it is periodic universally rigid, we may assume that
the affine dimension of $(G,p)$ is $d$. Let
$a_{1},\ldots,a_{n-d}\in\mathbb{R}^{n+1}$ be a basis of the kernel of

$\begin{pmatrix}\hat{P}&\ell\\\ \bm{1}_{n}^{\top}&0\end{pmatrix}.$

Since $a_{i}$ is orthogonal to $\bm{1}_{n+1}^{\prime}$, the matrix
$\Omega=\sum_{i=1}^{n-d}a_{i}a_{i}^{\top}$ is in $\mathcal{L}^{n+1}$. Since
$\mathcal{L}^{n+1}$ is spanned by $\\{F_{e}:e\in\hat{E}^{\circ}\\}$ by Lemma
6.4 (ii), there exists $\omega\in\mathbb{R}^{\hat{E}^{\circ}}$ such that
$\Omega=\sum_{e\in\hat{E}^{\circ}}\omega(e)F_{e}$. Then $\omega$ is an
equilibrium stress of $(G,p)$ and $\Omega=L_{\hat{G},z,\omega}$. Since
$\rank\Omega=n-d$ and $\Omega\succeq O$, the stress signature of $\omega$ is
full and nonnegative, so it certifies the first condition of periodic super
stability for $(G,p)$. It remains to check the conic condition. For this let
$S\in\mathcal{S}^{d}$ be a matrix satisfying (1). Then we have

$\left\langle\begin{pmatrix}\hat{P}&\ell\end{pmatrix}^{\top}S\begin{pmatrix}\hat{P}&\ell\end{pmatrix},F_{e}\right\rangle=0$

for all $e\in\hat{E}^{\circ}$. By translation, we may assume that the center
of gravity of $\hat{p}(\hat{V})$ is at the origin. Then
$\begin{pmatrix}\hat{P}&\ell\end{pmatrix}^{\top}S\begin{pmatrix}\hat{P}&\ell\end{pmatrix}\in\mathcal{L}^{n+1}$
and it is orthogonal to matrices $\\{F_{e}:e\in\hat{E}^{\circ}\\}$, which
spans $\mathcal{L}^{n+1}$ by Lemma 6.4 (ii). Hence
$\begin{pmatrix}\hat{P}&\ell\end{pmatrix}^{\top}S\begin{pmatrix}\hat{P}&\ell\end{pmatrix}=0$.
As $\begin{pmatrix}\hat{P}&\ell\end{pmatrix}$ is row independent, this implies
that $S=0$. Hence $(G,p)$ satisfies the conic condition. Thus we have
confirmed that $(G,p)$ is periodically super stable. By Proposition 5.5,
$(G,p)$ is periodically universally rigid.

If $(G,p)$ In particular, by considering the case $n=d$, we have
$\operatorname{rd}(G)=n$. ∎

##  7 Characterizations

###  7.1 Gluing operations

We extend the $k$-sum operations of finite graphs to $\mathbb{Z}$-labelled
graphs.

We denote a balanced simple complete graph of size $k\geq 0$ as $(K_{k},0)$.
Suppose that $(\hat{G},z)$ is a $\mathbb{Z}$-labelled graph and
$(\hat{G_{1}},z_{1})$, $(\hat{G_{2}},z_{2})$ are subgraphs of $(\hat{G},z)$
such that $\hat{V_{1}}\cup\hat{V_{2}}=\hat{V}$,
$\hat{E_{1}}\cup\hat{E_{2}}=\hat{E}$, and $z_{i}=z|_{\hat{E_{i}}}$ for
$i=1,2$. Then we say that $(\hat{G},z)$ is the _union_ of
$(\hat{G_{1}},z_{1})$ and $(\hat{G_{2}},z_{2})$, and it is denoted as
$(\hat{G_{1}},z_{1})\cup(\hat{G_{2}},z_{2})$. The _intersection_ of
$(\hat{G_{1}},z_{1})$ and $(\hat{G_{2}},z_{2})$ is defined as a
$\mathbb{Z}$-labelled graph on
$(\hat{V_{1}}\cap\hat{V_{2}},\hat{E_{1}}\cap\hat{E_{2}})$ with the edge
labelling $z_{1}|_{\hat{E_{1}}\cap\hat{E_{2}}}$, and it is denoted as
$(\hat{G_{1}},z_{1})\cap(\hat{G_{2}},z_{2})$. If $z_{1}=0$ and
$(\hat{G_{1}},0)\cap(\hat{G_{2}},z_{2})=(K_{k},0)$, then
$(\hat{G_{1}},0)\cup(\hat{G_{2}},z_{2})$ is called the _balanced $k$-sum_ of
$(\hat{G_{1}},0)$ and $(\hat{G_{2}},z_{2})$. We show that balanced $k$-sum
preserves $d$-realizability.

######  Lemma 7.1.

Let $(\hat{G},z)$ be a balanced $k$-sum of $(\hat{G_{1}},0)$ and
$(\hat{G_{2}},z_{2})$ for some $k$. Then
$\operatorname{rd}(\hat{G},z)=\max\\{\operatorname{rd}(\hat{G_{1}},0),\operatorname{rd}(\hat{G_{2}},z_{2})\\}$.

###### Proof.

As $(\hat{G_{1}},0)$ and $(\hat{G_{2}},z_{2})$ are subgraphs of $(\hat{G},z)$,
minor monotonicity of $\operatorname{rd}(\cdot)$ implies
$\operatorname{rd}(\hat{G},z)\geq\max\\{\operatorname{rd}(\hat{G_{1}},0),\operatorname{rd}(\hat{G_{2}},z_{2})\\}$.

For the converse inequality, suppose that $(\hat{G_{1}},0)$ and
$(\hat{G_{2}},z_{2})$ are $d$-realizable. Let $G=(V,E)$ be the lift graph of
$(\hat{G},z)$ and let $\hat{V}\subset V$ be a representative vertex set such
that the quotient $\mathbb{Z}$-labelled graph of $G$ with respect to $\hat{V}$
is $(\hat{G},z)$. Let $G_{i}=(V_{i},E_{i})$ be the lift graph of
$(\hat{G_{1}},z_{i})$, and let $\hat{V}_{i}=V_{i}\cap\hat{V}$ for each
$i=1,2$, where $z_{1}=0$. Note that $\hat{U}:=\hat{V}_{1}\cap\hat{V}_{2}$
forms a clique of size $k$ in $G$. Consider a periodic framework $(G,p)$ in
some dimension. We show that $(G,p)$ admits an equivalent periodic framework
in $\mathbb{R}^{d}$.

As both $G_{1}$, $G_{2}$ are $d$-realizable, there exists a periodic framework
$(G_{i},q_{i})$ in $\mathbb{R}^{d}$ equivalent to $(G_{i},p|_{V_{i}})$ for
$i=1,2$. Let $\ell_{i}$ be the lattice vector of $(G_{i},q_{i})$ for $i=1,2$.
As $\hat{U}$ forms a clique in $G$, the finite frameworks
$(K_{\hat{U}},q_{1}|_{\hat{U}})$ and $(K_{\hat{U}},q_{2}|_{\hat{U}})$ are
congruent, where $K_{\hat{U}}$ is a complete graph on $\hat{U}$. Hence there
is an orthogonal matrix $A\in O(\mathbb{R}^{d})$ and $t\in\mathbb{R}^{d}$ such
that $q_{2}(v)=Aq_{1}(v)+t$ for all $v\in\hat{U}$. Define
$q:V(G)\rightarrow\mathbb{R}^{d}$ by $q(v+\gamma):=Aq_{1}(v)+t+\gamma\ell_{2}$
for $v\in\hat{V}_{1}$ and $\gamma\in\mathbb{Z}$, and
$q(v+\gamma):=q_{2}(v)+\gamma\ell_{2}$ for $v\in\hat{V}_{2}$ and
$\gamma\in\mathbb{Z}$. Then we claim that that $(G,p)$ is equivalent to
$(G,q)$. For an edge in $E_{2}$, its length in $p$ equals to its length in
$q_{2}$, so it equals to its length in $q$. For an edge $e\in E_{1}$, as
$(\hat{G_{1}},0)$ is balanced, there is an edge $e^{\prime}$ in the same orbit
as $e$ whose endvertices belong to $\hat{V}_{1}$. So it suffices to check the
equality of an edge length of $e^{\prime}$ in $p$ and $q$, which holds as $A$
is an orthogonal matrix. Thus we have checked that $(G,p)$ is equivalent to
$(G,q)$. Hence the converse inequality follows. ∎

$1$$3$$2$$+0$$+0$$+1$$+0$(a)

$1$$4$$2$$+0$$+0$$+1$(b)

$1$$3$$2$$4$$+0$$+0$$+1$$+0$$+0$$+1$(c)

Figure 3: (a), (b) $2$-realizable $\mathbb{Z}$-labelled graphs. (c) The union
of (a) and (b), which is not $2$-realizable.

We remark that balancedness of one of the $\mathbb{Z}$-labelled graphs in
Lemma 7.1 is necessary, i.e., even if $(G_{1},z_{1})$ and $(G_{2},z_{2})$ are
$d$-realizable and $(G_{1},z_{1})\cap(G_{2},z_{2})=(K_{k},0)$ for some $k$,
$(G_{1},z_{1})\cup(G_{2},z_{2})$ may not be $d$-realizable. For example,
consider $\mathbb{Z}$-labelled graphs (a), (b) in Figure 3. The intersection
of (a) and (b) is $(K_{2},0)$, and by Proposition 6.5 (i), (a) and (b) are
$2$-realizable. On the other hand, their union shown in Figure 3 (c) is not
$2$-realizable since if an edge between $1$ and $4$ is contracted, it becomes
a graph $(K_{3}^{\bullet\bullet},z)$ for some labelling $z$, which is not
$2$-realizable by Proposition 6.5 (ii).

We provide another operation which also preserves $d$-realizability. If
$(\hat{G},z)=(\hat{G_{1}},z_{1})\cup(\hat{G_{2}},z_{2})$ and
$\hat{V}(\hat{G}_{1})\cap\hat{V}(\hat{G}_{2})=\emptyset$, $(\hat{G},z)$ is
called the disjoint union of $(\hat{G_{1}},z_{1})$ and $(\hat{G_{2}},z_{2})$.
For convenience, we consider that an empty $\mathbb{Z}$-labelled graph is a
complete graph and its multiplicity graph is spanning.

######  Lemma 7.2.

Let $(\hat{G},z)=(\hat{G_{1}},z_{1})\cup(\hat{G_{2}},z_{2})$ and let
$(\hat{H},w)=(\hat{G_{1}},z_{1})\cap(\hat{G_{2}},z_{2})$. Suppose that
$\operatorname{si}(\hat{H})$ is a complete graph and the multiplicity graph of
$\hat{H}$ is spanning. Then we have
$\operatorname{rd}(\hat{G},z)=\max\\{\operatorname{rd}(\hat{G_{1}},z_{1}),\operatorname{rd}(\hat{G_{2}},z_{2})\\}$.

###### Proof.

By the same argument in the first part of the proof of Proposition 7.1, it
suffices to prove
$\operatorname{rd}(\hat{G},z)\leq\max\\{\operatorname{rd}(\hat{G_{1}},0),\operatorname{rd}(\hat{G_{2}},z_{2})\\}$.
The case when $(\hat{H},w)$ is empty is trivial. Suppose that $(\hat{H},w)$ is
not empty. Let $H$ be the lift graph of $(\hat{H},w)$. Note that, by
Proposition 6.5 (ii), every periodic realization of $H$ is universally rigid.
Now the proof follows the same line as Lemma 7.1. We use the same notation as
in the proof of Lemma 7.1. For a given periodic framework $(G,p)$,
$(G_{i},p|_{\hat{V_{i}}})$ admits an equivalent framework $(G_{i},q_{i})$ for
$i=1,2$ in $\mathbb{R}^{d}$, where
$d=\max\\{\operatorname{rd}(\hat{G_{1}},z_{1}),\operatorname{rd}(\hat{G_{2}},z_{2})\\}$.
Then by the periodical universal rigidity of $(H,p|_{V(H)})$, one can take an
orthogonal matrix $A\in O(\mathbb{R}^{d})$ and $t\in\mathbb{R}^{d}$ satisfying
$q_{2}(v)=Aq_{1}(v)+t$ for all $v\in\hat{U}$ and $\ell_{2}=A\ell_{1}$, where
$\ell_{i}$ is the lattice vector of $(G_{i},q_{i})$. Then, one can check that
the same $(G,q)$ given in the proof of Lemma 7.1 is equivalent to $(G,p)$. ∎

A special case of the situation in Lemma 7.2 is when
$\hat{V}_{1}\cap\hat{V}_{2}$ is a singleton. In this case, the operation to
take their union is called a _$1$ -sum_.

###  7.2 Characterization for $d=1$

Let $\mathcal{F}(K_{2}^{\bullet})$ be the set of all simple
$\mathbb{Z}$-labelled graphs of the form $(K_{2}^{\bullet},z)$ for some $z$.

######  Theorem 7.3.

For a $\mathbb{Z}$-labelled graph $(\hat{G},z)$, the followings are
equivalent:

  1. (i)

$\operatorname{rd}(\hat{G},z)\leq 1$.

  2. (ii)

$(\hat{G},z)$ has no minor isomorphic to a $\mathbb{Z}$-labelled graph in
$\mathcal{F}(K_{2}^{\bullet})\cup\\{(K_{3},0)\\}$.

  3. (iii)

$(\hat{G},z)$ is obtained by a sequence of disjoint unions and $1$-sums of
$\mathbb{Z}$-labelled graphs in $\mathcal{F}$, where $\mathcal{F}$ consists of
all $\mathbb{Z}$-labelled graphs isomorphic to either $(K_{2},0)$ or a
$\mathbb{Z}$-labelled graph with single vertex.

  4. (iv)

$\hat{G}$ does not contain a cycle other than selfloops.

###### Proof.

By Proposition 6.5, $\operatorname{rd}(K_{2}^{\bullet},z)=2$ for any labelling
$z$ and $\operatorname{rd}(K_{3},0)=2$, so by minor monotonocity (i) implies
(ii). By Proposition 6.5, $\operatorname{rd}(K_{2},0)=1$ and the realizable
dimension of a $\mathbb{Z}$-labelled graph with single vertex is at most $1$.
So one can inductively check that (iii) implies (i) using Lemma 7.1 and Lemma
7.2. Since any cycle (except for selfloops) in $\hat{G}$ can be contracted to
either $(K_{2}^{\bullet},z)\in\mathcal{F}(K_{2}^{\bullet})$ or $(K_{3},0)$,
(ii) implies (iv). Finally if $(\hat{G},z)$ satisfies (iv),
$\operatorname{si}(\hat{G})$ is a forest and the multigraph $\hat{G}$ has no
parallel edge. Hence each connected component is obtained by a sequence of
$1$-sums of $\mathbb{Z}$-labelled graphs in $\mathcal{F}$. ∎

We remark that as the minor relation between $\mathbb{Z}$-labelled graphs is
equivalent to the minor relation between lift graphs, Theorem 3.2 (i)
immediately follows from the equivalence of (i) and (ii) in Theorem 7.3. Given
a $\mathbb{Z}$-labelled graph $(\hat{G},z)$, the cycle-free condition (iv) is
checkable first by checking if there are any parallel edges, and then by
checking if $\operatorname{si}(\hat{G})$ contains a cycle. This gives a
polynomial time algorithm to check if a given $\mathbb{Z}$-labelled graph is
$1$-realizable.

###  7.3 Characterization for $d=2$

Recall that $K_{3}^{\bullet\bullet}$ is a directed multigraph on $\\{1,2,3\\}$
whose edge set consists of a single edge from $1$ to $2$ and parallel edges
between $\\{1,3\\}$ and $\\{2,3\\}$. Let $\mathcal{F}(K_{3}^{\bullet\bullet})$
be the set of all simple $\mathbb{Z}$-labelled graphs of the form
$(K_{3}^{\bullet\bullet},z)$ for some edge labelling $z$.

######  Lemma 7.4.

If a $\mathbb{Z}$-labelled graph $(\hat{G},z)$ has no minor isomorphic to a
$\mathbb{Z}$-labelled graph in
$\mathcal{F}(K_{3}^{\bullet\bullet})\cup\\{(K_{4},0)\\}$, then a simple graph
$\operatorname{si}(\hat{G})$ does not have $K_{4}$ as a minor.

###### Proof.

Suppose, on the contrary, that $K_{4}$ is a minor of a simple graph
$\operatorname{si}(\hat{G})$. Then $(\hat{G},z)$ has a $\mathbb{Z}$-labelled
minor $(K_{4},w)$. As $(K_{4},0)$ is not a minor of $(\hat{G},z)$, $(K_{4},w)$
is not balanced. We can further say that $(K_{4},w)$ has at least two
unbalanced cycles since the sum of labels along four cycles $1\rightarrow
2\rightarrow 3\rightarrow 1$, $2\rightarrow 3\rightarrow 4\rightarrow 2$,
$3\rightarrow 4\rightarrow 1\rightarrow 3$, $4\rightarrow 1\rightarrow
2\rightarrow 4$ is zero, where $1,2,3,4$ are vertices of $(K_{4},w)$. Then by
contracting the common edge of two unbalanced cycles, one obtains
$(K_{3}^{\bullet\bullet},z)$ for some simple labelling $z$, which is a
contradiction. ∎

We are now ready to characterize $2$-realizable $\mathbb{Z}$-labelled graphs.

######  Theorem 7.5.

For a $\mathbb{Z}$-labelled graph $(\hat{G},z)$, the followings are
equivalent:

  1. (i)

$\operatorname{rd}(\hat{G},z)\leq 2$.

  2. (ii)

$(\hat{G},z)$ has no minor isomorphic to a $\mathbb{Z}$-labelled graph in
$\mathcal{F}(K_{3}^{\bullet\bullet})\cup\\{(K_{4},0)\\}$.

  3. (iii)

$(\hat{G},z)$ is a subgraph of a $\mathbb{Z}$-labelled graph obtained by a
sequence of disjoint unions, $1$-sums and balanced $2$-sums of
$\mathbb{Z}$-labelled graphs in $\mathcal{F}$, where $\mathcal{F}$ consists of
all $\mathbb{Z}$-labelled graphs isomorphic to either $(K_{3},0)$ or a
$\mathbb{Z}$-labelled graph with at most two vertices.

###### Proof.

By Proposition 6.5, we have $\operatorname{rd}(K_{3}^{\bullet\bullet},z)=3$
for any $z$ and $\operatorname{rd}(K_{4},0)=3$, so by minor monotonicity, (i)
implies (ii). By Proposition 6.5, $\operatorname{rd}(K_{3},0)=2$ holds, and
$\mathbb{Z}$-labelled graphs with at most two vertices are $2$-realizable. So
one can inductively check that (iii) implies (i) by Lemma 7.1 and Lemma 7.2.
It remains to prove a combinatorial statement that (ii) implies (iii). For
this, we may assume that $\hat{G}$ does not have a selfloop. We prove this by
induction on $|\hat{V}|$. When $|\hat{V}|=1,2,3$, one can directly check that
the statement holds from Proposition 6.5. Suppose, on the contrary,
$(\hat{G},z)$ satisfies (ii), but not (iii). Then $\operatorname{si}(\hat{G})$
is $2$-connected, since otherwise $(\hat{G},z)$ is a disjoint union or a
$1$-sum of graphs satisfying (ii) with smaller vertices, so by induction
hypothesis, $(\hat{G},z)$ satisfies (iii), which is a contradiction. By Lemma
7.4, $\operatorname{si}(\hat{G})$ does not have $K_{4}$ as a minor, so
$\operatorname{si}(\hat{G})$ has a vertex $v\in\hat{V}$ with degree two in
$\operatorname{si}(\hat{G})$ (cf. [8]). Let $x,y$ be two neighbors of $v$ in
$\operatorname{si}(\hat{G})$. By $2$-connectivity, there is a path in
$\operatorname{si}(\hat{G})$ between $x$ and $y$ not passing through $v$.
Hence to exclude $(K_{3}^{\bullet\bullet},z)$-minor, either multiplicity
between $v$ and $x$ or multiplicity between $v$ and $y$ in $\hat{G}$ must be
one.

Suppose that both multiplicities are one in $\hat{G}$. Let $e_{1}$ (resp.
$e_{2}$) be an edge between $v$ and $x$ (resp. $v$ and $y$). Switch at $x$ and
$y$ so that both labels of $e_{1}$ and $e_{2}$ are zero. Then $(\hat{G},z)$ is
a subgraph of a balanced $2$-sum of $(K_{3},0)$ and $(\hat{G}/e_{1},z)$. As
$(\hat{G}/e_{1},z)$ satisfies (ii) and the number of vertices is smaller than
$|\hat{V}|$, it satisfies (iii) by induction hypothesis. Then $(\hat{G},z)$
also satisfies (iii), which is a contradiction.

So we may assume that, in $\hat{G}$, the multiplicity between $v$ and $y$ is
$1$ and the multiplicity between $v$ and $x$ is at least $2$. We claim that
$(\hat{G}-v,z)$ is balanced. To see this, suppose, on the contrary, that
$(\hat{G}-v,z)$ contains an unbalanced cycle $C$. By Menger’s theorem, in
$\operatorname{si}(\hat{G})$, there exist vertex disjoint paths $P_{1}$ and
$P_{2}$ such that $P_{1}$ connects $u_{1}\in V(C)$ and $x$, $P_{2}$ connects
$u_{2}\in V(C)$ and $y$, and $V(P_{i})\cap V(C)=\\{u_{i}\\}$ for $i=1,2$.
Contract $P_{1}$ and $P_{2}$, and contract $C$ to a pair of parallel edges.
Then we obtain a $(K_{3}^{\bullet\bullet},z)$-minor, which is a contradiction.
Hence $(\hat{G}-v,z)$ is balanced.

Switch all the labels of edges in $\hat{E}[\hat{G}-v]$ to $0$. We prove that
$(\hat{G},z)$ satisfies (iii). For this, by adding an edge if necessary, we
may assume that $(x,y;0)\in\hat{E}(\hat{G})$. $(\hat{G}-v,0)$ is balanced and
$\operatorname{si}(\hat{G}-v)$ is an ordinary graph minor of
$\operatorname{si}(\hat{G})$, which does not contain $K_{4}$ as a minor. Hence
$(\hat{G}-v,0)$ satisfies (ii). Let $(\hat{G}[\\{x,y,v\\}],z)$ be a
$\mathbb{Z}$-labelled graph in which the underlying graph is an induced
directed multigraph of $\hat{G}$ on $\\{x,y,v\\}$ and the edge labelling is
restricted to the remaining edges. Then it is a $\mathbb{Z}$-labelled graph
minor of $(\hat{G},z)$, so it satisfies (ii). By induction hypothesis, both
$(\hat{G}-v,0)$ and $(\hat{G}[\\{x,y,v\\}],z)$ satisfy (iii). Since
$(\hat{G},z)$ is a balanced $2$-sum of $(\hat{G}-v,0)$ and
$(\hat{G}[\\{x,y,v\\}],z)$, $(\hat{G},z)$ satisfies (iii). But this
contradicts our assumption that $(\hat{G},z)$ does not satisfy (iii). Thus we
have confirmed that (ii) implies (iii). ∎

We remark that Theorem 3.2 (ii) immediately follows from Theorem 7.5. By
following the proof of Theorem 7.5, we obtain the following polynomial time
algorithm to check $2$-realizability of $\mathbb{Z}$-labelled graphs. Given a
$\mathbb{Z}$-labelled graph $(\hat{G},z)$, remove all the selfloops. If the
degree of every vertex in $\operatorname{si}(\hat{G})$ is at least $3$, it is
not $2$-realizable. Otherwise, if $\operatorname{si}(\hat{G})$ is not
connected or it has a size one separator, recursively check the smaller
$\mathbb{Z}$-labelled graphs. Otherwise $\operatorname{si}(\hat{G})$ has a
degree two vertex $v$ with neighbors $x,y$. If the multiplicity between $v$
and $x$ the multiplicity betwenn $v$ and $y$ are both $2$, it is not
$2$-realizable. If both multiplicities are one, contract $vx$ and check
recursively. In the remaining case, delete $v$ from $(\hat{G},z)$ and check if
$(\hat{G}-v,z)$ is balanced or not, which can be done by taking rooted
spanning tree in $\operatorname{si}(\hat{G})$ and by doing switching from the
root.

##  8 Closing Remark

A characterization of $3$-realizable $\mathbb{Z}$-labelled graphs is open. If
there is a size $2$ separator, we can provably reduce the size. So, by [2],
the characterization of $3$-realizable $\mathbb{Z}$-labelled graphs
$(\hat{G},z)$ is reduced to two cases; the first case is when the treewidth of
$\operatorname{si}(\hat{G})$ is at most $3$, and the second case is when
$\operatorname{si}(\hat{G})=C_{5}\times C_{2}$ or $V_{8}$. As in [18, 19], SDP
formulation might help to find an equivalent framework in lower affine
dimensional space.

Realizable dimension has been defined for other metric spaces such as
spherical metric space [12, 13] and $\ell_{p}$-space [9, 17]. In [12, 13], a
spherical variant $\operatorname{gd}^{=}$ of realizable dimension is
introduced, and graphs with $\operatorname{gd}^{=}$ at most $2,3$, or $4$ are
characterized. They also exploit SDP formulation and deduce a relationship
between $\operatorname{gd}^{=}$ and Colin de Verdière number $\nu^{=}$. It is
not clear if those results can be extended to $\mathbb{Z}$-labelled graphs.

#### Acknowledgement

This work was supported by JST PRESTO Grant Number JPMJPR2126, JST ERATO Grant
Number JPMJER1903, and JST ACT-X Grant Number JPMJAX2009, Japan.

## References

  * [1] M. Belk.  Realizability of graphs in three dimensions.  Discrete & Computational Geometry, 37(2):139–162, 2007.
  * [2] M. Belk and R. Connelly.  Realizability of graphs.  Discrete & Computational Geometry, 37(2):125–137, 2007.
  * [3] C. Borcea and I. Streinu.  Periodic frameworks and flexibility.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 466(2121):2633–2649, 2010.
  * [4] R. Connelly.  Rigidity and energy.  Invent. math., 66(1):11–33, 1982.
  * [5] R. Connelly.  Tensegrities and global rigidity.  In Shaping Space: Exploring Polyhedra in Nature, Art, and the Geometrical Imagination, pages 267–278. Springer, 2012.
  * [6] R. Connelly, S. J. Gortler, and L. Theran.  Affine rigidity and conics at infinity.  International Mathematics Research Notices, 2018(13):4084–4102, 2018.
  * [7] S. Dewar, B. Schulze, S. Tanigawa, and L. Theran.  Global rigidity of periodic frameworks.  manuscript.
  * [8] R. Diestel.  Graph Theory, 5ht edition, volume 173 of GTM.  Springer, 2016.
  * [9] S. Fiorini, T. Huynh, G. Joret, and A. Varvitsiotis.  The excluded minors for isometric realizability in the plane.  SIAM Journal on Discrete Mathematics, 31(1):438–453, 2017.
  * [10] J. Geelen and B. Gerards.  Excluding a group-labelled graph.  Journal of Combinatorial Theory, Series B, 99(1):247–253, 2009\.
  * [11] V. E. Kaszanitzky, B. Schulze, and S. Tanigawa.  Global rigidity of periodic graphs under fixed-lattice representations.  Journal of Combinatorial Theory, Series B, 146:176–218, 2021.
  * [12] M. Laurent and A. Varvitsiotis.  A new graph parameter related to bounded rank positive semidefinite matrix completions.  Mathematical Programming, 145(1-2):291–325, 2014.
  * [13] M. Laurent and A. Varvitsiotis.  Positive semidefinite matrix completion, universal rigidity and the strong arnold property.  Linear Algebra and its Applications, 452:292–317, 2014.
  * [14] J. Malestein and L. Theran.  Generic combinatorial rigidity of periodic frameworks.  Advances in Mathematics, 233(1):291–331, 2013.
  * [15] J. Malestein and L. Theran.  Generic rigidity with forced symmetry and sparse colored graphs.  Rigidity and Symmetry. Fields Institute Communications, 70:227–252, 2014.
  * [16] B. Schulze and W. Whiteley.  Rigidity of symmetric frameworks.  In Handbook of Discrete and Computational Geometry, pages 1633–1659. Chapman and Hall/CRC, 2017.
  * [17] M. Sitharam and J. Willoughby.  On flattenability of graphs.  In International Workshop on Automated Deduction in Geometry, pages 129–148. Springer, 2014.
  * [18] A. M. So.  A semidefinite programming approach to the graph realization problem: Theory, applications and extensions.  PhD thesis, Stanford University, 2007.
  * [19] A. M. So and Y. Ye.  A semidefinite programming approach to tensegrity theory and realizability of graphs.  In SODA, volume 6, pages 766–775, 2006.
  * [20] A. M. So and Y. Ye.  Theory of semidefinite programming for sensor network localization.  Math. Program., 109:367–384, 2007.