# Block-and-hole graphs:
Constructibility and $(3,0)$-sparsity

Bryan Gin–ge Chen<EMAIL_ADDRESS>,  James Cruickshank  School of
Mathematical and Statistical Sciences, University of Galway, Galway, Ireland.
<EMAIL_ADDRESS>and  Derek Kitson  Department of
Mathematics and Computer Studies, Mary Immaculate College, Thurles, Co.
Tipperary, Ireland<EMAIL_ADDRESS>
###### Abstract.

We show that minimally 3-rigid block-and-hole graphs, with one block or one
hole, are characterised as those which are constructible from $K_{3}$ by
vertex splitting, and also, as those having associated looped face graphs
which are $(3,0)$-tight. This latter property can be verified in polynomial
time by a form of pebble game algorithm. We also indicate connections to the
rigidity properties of polyhedral surfaces known as origami and to graph
rigidity in $\ell_{p}^{3}$ for $p\not=2$.

##  1\. Introduction

A finite simple graph is $3$-rigid if it forms the structure graph for an
infinitesimally rigid bar-and-joint framework in Euclidean $3$-space. If, in
addition, the removal of any edge from the graph results in a subgraph which
is not $3$-rigid then the graph is minimally $3$-rigid. A block-and-hole graph
is obtained by first triangulating a sphere, then removing the interiors of
some triangulated discs to create holes, and finally adjoining minimally
$3$-rigid graphs to the boundaries of some of the resulting holes to create
blocks. It is well known that a graph obtained from a triangulation of a
sphere is minimally $3$-rigid, see for example [9]. Whiteley ([20, Theorem
4.2]) showed that a block-and-hole graph with a single block and a single
hole, and common boundary length $k$, is minimally 3-rigid if and only if the
removal of any $k-1$ vertices does not disconnect the two boundary cycles. In
[7], it is shown that switching the blocks and holes in a block-and-hole graph
preserves minimal $3$-rigidity. The main theorem of [3] characterizes the
minimally 3-rigid block-and-hole graphs with a single block and finitely many
holes (or vice versa) as those which are $(3,6)$-tight. Moreover, Whiteley’s
result is generalised in the form of girth inequalities and a constructive
characterisation is obtained which uses the well-known graph move known as
vertex-splitting together with a form of graph fusion known as isostatic
substitution. In recent work, Jordán ([11]) has obtained a rank formula for
the $3$-dimensional rigidity matroid of a block-and-hole graph with a single
block.

In Section 2, we improve the constructive characterisation obtained in [3] by
circumventing the need for isostatic substitution. The main result, Theorem
2.15, characterises minimally $3$-rigid block-and-hole graphs, with one block
or one hole, as those for which an associated discus-and-hole graph is
constructible from the complete graph $K_{3}$ by a sequence of vertex
splitting operations. In Section 3, we present new characterisations of
minimal $3$-rigidity for block-and-hole graphs which are expressed in terms of
associated multigraphs, referred to as looped face graphs. The main result,
Theorem 3.3, shows that a block-and-hole graph, with one block or one hole, is
minimally $3$-rigid if and only if its associated looped face graphs are
$(3,0)$-tight. This latter property has a significant advantage that, unlike
$(3,6)$-tightness, it is verifiable in polynomial time by a pebble game
algorithm (see [14]). In Section 4, we apply our constructive characterisation
to show that $(3,6)$-tight discus-and-hole graphs are independent in any
3-dimensional real normed linear space which is smooth and strictly convex.
Conjectures are made on the minimal rigidity of block-and-hole graphs in the
normed space $\ell_{p}^{3}$, for $p\in[1,\infty]$, $p\not=2$, and on the
global rigidity of discus-and-hole graphs in the Euclidean space
$\mathbb{R}^{3}$. Finally, we indicate connections between the rigidity
properties of block-and-hole graphs and the rigidity properties of polyhedral
surfaces known as origami.

In what follows, we use the definition and notation of block-and-hole graphs
and related terminology, from [3]. Let $S=(V,E)$ be the graph of a
triangulated sphere (i.e. a maximal planar graph). Let $c$ be a simple cycle
in $S$ of length four or more. Then $c$ determines two complementary planar
subgraphs of $S$, each with a single non-triangular face bordered by the edges
of $c$. Such a subgraph $D$ is referred to as a simplicial disc of $S$ with
boundary cycle $\partial D:=c$. A collection of simplicial discs is
internally-disjoint if their respective triangular faces are pairwise
disjoint.

######  Definition 1.1.

A face graph is a simple graph, $G$, which is obtained from the graph of a
triangulated sphere, $S$, by,

  1. (i)

choosing a collection of internally disjoint simplicial discs in $S$,

  2. (ii)

removing the vertices and edges of each of these simplicial discs except for
the vertices and edges which lie in the boundary cycles of the simplicial
discs,

  3. (iii)

labelling the non-triangular faces of the resulting planar graph by either $B$
or $H$.

A $BH$ edge in a face graph $G$ is an edge which lies in the boundary of a
$B$-labelled face and a $H$-labelled face. A $TT$ edge in $G$ is an edge which
lies in the boundary of two triangular faces.

######  Example 1.2.

Figure 1 illustrates the three steps in the construction of a face graph
beginning on the left hand side with a maximal planar graph. Two internally
disjoint simplicial discs are chosen with boundary cycles indicated in red and
blue. Non-boundary vertices and edges of the chosen simplicial discs are
removed (centre) and finally non-triangular faces are labelled by either $B$
or $H$ (right).

$H$$B$ Figure 1. Constructing a face graph.

######  Definition 1.3.

A block-and-hole graph is a simple graph of the form
$\hat{G}=G\cup\hat{B}_{1}\cup\cdots\cup\hat{B}_{m}$ where,

  1. (i)

$G$ is a face graph with $m$ $B$-labelled faces $B_{1},\ldots,B_{m}$,

  2. (ii)

$\hat{B}_{1},\ldots,\hat{B}_{m}$ are minimally $3$-rigid graphs,

  3. (iii)

$G\cap\hat{B}_{i}=\partial B_{i}$, for each $i=1,\ldots,m$.

We refer to the minimally $3$-rigid graphs $\hat{B}_{1},\ldots,\hat{B}_{m}$ as
blocks and the $H$-labelled faces of $G$ as holes.

For each $B$-labelled face $B_{i}$ we can construct a block $B_{i}^{\dagger}$
with,

$V(B_{i}^{\dagger})=V(\partial B_{i})\cup\\{x_{i},y_{i}\\},\quad
E(B_{i}^{\dagger})=E(\partial B_{i})\cup\\{(v,x_{i}),(v,y_{i}):v\in V(\partial
B_{i})\\}.$

The block $B_{i}^{\dagger}$ is referred to as a simplicial discus with poles
at $x_{i}$ and $y_{i}$. The resulting block-and-hole graph $G^{\dagger}:=G\cup
B_{1}^{\dagger}\cup\cdots\cup B_{m}^{\dagger}$ is referred to as the discus-
and-hole graph for $G$.

Let $f(J)$ denote the _freedom number_ $3|V(J)|-|E(J)|$ of a graph $J$. A
simple graph $J$ is said to be $(3,6)$-sparse if $f(J^{\prime})\geq 6$ for any
subgraph $J^{\prime}$ containing at least two edges. The graph $J$ is
$(3,6)$-tight if it is $(3,6)$-sparse and $f(J)=6$. We denote by
$\mathcal{G}(m,n)$ the set of face graphs with $m$ $B$-labelled faces and $n$
$H$-labelled faces for which the discus-and-hole graph $G^{\dagger}$ is
$(3,6)$-tight.

We will make reference to the following theorem which is proved in [3].

######  Theorem 1.4.

Let $\hat{G}$ be a block-and-hole graph with a single block and finitely many
holes, or, a single hole and finitely many blocks. Then the following
statements are equivalent.

  1. (i)

$\hat{G}$ is minimally $3$-rigid.

  2. (ii)

$\hat{G}$ is $(3,6)$-tight.

  3. (iii)

$\hat{G}$ is constructible from $K_{3}$ by vertex splitting and isostatic
substitution.

  4. (iv)

$\hat{G}$ satisfies the girth inequalities.

##  2\. Vertex splitting

Let $J$ be a simple graph and let $v$ be a vertex of $J$ with adjacent
vertices $v_{1},v_{2},\ldots,v_{n}$, $n\geq 2$. Construct a new graph
$\tilde{J}$ from $J$ by,

  1. (i)

removing the vertex $v$ and its incident edges from $J$,

  2. (ii)

adjoining two new vertices $w_{1},w_{2}$,

  3. (iii)

adjoining the edge $w_{1}v_{j}$ or the edge $w_{2}v_{j}$ for each
$j=3,4,\ldots,n$,

  4. (iv)

adjoining the five edges $v_{1}w_{1},v_{2}w_{1}$, $v_{1}w_{2},v_{2}w_{2}$ and
$w_{1}w_{2}$.

The graph $\tilde{J}$ is said to be obtained from $J$ by (3-dimensional)
vertex splitting. See Figure 2 for an illustration.

Figure 2. A vertex splitting operation.

In this section we show that a block-and-hole graph with a single block, or a
single hole, is minimally $3$-rigid if and only if the corresponding discus-
and-hole graph is constructible from $K_{3}$ by vertex splitting. For more on
vertex splitting and rigid graphs see [21] for example.

###  2.1. Critical separating cycles

Let $G$ be a face graph with exactly one $B$-labelled face and any number of
$H$-labelled faces. Fix a planar realisation of $G$ such that the unbounded
face is $B$-labelled. Let $c$ be a simple cycle in $G$. Define $G_{1}$ to be
the face graph obtained from $G$ and $c$ by,

  1. (i)

removing all edges and vertices interior to $c$, and,

  2. (ii)

if $|c|\geq 4$, viewing the edges of $c$ as the boundary of a new face with
label $H$.

Define $G_{2}$ to be the face graph obtained from $G$ and $c$ by,

  1. (i)

removing all edges and vertices which are exterior to $c$, and,

  2. (ii)

if $|c|\geq 4$, viewing the edges of $c$ as the boundary of a new face with
label $B$.

We refer to $G_{1}$ and $G_{2}$ respectively as the external and internal face
graphs associated with $c$. See Figure 3 for an illustration.

$H$$B$$H$$B$$H$$B$ Figure 3. Left: A cycle $c$ (indicated in red) in a face
graph with one $B$-labelled face. Centre: The associated external face graph
$G_{1}$. Right: The associated internal face graph $G_{2}$.

Note that in the case where $|c|=3$, the internal face graph $G_{2}$ has no
$B$-labelled face. We denote by $Ext_{G}(c)$, or simply $Ext(c)$ when the
context is clear, the discus-and-hole graph for the external face graph
$G_{1}$. Note that $Ext(c)$ is a block-and-hole graph with a single block and
so, by Theorem 1.4, $Ext(c)$ is $(3,6)$-tight if and only if it is minimally
$3$-rigid.

######  Definition 2.1.

A critical separating cycle for a face graph $G\in\mathcal{G}(1,n)$ is a
simple cycle $c$ in $G$ with the property that the external discus-and-hole
graph $Ext(c)$ is $(3,6)$-tight.

We will require the following lemma which is adapted from the proof of [3,
Proposition 22].

######  Lemma 2.2.

Let $G\in{\mathcal{G}}(1,n)$ and let $v$ and $w$ be distinct vertices in
$\partial B$ which are not joined by a $BH$ edge in $G$. If $v$ and $w$ lie in
a common $H$-labelled face then $G$ contains a non-facial critical separating
cycle.

###### Proof.

Suppose there exists a $H$-labelled face in $G$ which contains the vertices
$v$ and $w$. The boundary of this $H$-labelled face is composed of two edge-
disjoint paths $\pi_{1}$ and $\pi_{2}$ joining $v$ to $w$. Let $c_{1}$ be the
simple cycle in $\partial B\cup\partial H$ which contains the path $\pi_{1}$
and has the property that $Ext(c_{1})$ does not contain the path $\pi_{2}$.
Similarly, let $c_{2}$ be the simple cycle in $\partial B\cup\partial H$ which
contains the path $\pi_{2}$ and has the property that $Ext(c_{2})$ does not
contain the path $\pi_{1}$. See Figure 4 for an illustration. Note that
$Ext(c_{1})\cap Ext(c_{2})=B^{\dagger}$. Thus,

$f(G^{\dagger})=f(Ext(c_{1}))+f(Ext(c_{2}))-f(B^{\dagger}).$

Since $f(G^{\dagger})=f(B^{\dagger})=6$, it follows that
$f(Ext(c_{1}))=f(Ext(c_{2}))=6$. Hence $Ext(c_{1})$ and $Ext(c_{2})$ are both
$(3,6)$-tight and so $c_{1}$ and $c_{2}$ are non-facial critical separating
cycles for $G$.

∎

$H$$B$$v$$w$$H$$B$$v$$w$ Figure 4. An illustration of the proof of Lemma 2.2.
The edge-disjoint paths $\pi_{1}$ and $\pi_{2}$ are indicated in red and blue
on the left. The cycles $c_{1}$ and $c_{2}$ are indicated in red and blue on
the right.

We will require the following result, known as the “hole-filling” lemma. In
the statement of the lemma, $int(c)$ denotes the subgraph of $G$ spanned by
edges which lie inside the cycle $c$.

######  Lemma 2.3 ([3, Lemma 26]).

Let $G\in{\mathcal{G}}(1,n)$ and let $K^{\prime}$ be a subgraph of
$G^{\dagger}$. Suppose that $c$ is a simple cycle in $K^{\prime}\cap G$ with
$E(K^{\prime}\cap int(c))=\emptyset$. If $K^{\prime}$ is $(3,6)$-tight then
$K^{\prime}\cup int(c)$ is $(3,6)$-tight.

######  Lemma 2.4.

Let $G\in\mathcal{G}(1,n)$. Suppose that $K^{\prime}$ is a $(3,6)$-tight
subgraph of $G^{\dagger}$ with $B^{\dagger}\subset K^{\prime}$ and let
$K=K^{\prime}\cap G$. Label the face of $K$ corresponding to $B^{\dagger}$ by
$B$ and every other non-triangular face by $H$. Then,

  1. (i)

$K$ is a face graph.

  2. (ii)

The boundary cycle of every $H$-labelled face in $K$ is either the boundary of
a $H$-labelled face in $G$ or is a non-facial critical separating cycle in
$G$.

###### Proof.

$(i)$ We need to show that the boundary cycle of each $H$-labelled face of $K$
is simple. If this were not the case then the boundary cycle of some face of
$K$ would contain a repeated vertex. Note that this repeated vertex is a cut
vertex for $K$. It is also a cut vertex for $K^{\prime}$. However,
$K^{\prime}$ does not have a cut vertex since it is $(3,6)$-tight.

$(ii)$ Suppose $c$ is the boundary cycle of a $H$-labelled face in $K$ which
is not a $H$-labelled face in $G$. Let $G_{1}$ be the external face graph
associated with $c$. Note that the external discus-and-hole graph
$G_{1}^{\dagger}$ is obtained from $K^{\prime}$ by “filling in” $H$-labelled
faces of $K$. Since $K^{\prime}$ is $(3,6)$-tight, by the hole-filling lemma
(Lemma 2.3), $G_{1}^{\dagger}$ is also $(3,6)$-tight. Thus, $c$ is a non-
facial critical separating cycle in $G$. ∎

We will require the following result, known as the isostatic substitution
principle. See [19, Corollary 2.8] and the more general form [7, Corollary
2.6].

######  Lemma 2.5.

Let $K$ be a simple graph which is minimally $3$-rigid and let $K^{\prime}$ be
a vertex induced subgraph of $K$ which is also minimally $3$-rigid. If
$K^{\prime}$ is replaced with another minimally $3$-rigid graph
$K^{\prime\prime}$ with the property that $V(K^{\prime})\subseteq
V(K^{\prime\prime})$ then the resulting graph is minimally $3$-rigid.

######  Lemma 2.6.

Let $G\in\mathcal{G}(1,n)$. Suppose $c$ is a non-facial critical separating
cycle for $G$ with internal face graph $G_{2}$. If $d$ is a critical
separating cycle for $G_{2}$ then $d$ is also a critical separating cycle for
$G$.

###### Proof.

By Theorem 1.4, the discus-and-hole graphs $Ext_{G_{2}}(d)$ and $Ext_{G}(c)$
are minimally $3$-rigid. Note that $Ext_{G}(d)$ is obtained by replacing the
discus in $Ext_{G_{2}}(d)$ with $Ext_{G}(c)$. Thus, by the isostatic
substitution principle (Lemma 2.5), since $Ext_{G_{2}}(d)$ is minimally
$3$-rigid, $Ext_{G}(d)$ is also minimally $3$-rigid. We conclude that $d$ is a
critical separating cycle for $G$. ∎

We now present a key technical lemma which is needed for the proof of Theorem
2.15 below.

$f$$e$$d$$c$ Figure 5. Lemma 2.7.

######  Lemma 2.7.

Let $G\in\mathcal{G}(1,n)$ and let $c$ be a critical separating cycle for $G$
of length $|c|\geq 4$, with associated external and internal face graphs
$G_{1}$ and $G_{2}$. Let $e$ be a $TT$ edge in $G_{1}$ and let $f$ be a $TT$
edge in $G_{2}$.

  1. (i)

If $e$ lies in a non-facial critical separating cycle for $G$ then $e$ also
lies in a non-facial critical separating cycle for $G_{1}$.

  2. (ii)

If $f$ lies in a non-facial critical separating cycle for $G$ then $f$ also
lies in a non-facial critical separating cycle for $G_{2}$.

###### Proof.

$(i)$ Suppose $d$ is a non-facial critical separating cycle for $G$ which
contains the edge $e$ (see Figure 5 for an illustration). Let
$K^{\prime}=Ext(c)\cap Ext(d)$ and let $K=K^{\prime}\cap G$. Similarly, let
$L^{\prime}=Ext(c)\cup Ext(d)$ and let $L=L^{\prime}\cap G$. Observe that,

$f(K^{\prime})+f(L^{\prime})=f(Ext(c))+f(Ext(d))=12.$

Therefore $f(K^{\prime})=f(L^{\prime})=6$ and so $K^{\prime}$ and $L^{\prime}$
are $(3,6)$-tight subgraphs of $G^{\dagger}$ which contain $B^{\dagger}$.
Label the face of $K$ corresponding to $B^{\dagger}$ by $B$ and every other
non-triangular face of $K$ by $H$. Note that, since $|c|\geq 4$, $e$ lies on
the boundary cycle of a $H$-labelled face of $K$ by construction. Let
$d^{\prime}$ be this boundary cycle. Since $e$ is a $TT$ edge in $G_{1}$,
$d^{\prime}$ cannot be the boundary of a face in $G_{1}$. Therefore, by Lemma
2.4, $d^{\prime}$ is a non-facial critical separating cycle for $G_{1}$. This
proves part $(i)$. Part $(ii)$ is proved by applying similar arguments to $L$.
∎

###  2.2. On indivisible graphs in $\mathcal{G}(1,n)$

In this section, we derive properties of face graphs in $\mathcal{G}(1,n)$
which contain no $TT$ edges and no non-facial critical separating cycles.

######  Definition 2.8.

A face graph $G$ in ${\mathcal{G}}(1,n)$ is _indivisible_ if every critical
separating cycle for $G$ is the boundary cycle of a face of $G$.

######  Lemma 2.9.

Suppose that $G\in\mathcal{G}(1,n)$ has no $TT$ edge and is also indivisible.
Then $G$ has at least three $BH$ edges.

###### Proof.

By [3, Proposition 22(ii)], $G$ must contain at least one $BH$ edge. The cases
where $G$ contains exactly one $BH$ edge and exactly two $BH$ edges are
considered below. Since there are no $TT$ edges in $G$, for each vertex $v$ of
$\partial B$ there exists a $H$-labelled face $H_{v}\in{\mathcal{H}}$ which
contains $v$. The set of all $H$-labelled faces of $G$ is denoted by
${\mathcal{H}}$. Since $f(G^{\dagger})=6$ it follows that $|\partial
B|-3=\sum_{H\in{\mathcal{H}}}(|\partial H|-3)$.

Case 1: Suppose $G$ contains exactly one $BH$ edge $e$. Then the vertices of
$e$ are contained in a common $H$-labelled face $H_{e}$. If the remaining
$r=|\partial B|-2$ vertices $v_{1},v_{2},\ldots,v_{r}$ in $\partial B$ are
each contained in distinct $H$-labelled faces then we obtain the
contradiction,

$|\partial B|-3=\sum_{H\in{\mathcal{H}}}(|\partial H|-3)\geq(|\partial
H_{e}|-3)+\sum_{i=1}^{r}(|\partial H_{v_{i}}|-3)\geq r+1.$

Case 2: Suppose $G$ contains exactly two $BH$ edges $e$ and $f$ and that these
edges are adjacent. The vertices of $e$ are contained in a common $H$-labelled
face $H_{e}$. If the remaining $r=|\partial B|-3$ vertices
$v_{1},v_{2},\ldots,v_{r}$ in $\partial B$ are each contained in distinct
$H$-labelled faces then we obtain the contradiction,

$|\partial B|-3=\sum_{H\in{\mathcal{H}}}(|\partial H|-3)\geq(|\partial
H_{e}|-3)+\sum_{i=1}^{r}(|\partial H_{v_{i}}|-3)\geq r+1.$

Case 3: Suppose $G$ contains exactly two $BH$ edges $e$ and $f$ and that these
edges are not adjacent. The vertices of $e$ are contained in a common
$H$-labelled face $H_{e}$ and the vertices of $f$ are contained in a common
$H$-labelled face $H_{f}$. If $H_{e}$ and $H_{f}$ are distinct, and, if the
remaining $r=|\partial B|-4$ vertices $v_{1},v_{2},\ldots,v_{r}$ in $\partial
B$ are each contained in distinct $H$-labelled faces then we obtain the
contradiction,

$|\partial B|-3=\sum_{H\in{\mathcal{H}}}(|\partial H|-3)\geq(|\partial
H_{e}|-3)+(|\partial H_{f}|-3)+\sum_{i=1}^{r}(|\partial H_{v_{i}}|-3)\geq
r+2.$

The contradictions obtained in each of the above cases imply that there must
exist a pair of vertices $v$ and $w$ in $\partial B$ which are not joined by a
$BH$-edge and for which $H_{v}=H_{w}$. By Lemma 2.2, there must exist a non-
facial critical separating cycle in $G$. However, this contradicts the
indivisibility of $G$ and so $G$ must contain at least three $BH$ edges.

∎

######  Lemma 2.10.

Suppose that $G\in\mathcal{G}(1,n)$ has no $TT$ edges, is indivisible and has
exactly three $BH$ edges. Then

  1. (i)

Every $H$-labelled face in $G$ is a quadrilateral.

  2. (ii)

The three $BH$ edges are not consecutive edges in $\partial B$.

###### Proof.

Consider the following three cases.

Case 1: Suppose $G$ contains exactly three $BH$ edges $e,f,g$ and no two are
adjacent. Then the vertices of $e,f,g$ are respectively contained in common
$H$-labelled faces $H_{e}$, $H_{f}$ and $H_{g}$. Since $G$ is indivisible, the
faces $H_{e}$, $H_{f}$ and $H_{g}$ are distinct and the remaining $r=|\partial
B|-6$ vertices $v_{1},v_{2},\ldots,v_{r}$ in $\partial B$ are each contained
in a distinct $H$-labelled face. Thus,

$\displaystyle|\partial B|-3$ $\displaystyle=$
$\displaystyle\sum_{H\in{\mathcal{H}}}(|\partial H|-3)$ $\displaystyle\geq$
$\displaystyle(|\partial H_{e}|-3)+(|\partial H_{f}|-3)+(|\partial
H_{g}|-3)+\sum_{i=1}^{r}(|\partial H_{v_{i}}|-3)$ $\displaystyle\geq$
$\displaystyle r+3$

The above inequalities imply that $H_{e}$, $H_{f}$, $H_{g}$ and
$H_{v_{1}},\ldots,H_{v_{r}}$ are the only $H$-labelled faces of $G$ and each
of these faces has boundary length four.

Case 2: Suppose $G$ contains exactly three $BH$ edges $e,f,g$ and exactly two
of these edges, $e$ and $f$ say, are adjacent. The vertices of $e$ and $g$ are
respectively contained in common $H$-labelled faces $H_{e}$ and $H_{g}$. Since
$G$ is indivisible, the faces $H_{e}$ and $H_{g}$ are distinct and the
remaining $r=|\partial B|-5$ vertices $v_{1},v_{2},\ldots,v_{r}$ in $\partial
B$ are each contained in distinct $H$-labelled faces. Thus,

$\displaystyle|\partial B|-3$ $\displaystyle=$
$\displaystyle\sum_{H\in{\mathcal{H}}}(|\partial H|-3)$ $\displaystyle\geq$
$\displaystyle(|\partial H_{e}|-3)+(|\partial
H_{g}|-3)+\sum_{i=1}^{r}(|\partial H_{v_{i}}|-3)$ $\displaystyle\geq$
$\displaystyle r+2$

The above inequalities imply that $H_{e}$, $H_{g}$ and
$H_{v_{1}},\ldots,H_{v_{r}}$ are the only $H$-labelled faces of $G$ and each
of these faces has boundary length four.

Case 3: Suppose $G$ contains exactly three $BH$ edges $e,f,g$ and these three
edges are consecutive. The vertices of $e$ are contained in a common
$H$-labelled face $H_{e}$. Since $G$ is indivisible, it follows from Lemma 2.2
that the remaining $r=|\partial B|-4$ vertices $v_{1},v_{2},\ldots,v_{r}$ in
$\partial B$ are each contained in distinct $H$-labelled faces. Thus,

$\displaystyle|\partial B|-3$ $\displaystyle=$
$\displaystyle\sum_{H\in{\mathcal{H}}}(|\partial H|-3)$ $\displaystyle\geq$
$\displaystyle(|\partial H_{e}|-3)+\sum_{i=1}^{r}(|\partial H_{v_{i}}|-3)$
$\displaystyle\geq$ $\displaystyle r+1$

The above inequalities imply that $H_{e}$ and $H_{v_{1}},\ldots,H_{v_{r}}$ are
the only $H$-labelled faces of $G$ and each of these faces has boundary length
four. However, the boundary of $H_{e}$ consists of three consecutive edges of
$\partial B$ and a fourth edge that is not in $B^{\dagger}$ but is incident to
two vertices of $B^{\dagger}$. This contradicts the $(3,6)$-tightness of
$G^{\dagger}$ and so the three $BH$-edges of $G$ must not be consecutive. ∎

See Figure 6 for examples of face graphs with no $TT$ edges and exactly three
$BH$ edges.

$H$$H$$H$$B$$H$$H$$H$$H$$B$$H$$H$$H$$H$$H$$B$ Figure 6. Face graphs with no
$TT$ edges and exactly three $BH$ edges. The face graph on the left lies in
$\mathcal{G}(1,3)$ and is indivisible. The face graphs in the middle and on
the right lie in $\mathcal{G}(1,4)$ and $\mathcal{G}(1,5)$ respectively and
contain non-facial critical separating cycles (indicated in blue).

###  2.3. On the sufficiency of vertex splitting

Let $G\in\mathcal{G}(1,n)$. A $TT$ edge is contractible in $G$ if it does not
belong to any non-facial $3$-cycle in $G$. A $TT$ edge contraction on $G$ is
an operation on the class of face graphs whereby the vertices of a
contractible $TT$ edge in $G$ are identified, the resulting loop and parallel
edges are discarded, and the labellings of all non-triangular faces in the
resulting planar graph are inherited from $G$. Note that a $TT$ edge
contraction fails to preserve $(3,6)$-tightness if and only if the
contractible $TT$ edge lies on a non-facial critical separating cycle of $G$
(see [3, Lemma 27]). For this reason we restrict attention to $TT$ edge
contractions on $G$ which are admissible in the sense that the contractible
$TT$ edge does not belong to a non-facial critical separating cycle of $G$.

######  Definition 2.11.

A face graph $G\in\mathcal{G}(1,n)$ is terminal if there exist no admissible
$TT$ edge contractions on $G$.

######  Lemma 2.12.

Let $G\in\mathcal{G}(1,n)$. If $G$ is terminal then $G$ contains no non-facial
$3$-cycles.

###### Proof.

Suppose $c$ is a non-facial $3$-cycle in $G$. Note that $f(c)=6$. Since
$G^{\dagger}=Ext(c)\cup G_{2}$ and $c=Ext(c)\cap G_{2}$ we have,

$f(G_{2})=f(Ext(c))+f(G_{2})-f(c)=f(G^{\dagger})=6.$

Recall that in general planar graphs satisfy $f(K)\geq 6$ and so $G_{2}$ is a
maximal planar graph. Since $c$ is a non-facial $3$-cycle in $G$ it follows
that there exists a contractible $TT$ edge $f$ in $G_{2}$ that does not lie in
$c$ (see for example [1, Lemma 1]). Note that the graph $G_{2}/f$ obtained on
contracting this $TT$ edge is again a maximal planar graph. Consider the face
graph $G/f$ obtained from $G$ by applying a $TT$ edge contraction to $f$. Note
that the discus-and-hole graph $(G/f)^{\dagger}$ is obtained from
$G^{\dagger}$ by replacing $G_{2}$ with $G_{2}/f$. Also note that,
$G^{\dagger}$, $G_{2}$ and $G_{2}/f$ are minimally $3$-rigid. Thus, by the
isostatic substitution principle (Lemma 2.5), $(G/f)^{\dagger}$ is minimally
$3$-rigid. In particular, $(G/f)^{\dagger}$ is $(3,6)$-tight. Since the $TT$
edge contraction of $f$ preserves $(3,6)$-tightness it is an admissible $TT$
edge contraction on $G$. This contradicts the terminality of $G$. ∎

A $BH$ edge in the face graph $G$ is contractible if it does not belong to any
$3$-cycle in $G$. A $BH$ edge contraction on $G$ is an operation on the class
of face graphs whereby the vertices of a contractible $BH$ edge in $G$ are
identified, the resulting loop is discarded, and the labellings of all non-
triangular faces are inherited from $G$. Note that $BH$ edge contractions
preserve $(3,6)$-tightness (see [3, Lemma 29]). Also note that under a $BH$
edge contraction it is possible for the $B$-labelled face and the $H$-labelled
face containing the contractible $BH$ edge to be transformed into triangular
faces.

######  Definition 2.13.

A face graph is $BH$-reduced if it contains no contractible $BH$ edges.

We will require the following result.

######  Lemma 2.14.

[3, Corollary 33] For each $n\geq 1$, there is no face graph in
${\mathcal{G}}(1,n)$ which is terminal, indivisible and $BH$-reduced.

Note that the reversal of a $TT$ edge contraction or a $BH$ edge contraction
is a vertex splitting operation. We can now strengthen the statement of
Theorem 1.4 as follows.

######  Theorem 2.15.

Let $\hat{G}$ be a block-and-hole graph with a single block and finitely many
holes, or, a single hole and finitely many blocks. The following statements
are equivalent.

  1. (i)

$\hat{G}$ is minimally $3$-rigid.

  2. (ii)

$G^{\dagger}$ is constructible from $K_{3}$ by vertex splitting.

###### Proof.

Throughout this proof we will use the word “constructible” as a shorthand for
“constructible from $K_{3}$ by vertex splitting only”. In light of Theorem 1.4
it suffices to show that if the discus-and-hole graph $G^{\dagger}$ with a
single discus and finitely many holes is $(3,6)$-tight then it is
constructible. We prove this by induction on the number of edges in
$G^{\dagger}$. Thus let $G\in\mathcal{G}(1,n)$ and assume that the theorem is
true for all discus-and-hole graphs with strictly fewer edges than
$G^{\dagger}$. If $G$ has a contractible $BH$ edge then by [3, Lemma 29] we
can apply a $BH$ edge contraction to obtain a face graph $G^{\prime}$ that
lies in $\mathcal{G}(1,n)$, $\mathcal{G}(1,n-1)$ or in $\mathcal{G}(0,0)$. In
any case, the resulting discus-and-hole graph $(G^{\prime})^{\dagger}$ has
fewer edges than $G^{\dagger}$ and is hence constructible. Note that
$G^{\dagger}$ can be obtained from $(G^{\prime})^{\dagger}$ by applying a
vertex splitting operation and so $G^{\dagger}$ is also constructible.
Similarly, if $G$ has a contractible $TT$ edge that does not lie in any non-
facial critical separating cycle then we may apply an admissible $TT$ edge
contraction to obtain a face graph $G^{\prime}$ which lies in
$\mathcal{G}(1,n)$. Again, the resulting discus-and-hole graph
$(G^{\prime})^{\dagger}$ has fewer edges than $G^{\dagger}$ and is hence
constructible. Since $G^{\dagger}$ can be obtained from
$(G^{\prime})^{\dagger}$ by vertex splitting we conclude that $G^{\dagger}$ is
constructible also.

Now suppose $G$ is both $BH$-reduced and terminal. By Lemma 2.12, $G$ contains
no non-facial $3$-cycles. Thus, by 2.14, $G$ must contain a non-facial
critical separating cycle $c$ with $|c|\geq 4$. Let $G_{1}$ and $G_{2}$ be the
external and internal face graphs associated with $c$. We can choose $c$ so
that there is no non-facial critical separating cycle for $G$ in $G_{2}$ apart
from $c$ itself. By Lemma 2.6, any critical separating cycle for the internal
face graph $G_{2}$ is also a critical separating cycle for $G$. Thus, our
choice of $c$ ensures that the face graph $G_{2}$ is indivisible.

If $G_{2}$ contains a $TT$ edge $e$, then $e$ does not lie on any non-facial
critical separating cycle of $G_{2}$. Since $|c|\geq 4$, $e\not\in c$ and so
$e$ is also a $TT$ edge in $G$. By Lemma 2.7, we conclude that $e$ does not
lie on any non-facial critical separating cycle for $G$ either. Thus the
contraction of $e$ is an admissible $TT$ edge contraction for $G$. This
contradicts the terminality of $G$ and so, from now on, we may assume that
$G_{2}$ has no $TT$ edges.

Suppose $G_{1}$ has a contractible $TT$ edge $e$ that does not lie on any non-
facial critical separating cycle of $G_{1}$. Since $|c|\geq 4$, $e$ is also a
$TT$ edge in $G$. By Lemma 2.7, $e$ does not lie on any non-facial critical
separating cycle of $G$. Again, the contraction of $e$ is an admissible $TT$
edge contraction for $G$ and this contradicts the assumption that $G$ is
terminal. Thus, we may assume that $G_{1}$ is terminal.

Since $Ext(c)$ has fewer edges than $G^{\dagger}$, it is constructible. Thus
$G_{1}$ must have at least one contractible $BH$ edge. Since $G$ is
$BH$-reduced and contains no non-facial $3$-cycles, we conclude that $G$
contains no $BH$ edges. Thus every contractible $BH$ edge of $G_{1}$ must in
fact also be an edge of $c$ (otherwise it would be a $BH$ edge in $G$).

######  Claim 2.16.

There are at least four edges of $c$ that are not in the boundary of the
$B$-labelled face in $G$.

###### Proof of Claim..

Using the isostatic substitution principle (Lemma 2.5), observe that
$G_{2}^{\dagger}$ is $(3,6)$-tight since it is obtained from $G^{\dagger}$ by
replacing $Ext(c)$ with a discus. Since $G_{2}$ is indivisible and has no $TT$
edges we can apply Lemma 2.9 to conclude that $G_{2}$ has at least three $BH$
edges. None of these edges are contained in the boundary of the $B$-labelled
face in $G$ since $G$ contains no $BH$ edges. Thus, we have demonstrated the
existence of three of the required four edges. To get the fourth edge we use
Lemma 2.10. This says that in the case where $G_{2}$ has exactly three $BH$
edges, these three edges are not consecutive around the boundary of the
$B$-labelled face of $G_{2}$. Label these three edges $e_{1}$, $e_{2}$ and
$e_{3}$. Now suppose that all other edges of $c$ also belong to the boundary
of the the $B$-labelled face in $G$. Since $e_{1}$, $e_{2}$ and $e_{3}$ are
not consecutive in the cycle $c$, at least one of these edges, say $e_{1}$
after relabelling if necessary, is not adjacent to either of the other two.
Then the vertices of $e_{1}$ must lie in the boundary of the $B$-labelled face
in $G$. It follows that $e_{1}$ is an edge of $G^{\dagger}$ that is not in the
discus $B^{\dagger}$ but is incident with two vertices in $B^{\dagger}$. This
contradicts the $(3,6)$-tightness of $G^{\dagger}$. ∎

Now let $K$ be the face graph obtained by applying $BH$ edge contractions to
$G_{1}$ until no further $BH$ edge contractions are possible (recalling that
all of these $BH$ edges lie in $c$). By Claim 2.16 there are at least four
edges remaining in the cycle corresponding to $c$. So this cycle still bounds
a hole in $K$. Thus every $TT$ edge of $K$ is also a $TT$ edge of $G_{1}$.
Moreover it is clear that there is an obvious correspondence between the non-
facial critical separating cycles of $K$ and those of $G_{1}$, and, that if a
$TT$ edge of $K$ lies on a non-facial critical separating cycle in $K$ then it
does so in $G_{1}$. By induction $K^{\dagger}$ is constructible and so $K$
must have a contractible $TT$ edge that does not lie on a non-facial critical
separating cycle (it has no contractible $BH$ edges by construction). But this
contradicts the assumption that $G_{1}$ has no such edges.

We conclude that $G$ cannot be both $BH$-reduced and terminal. This completes
the proof. ∎

##  3\. $(3,0)$-sparsity and pebble games

The main result of [3] characterises minimal $3$-rigidity for block-and-hole
graphs with a single block in terms of $(3,6)$-sparsity. The aim of this
section is to show that $(3,6)$-sparsity is equivalent to an a priori weaker
sparsity condition on two related multigraphs. The advantage of these
characterisations is that they can be quickly checked via a pebble game
algorithm in the sense of [14], whereas the $(3,6)$-sparsity condition lies
outside the “matroidal” range and cannot be so easily checked.

Let $G$ be a face graph with a single $B$-labelled face. We denote by
$G^{2\sigma}$ the multigraph constructed from the face graph $G$ by adjoining
two self-loops to each vertex $v\in V(\partial B)$. Let $G^{-}=G\setminus
E(\partial B)$ be the graph obtained by removing the edges in the boundary
cycle $\partial B$ from $G$. We denote by $(G^{-})^{3\sigma}$ the graph
obtained from $G^{-}$ by adding three self-loops to each of the vertices of
$\partial B$. We refer to $G^{2\sigma}$ and $(G^{-})^{3\sigma}$ as looped face
graphs.

A multigraph $J$ is said to be $(3,0)$-sparse if $f(J^{\prime})\geq 0$ for any
subgraph $J^{\prime}$. A multigraph $J$ is $(3,0)$-tight if it is
$(3,0)$-sparse and $f(J)=0$. For more on $(k,l)$-sparsity generally see [14].
We will require the following lemma.

######  Lemma 3.1.

A multigraph is $(3,0)$-tight if and only if there exists an outdegree 3
orientation of the edges of the multigraph.

###### Proof.

Apply [14, Theorem 8 and Lemma 10]. ∎

$H$$H$$H$$B$ Figure 7. A face graph $G$ (left) and its associated looped face
graphs $G^{2\sigma}$ (centre) and $(G^{-})^{3\sigma}$ (right) together with
out degree $3$ edge orientations.

######  Example 3.2.

Let $\hat{G}$ be a block-and hole graph on the face graph $G$ illustrated in
Figure 7. The associated looped face graphs admit out degree $3$ edge
orientations. Thus, by Lemma 3.1, these multigraphs are $(3,0)$-tight. By
Theorem 3.3 below, the block and hole graph $\hat{G}$ is $(3,6)$-tight and so,
by Theorem 1.4, $\hat{G}$ is minimally $3$-rigid.

We now prove the main result of this section.

######  Theorem 3.3.

Let $\hat{G}$ be a block-and-hole graph with a single block and finitely many
holes. Then the following statements are equivalent.

  1. (i)

$\hat{G}$ is minimally $3$-rigid.

  2. (ii)

$G^{2\sigma}$ is $(3,0)$-tight.

  3. (iii)

$(G^{-})^{3\sigma}$ is $(3,0)$-tight.

###### Proof.

$(i)\Rightarrow(ii)$ Suppose $\hat{G}$ is minimally $3$-rigid. Let $K$ be a
subgraph of $G^{2\sigma}$ and let $K^{\prime}=K\cap G$ be the subgraph of $G$
obtained by removing all self-loops from $K$. Note that
$K^{\prime}\cap\hat{B}$ is a subgraph of the boundary cycle $\partial B$ and
so $|E(K^{\prime}\cap\hat{B})|\leq|V(K^{\prime}\cap\hat{B})|$. It follows that
$f(K^{\prime}\cap\hat{B})\geq 2|V(K^{\prime}\cap\partial B)|$. Note that

$f(K^{\prime}\cup\hat{B})=f(K^{\prime})+f(\hat{B})-f(K^{\prime}\cap\hat{B})\leq
f(K^{\prime})+6-2|V(K^{\prime}\cap\partial B)|\leq f(K)+6.$

Since $K^{\prime}\cup\hat{B}$ is a subgraph of $\hat{G}$, it is
$(3,6)$-sparse, and so $f(K)\geq 0$. We conclude that $G^{2\sigma}$ is
$(3,0)$-sparse. Note that $f(\partial B)=2|V(\partial B)|$ and so,

$f(\hat{G})=f(\hat{B})+f(G)-f(\partial B)=6+f(G)-2|V(\partial
B)|=6+f(G^{2\sigma}).$

Thus $f(G^{2\sigma})=f(\hat{G})-6=0$ and so $G^{2\sigma}$ is $(3,0)$-tight.

$(ii)\Leftrightarrow(iii)$ Note that on $V(\partial B)$, any outdegree $3$
orientation of the edges of $(G^{-})^{3\sigma}$ or $G^{2\sigma}$ has a very
constrained form. For any vertex $v$ of $V(\partial B)\subset
V((G^{-})^{3\sigma})$, the three self-loops on it must be oriented away from
$v$, and similarly for the two self-loops on the vertices of $\partial
B\subset G^{2\sigma}$. Then there is one remaining outgoing edge from each
$v\in V(\partial B)\subset V(G^{2\sigma})$ which must be one of the two edges
of $\partial B$ that meet it. It follows that $\partial B\subset G^{2\sigma}$
must be oriented according to one of its two cyclic orientations. Thus any
outdegree 3 orientation of $(G^{-})^{3\sigma}$ is easily converted to one of
$G^{2\sigma}$ and vice versa. The result now follows from Lemma 3.1.

$(iii)\Rightarrow(i)$ Suppose the multigraph $(G^{-})^{3\sigma}$ is
$(3,0)$-tight. Let $K$ be a subgraph of $\hat{G}$ containing at least two
edges. If $K$ is a subgraph of $G$ then, since $G$ is a subgraph of a
triangulated sphere, $K$ is $(3,6)$-sparse. If $K$ is not a subgraph of $G$
then we consider three possible cases:

Case 1: Suppose $K\cap\hat{B}$ contains at least two edges. Consider the
subgraph $(K\cap G^{-})^{3\sigma}$ of the multigraph $(G^{-})^{3\sigma}$. Note
that,

$0\leq f((K\cap G^{-})^{3\sigma})=f(K\cap G)-f(K\cap\partial B).$

Since $\hat{B}$ is $(3,6)$-sparse, we have $f(K\cap\hat{B})\geq 6$ and so,

$f(K)=f(K\cap\hat{B})+f(K\cap G)-f(K\cap\partial B)\geq 6.$

Case 2: Suppose $K\cap\hat{B}$ contains no edges, or contains exactly one edge
which lies in $\partial B$. Then $K$ must be the disjoint union of $K\cap G$
(which, as a subgraph of a triangulated sphere, is $(3,6)$-sparse) and some
number of vertices in $\hat{B}$. Hence $f(K)\geq f(K\cap G)\geq 6$.

Case 3: Suppose $K\cap\hat{B}$ contains exactly one edge and that this edge
does not lie in $\partial B$. Then $K$ must consist of $K\cap G$ with an
additional edge (which is still a subgraph of a triangulated sphere) together
with some number of vertices in $\hat{B}$. Hence $f(K)\geq 6$.

We conclude that $\hat{G}$ is $(3,6)$-sparse. Also,

$f(\hat{G})=f(\hat{B})+f(G)-f(\partial B)=6+f(G)-2|V(\partial
B)|=6+f((G^{-})^{3\sigma}).$

Thus $f(\hat{G})=6$ and so $\hat{G}$ is $(3,6)$-tight. By Theorem 1.4,
$\hat{G}$ is minimally $3$-rigid. ∎

##  4\. Applications and Conjectures

###  4.1. Rigidity in $\ell_{p}^{3}$

The vertex splitting operation considered in Section 2 is known to preserve
rigidity properties in geometric settings other than the Euclidean space
$\mathbb{R}^{3}$. For example, it is known that vertex splitting preserves
independence in every $3$-dimensional real normed linear space which is both
smooth and strictly convex (see [6, Proposition 4.7]). It follows that any
class of graphs which are constructible from an independent base graph by
vertex splitting (for example, triangulations of a 2-sphere) will satisfy
independence. Thus, with the main theorem of Section 2 in hand, we obtain the
following immediate corollary.

######  Corollary 4.1.

Let $X$ be a $3$-dimensional real normed linear space which is smooth and
strictly convex. Then every $(3,6)$-tight discus-and-hole graph, with a single
discus, is independent in $X$.

###### Proof.

By [6, Proposition 4.7], vertex splitting preserves independence in $X$. The
graph $K_{3}$ is independent in $X$. Thus the result follows from Theorem
2.15. ∎

In the case of $\ell_{p}^{3}$, where $p\in[1,\infty]$ and $p\not=2$, the
minimally rigid graphs are $(3,3)$-tight. Here a simple graph $J$ is
$(3,3)$-tight if $f(J)=6$ and $f(J^{\prime})\geq 3$ for any subgraph
$J^{\prime}$. The smallest (non-trivial) graph with this property is the
complete graph $K_{6}$. It is conjectured that every $(3,3)$-tight simple
graph is minimally rigid in $\ell_{p}^{3}$ (see for example [6]). We propose
here a special case of this conjecture.

######  Conjecture 4.2.

Let $p\in[1,\infty]$, $p\not=2$. Let $\hat{G}$ be a block-and-hole graph with
a single block. If the block is minimally rigid in $\ell_{p}^{3}$ then the
following statements are equivalent.

  1. (i)

$\hat{G}$ is minimally rigid in $\ell_{p}^{3}$.

  2. (ii)

$\hat{G}$ is $(3,3)$-tight.

###  4.2. Conjecture on global rigidity

Establishing global rigidity is typically a more difficult problem than
establishing rigidity for a given class of graphs. One of the reasons is that
vertex splitting is less well understood in this context. Connelly and
Whiteley have conjectured a necessary and sufficient condition for vertex
splitting to preserve global rigidity in $\mathbb{R}^{d}$ [2]. This conjecture
is still open but has been verified in certain special cases (see [12, 4, 5])
leading to global rigidity characterisations for braced plane triangulations
and for triangulations of non-spherical surfaces. Given Theorem 2.15, it is
natural to wonder if similar global rigidity characterisations might be
obtained for discus-and-hole graphs.

######  Conjecture 4.3.

Suppose that $G^{\dagger}$ is a discus-and-hole graph with exactly one discus.
Then $G^{\dagger}$ is generically globally rigid in $\mathbb{R}^{3}$ if and
only if $G^{\dagger}$ is $4$-connected and redundantly rigid in
$\mathbb{R}^{3}$.

Note that the “only if” implication in Conjecture 4.3 is already well known
(see [10]).

###  4.3. Connection to rigid origami

Rigid origami is the study of structures made out of flat rigid sheets joined
at hinges. Such structures have inspired work in structural engineering,
mechanical design and the physics of mechanical metamaterials [8, 15, 16, 18].
It is of practical interest, given such a structure, to determine its
mechanical properties, and as a very first step, one would like to know
whether it is floppy or rigid. It is natural, given the constraint that the
sheets remain rigidly flat, to mathematically model rigid origami by
polyhedral surfaces (with boundary).

The connection to the block-and-hole graphs considered in this article is then
as follows. Given a polyhedral surface, we wish to replace it by a bar-joint
framework such that all vertices and edges of the polyhedral surface become
joints and bars, respectively. In order for the framework to have the same
rigidity properties we must add additional bars and joints to the non-
triangular faces, as they could otherwise bend and flex in the framework. By
the isostatic substitution principle (Lemma 2.5), this can be done without
introducing dependencies in the bars by adding any minimally 3-rigid graph on
the vertices of the planar face.

For example, the following two part construction works: first, triangulate
each of the non-triangular faces and second, for each non-triangular face,
create a new joint off the plane of the face with bars to each of the vertices
of that face. Note that this replaces the rigid face with a triangulated
prism.

One can then naturally identify these with “blocks” and the missing faces as
“holes”. One important caveat is that the realizations of block-and-hole
graphs arising from the above construction are not generic – the blocks are
bounded by sets of coplanar vertices. It is natural of course to conjecture
(along the lines of the molecular conjecture of Tay and Whiteley [17] proved
by Katoh and Tanigawa [13]) that the rigidity of generic polyhedral surfaces
can indeed be predicted by the rigidity of structures where the blocks are
made more generic, but this remains to be proven.

One further point is that the definition of rigid origami above allows
vertices to have discrete Gaussian curvature (i.e. the angles of the faces
around them may not sum to $2\pi$). Such a structure could not be folded from
an ordinary sheet of paper. It would be interesting to consider the
“developable” rigid origami case (where all angle-sums around vertices are
$2\pi$), and this would require the consideration of further non-genericities.
It may be that block-and-hole graphs provide the appropriate counts for
“generic developable rigid origami” as well.

Assuming a suitable “molecular origami conjecture” holds, Theorem 1.4 and
Theorem 3.3 give a way of determining the rigidity or flexibility of rigid
origami with either (1) one non-triangular face and an arbitrary number of
non-triangular holes or (2) one non-triangular hole and an arbitrary number of
non-triangular faces (related by block-and-hole swapping). Note that “pure”
origami folded from a single-sheet without allowing any cutting leads at the
combinatorial level to block-and-hole graphs which satisfy (2), with the
exterior of the paper viewed as a large hole.

##  5\. Acknowledgement

This article is based on work initiated by the authors during the BIRS
workshop on Advances in Combinatorial and Geometric Rigidity (15w5114).

## References

  * [1] D. Barnette, Generating the triangulations of the projective plane, J. Combin. Theory Ser. B, 33(3):222–230, 1982.
  * [2] Connelly, R., Whiteley, W.J. Global Rigidity: The Effect of Coning. Discrete Comput Geom 43, pp. 717–735, 2010. https://doi.org/10.1007/s00454-009-9220-0
  * [3] J. Cruickshank, D. Kitson, S. C. Power, The generic rigidity of triangulated spheres with blocks and holes. J. Combin. Theory Ser. B 122 (2017), 550–577.
  * [4] J. Cruickshank, B. Jackson and S. Tanigawa. Vertex Splitting, Coincident Realisations, and Global Rigidity of Braced Triangulations. Discrete Comput Geom 69, 192–208 (2023). https://doi.org/10.1007/s00454-022-00459-9
  * [5] J. Cruickshank, B. Jackson and S. Tanigawa. Global Rigidity of Triangulated Manifolds, 2022 https://arxiv.org/abs/2204.02503
  * [6] S. Dewar, D. Kitson, A. Nixon, Which graphs are rigid in $\ell_{p}^{d}$? J. Glob. Optim. 83, 49–71 (2022).
  * [7] W. Finbow, E. Ross, W. Whiteley, The rigidity of spherical frameworks: swapping blocks and holes. SIAM J. Discrete Math. 26 (2012), no.1, 280–304.
  * [8] E. T. Filipov, G. H. Paulino, and T. Tachi, Origami tubes with reconfigurable polygonal cross-sections, Proceedings of the Royal Society A, 472:1–23, 2016.
  * [9] H. Gluck, Almost all simply connected closed surfaces are rigid, in Geometric Topology, Lecture Notes in Math., no. 438, Springer-Verlag, Berlin, 1975, pp. 225–239.
  * [10] B. Hendrickson, Conditions for Unique Graph Realizations, SIAM Journal on Computing, vol. 21, Iss. 1, pp 65–84, 1992\.
  * [11] T. Jordán, Rigid block and hole graphs with a single block, Discrete Mathematics, 346(3) (2023), 113268.
  * [12] T. Jordán, S. Tanigawa, Global rigidity of triangulations with braces, Journal of Combinatorial Theory, Series B, Volume 136, 2019, pp 249-288, ISSN 0095-8956, https://doi.org/10.1016/j.jctb.2018.11.003.
  * [13] N. Katoh and S. Tanigawa, A Proof of the Molecular Conjecture, Discrete Comput. Geom., 45:617–700, 2011.
  * [14] A. Lee and I. Streinu, Pebble game algorithms and sparse graphs, Discrete Mathematics, 308(8):1425–1437, 2008.
  * [15] M. Schenk and S. D. Guest, Geometry of Miura-folded metamaterials, Proceedings of the National Academy of Sciences, 110(9):3276–3281, 2013.
  * [16] J. L. Silverberg, A. A. Evans, Lauren McLeod, Ryan C. Hayward, Thomas Hull, Christian D. Santangelo and Itai Cohen, Using origami design principles to fold reprogrammable mechanical metamaterials, Science 345(6197):647–650, 2014.
  * [17] T. S. Tay and W. Whiteley, Recent advances in the generic rigidity of structures. Strut. Topol. 9, 31–38, 1984.
  * [18] Z. Y. Wei, Z. V. Guo, L. Dudte, H. Y. Liang and L. Mahadevan, Geometric Mechanics of Periodic Pleated Origami, Phys. Rev. Lett. 110(21):215501, 2013.
  * [19] W. Whiteley, Infinitesimally Rigid Polyhedra. I. Statics of Frameworks, Transactions of the American Mathematical Society, 285(2):431–465, 1984.
  * [20] W. Whiteley, Infinitesimally rigid polyhedra. II: Modified spherical frameworks, Trans. Amer. Math. Soc., 306 (1988), 115–139.
  * [21] W. Whiteley, Vertex splitting in isostatic frameworks, Structural Topology, 16 (1990), 23–30.