∎

11institutetext: Christian Millichap 22institutetext: Department of
Mathematics, Furman University, Greenville, SC 29613
22email<EMAIL_ADDRESS>33institutetext: Fabian Salinas
44institutetext: Spartanburg, SC 29372
44email<EMAIL_ADDRESS>
# Embedding Grid Graphs on Surfaces

Christian Millichap  Fabian Salinas

(Received: date / Accepted: date)

###### Abstract

In this paper, we analyze embeddings of grid graphs on orientable surfaces. We
determine the genus of two infinite classes of $3$-dimensional grid graphs
that do not admit quadrilateral embeddings and effective upper bounds for the
genus of any $3$-dimensional grid graph, both in terms of a grid graph’s
combinatorics. As an application, we provide a complete classification of
planar and toroidal grid graphs. Our work requires a variety of combinatorial
and graph theoretic arguments to determine effective lower bounds on the genus
of a grid graph, along with explicitly constructing embeddings of grid graphs
on surfaces to determine effective upper bounds on their genera.

Acknowledgment: The Version of Record of this article is published in Graphs
and Combinatorics, and is available online at
https://link.springer.com/article/10.1007/s00373-022-02488-w

###### Keywords:

Grid Graphs Quadrilateral Embeddings Genus of a Graph Planar Graphs Toroidal
Graphs

###### MSC:

05C10 57M15

##  1 Introduction

Define a path of length $\alpha$ $\in\mathbb{N}$ as the graph $P_{\alpha}$
that has vertex set $V=\\{v\in\mathbb{N}:0\leq v\leq\alpha\\}$ and where two
vertices determine an edge if and only if $|v_{i}-v_{j}|=1$ for
$v_{i},v_{j}\in V$. A $k$-dimensional grid graph
$G(\alpha_{1},\ldots,\alpha_{k})$ for $k\in\mathbb{N}$, is the graph Cartesian
product

$G(\alpha_{1},\ldots,\alpha_{k})=P_{\alpha_{1}}\boxempty\cdots\boxempty
P_{\alpha_{k}},$

where $\alpha_{i}\in\mathbb{N}$ for index $1\leq i\leq k$. We refer to the set
$\\{\alpha_{i}\\}_{i=1}^{k}$ as the grid parameters of
$G(\alpha_{1},\ldots,\alpha_{k})$. We use $G(\ast)$ to denote a grid graph
without specific grid parameters. A graph $G$ embeds on a closed connected
orientable surface of genus $g$, denoted $S_{g}$, if there exists a continuous
and one-to-one map $\phi:G\rightarrow S_{g}$. When it is obvious from context,
we will let $G$ also stand for its image $\phi(G)\subset S_{g}$. The genus of
a graph $G$, denoted $\gamma(G)$, is the smallest $g$ such that $G$ embeds on
$S_{g}$. Here, we are interested in studying embeddings of grid graphs and the
genera of grid graphs.

The genus of a grid graph $G(\ast)$ can be immediately determined when
$G(\ast)$ is known to have a quadrilateral embedding, that is, an embedding
where every face of $G(\ast)$ is bound by a $4$-cycle. Graphs admitting
quadrilateral embeddings have been well studied; see AbPa1983 , An1981 ,
Pi1980 , Pi1982 , Pi1989 . In particular, White in (Wh1970, , Theorem 4)
proved that any grid graph $G(\ast)$ with at least three odd grid parameters
admits a quadrilateral embedding, and so, determines the genus of $G(\ast)$.
However, White’s work does not address the infinite class of grid graphs that
admit at most two odd grid parameters. This raises a number of questions. Do
such grid graphs admit quadrilateral embeddings? If not, then can we determine
their genera? In this paper, we focus on addressing these questions for
$3$-dimensional grid graphs.

We now provide an outline of our major results. In Proposition 3, we detail an
explicit construction used to find an upper bound on the genus of any
$3$-dimensional grid graph with some even grid parameters, i.e., not covered
by White’s work. We then determine the genera for two infinite classes of
$3$-dimensional grid graphs where the bound from Proposition 3 is sharp; see
Theorem 4.2 and Theorem 4.3. In addition, we show that any grid graph (with
some even grid parameters) covered by these theorems, does not admit a
quadrilateral embedding. Lower bounds for the the genera of the grid graphs
discussed in Theorem 4.2 and Theorem 4.3 are determined using block
decompositions and finding complete bipartite graph minors in Section 4. In
Section 5, we make a quick observation about the maximum genus of a grid
graph, which is defined in that section. As a corollary of our work, we
classify exactly which grid graphs are planar, i.e., embed on the plane and
toroidal, i.e., embed on the torus, in Section 6.

##  2 Background

To start, we review some essential properties of grid graphs and graph
embeddings. The following lemma is a basic application of well known vertex
and edge counting formulas for Cartesian products of graphs. See ImKlRa2008
for more background on Cartesian products of graphs. We use $|V(G)|$ to denote
the number of vertices in a graph $G$ and $|E(G)|$ to denote the number of
edges in a graph $G$.

######  Lemma 1.

Let $G(\alpha_{1},\ldots,\alpha_{k})$ be a $k$-dimensional grid graph. Then we
have:

  1. 1.

$|V(G(\alpha_{1},\ldots,\alpha_{k}))|=\displaystyle\prod_{i=1}^{k}(\alpha_{i}+1).$

  2. 2.

$|E(G(\alpha_{1},\ldots,\alpha_{k}))|=\left(\displaystyle\prod_{i=1}^{k}(\alpha_{i}+1)\right)\left(\displaystyle\sum_{i=1}^{k}\frac{\alpha_{i}}{\alpha_{i}+1}\right).$

Lemma 1 provides a helpful dictionary which will be used in stating a number
of our results on embeddings of grid graphs. An embedding of a graph $G$ on a
surface $S$ is a $2$-cell embedding if each component of $S\setminus G$ is
homeomorphic to an open disk, in which case, we say $G$ 2-cell embeds on $S$.
Note that, any $2$-cell embedding is also an embedding, though the converse
isn’t necessarily true. We say that an embedding ($2$-cell embedding) of $G$
on $S_{g}$ is minimal if $\gamma(G)=g$. We do not distinguish between minimal
embeddings and minimal $2$-cell embeddings since the work of Youngs Yo1963
shows that each minimal embedding is a $2$-cell embedding. If $G$ $2$-cell
embeds on a surface $S_{g}$, then it determines a $2$-cell decomposition of
$S_{g}$ into vertices ($V$), edges ($E$), and faces ($F$), where $V$ and $E$
correspond with the vertices and edges of $G$, respectively, and each face is
a component of $S_{g}\setminus G$. Given such a $2$-cell embedding, the Euler
characteristic of $S_{g}$ is exactly $\chi(S_{g})=|V|-|E|+|F|$.

The following proposition and corollary motivate why we first consider the
genera of quadrilateral grid graphs. Both results are certainly well known but
we include them here for completeness. Recall that the girth of a graph $G$
(that is not a tree) is the length of its shortest cycle.

######  Proposition 1.

Suppose $G$ is a connected graph whose girth is at least $4$. Then

$\gamma(G)\geq 1+\frac{|E|}{4}-\frac{|V|}{2}.$

###### Proof.

Suppose $G$ $2$-cell embeds on a surface $S_{g}$, for some
$g\in\mathbb{N}_{0}$. The boundary of a face of this $2$-cell embedding is a
closed walk $W$ in $G$. We claim that $H$, the subgraph of $G$ induced by $W$,
contains a cycle. To see this, note that if $H$ did not contain a cycle, then
$H$ would be a tree. In this case, $G=H$ since our $2$-cell embedding could
only have one face if $H$ is a tree. However, this violates the assumptions
that $G$ has a cycle since it has nontrivial girth. Thus, the boundary of each
face in this $2$-cell embedding contains a subgraph that is a cycle, which
must contain at least $4$ edges based on the girth of $G$. At the same time,
each edge of this $2$-cell embedding appears on the boundary of at most two
faces. Thus, $|E|\geq\frac{4|F|}{2}=2|F|$, and so, $|F|\leq\frac{|E|}{2}$.
Then

$2-2g=\chi(S_{g})=|V|-|E|+|F|\leq|V|-|E|+\frac{|E|}{2}=|V|-\frac{|E|}{2},$

This implies that $g\geq 1+\frac{|E|}{4}-\frac{|V|}{2}$ and since this is true
for any $2$-cell embedding of $G$ on a closed connected orientable surface, we
have that $\gamma(G)\geq 1+\frac{|E|}{4}-\frac{|V|}{2}.$ ∎

######  Corollary 1.

Let $G(\alpha_{1},\ldots,\alpha_{k})$ be a grid graph with $k>1$. Then

$\gamma(G(\alpha_{1},\ldots,\alpha_{k}))\geq
1+\frac{|E|}{4}-\frac{|V|}{2}=1+\frac{1}{2}\prod_{i=1}^{k}(\alpha_{i}+1)\Big{[}\frac{1}{2}\sum_{i=1}^{k}\frac{\alpha_{i}}{\alpha_{i}+1}-1\Big{]}$

We have equality in the above formula if and only if
$G(\alpha_{1},\ldots,\alpha_{k})$ admits a quadrilateral embedding.

###### Proof.

First, we show that the girth of a $k$-dimensional grid graph is exactly 4
whenever $k>1$. It is easy to see that any such grid graph
$G(\ast)=G(\alpha_{1},\ldots,\alpha_{k})$ with $k>1$ contains a subgraph
isomorphic to $G(1,1)$, and so, $G(\ast)$ will always contain a $4$-cycle. In
addition, any grid graph is a simple graph (contains no loops or multi-edges),
so we only need to show that $G(\ast)$ has no $3$-cycles. Suppose $G(\ast)$
has a $3$-cycle determined by the vertices $v_{i}\in V(G(\ast))$ for $i=1,2,3$
with edges connecting each pair of vertices. Note that, there exists an edge
between two vertices in a grid graph if and only if the corresponding
$k$-tuples differ by one in one component and are equal in the rest. Thus, the
$k$-tuples representing $v_{1}$ and $v_{2}$ differ by one in exactly one grid
parameter and are equal in the rest of their respective grid parameters.
Similarly for the pair $v_{1}$ and $v_{3}$ and the pair $v_{2}$ and $v_{3}$.
However, this is not possible if $v_{1}$, $v_{2}$, and $v_{3}$ are all
distinct vertices. Thus, the girth of $G(\ast)$ is at least 4.

Now, the desired inequality in the first statement immediately follows from
combining Proposition 1 with the vertex and edge counting formulas from Lemma
1.

The second statement essentially follows from the proof of Proposition 1.
First, note that every edge in a grid graph occurs on a cycle. Then the
inequality $|F|\leq\frac{|E|}{2}$ in the proof of Proposition 1 becomes an
equality if and only if every face in a $2$-cell decomposition is bound by a
$4$-cycle. ∎

Corollary 1 shows that in some sense, quadrilateral grid graphs realize the
smallest possible genus for any such embedding of a grid graph relative to the
number of vertices and edges of that grid graph. The following theorem shows
that many grid graphs admit quadrilateral embeddings, and so, we can determine
their respective genera. This result was first proved by White in (Wh1970, ,
Theorem 4). Here, we have rephrased his work in terms of our notation.

######  Theorem 2.1.

(Wh1970, , Theorem 4) Let $G(\alpha_{1},\ldots,\alpha_{k})$ be a
$k$-dimensional grid graph where $k\geq 3$ and at least three $\alpha_{i}$ are
odd, for $i=1,\ldots,k$. Then $G(\alpha_{1},\ldots,\alpha_{k})$ admits a
quadrilateral embedding, i.e.,

$\gamma(G(\alpha_{1},\ldots,\alpha_{k}))=1+\frac{|E|}{4}-\frac{|V|}{2}=1+\frac{1}{2}\prod_{i=1}^{k}(\alpha_{i}+1)\Big{[}\frac{1}{2}\sum_{i=1}^{k}\frac{\alpha_{i}}{\alpha_{i}+1}-1\Big{]}.$

##  3 Upper bounds on the genus of a grid graph

In this section, we construct a $2$-cell embedding for each $3$-dimensional
grid graph $G(\ast)$, providing an upper bound on the genus of $G(\ast)$. In
Subsection 3.1, we discuss the case where all three grid parameters are odd.
By White’s work (Wh1970, , Theorem 4), such grid graphs are known to be
quadrilateral and his proof provides an explicit construction for such an
embedding. In Subsection 3.1, we provide our own method for building a
quadrilateral embedding for such grid graphs. Building off of this
construction, we then consider the case where some grid parameters are even in
Subsection 3.2.

###  3.1 $G(\alpha_{1},\alpha_{2},\alpha_{3})$ where all grid parameters are
odd

We first describe how to explicitly construct surfaces with a specified
$2$-cell structure. We will see that certain $3$-dimensional grid graphs embed
on these surfaces as the $1$-skeleton of their $2$-cell structure. Let
$U=\\{(x_{1},x_{2},x_{3})\in\mathbb{R}^{3}:0\leq x_{i}\leq 1\text{ for
}i=1,2,3\\}$ be the unit cube with it’s natural cell decomposition into eight
$0$-cells, twelve $1$-cells, six $2$-cells, and one $3$-cell. Let
$T(n_{1},n_{2},n_{3})$ be the unit cube translated by the vector
$(n_{1},n_{2},n_{3})\in\mathbb{N}_{0}^{3}$ and assume $T(n_{1},n_{2},n_{3})$
inherits this $3$-cell structure from $U$. Define
$C=C(\alpha_{1},\alpha_{2},\alpha_{3})$ for
$(\alpha_{1},\alpha_{2},\alpha_{3})\in\mathbb{N}^{3}$ as

$\displaystyle C=\\{$
$\displaystyle(n_{1},n_{2},n_{3})\in\mathbb{N}_{0}^{3}:\text{ At least 2
components in $(n_{1},n_{2},n_{3})$ are even,}$ $\displaystyle\text{ and
}n_{i}<\alpha_{i}\text{, for }i=1,2,3\\}.$

Define $W(\alpha_{1},\alpha_{2},\alpha_{3})$ as:

$W(\alpha_{1},\alpha_{2},\alpha_{3})=\bigcup_{(n_{1},n_{2},n_{3})\in
C}T(n_{1},n_{2},n_{3}).$

See Figure 1 for a visualization of $W(\alpha_{1},\alpha_{2},\alpha_{3})$
where each $\alpha_{i}$ is odd, for $i=1,2,3$. Intuitively,
$W(\alpha_{1},\alpha_{2},\alpha_{3})$ is constructed by gluing together copies
of unit cubes along some of their $2$-cells in pairs, where $C$ provides
instructions for where to place these cubes in $\mathbb{R}^{3}$ and which
$2$-cells to glue together. Based on this construction, it’s not difficult to
see that $W(\alpha_{1},\alpha_{2},\alpha_{3})$ is a $3$-manifold with
boundary. Furthermore, $W(\alpha_{1},\alpha_{2},\alpha_{3})$ inherits a
$3$-cell structure, $\mathcal{T}_{W}$, from the collection of translated
cubes, $\\{T(n_{1},n_{2},n_{3})\\}$, used in its construction.

Now let $S(\alpha_{1},\alpha_{2},\alpha_{3})=\partial
W(\alpha_{1},\alpha_{2},\alpha_{3})$, which must be a closed surface since it
is the boundary of a $3$-manifold. $S(\alpha_{1},\alpha_{2},\alpha_{3})$ is
connected since one can easily construct a continuous path from any point in
$S(\alpha_{1},\alpha_{2},\alpha_{3})$ to $(0,0,0)\in
S(\alpha_{1},\alpha_{2},\alpha_{3})$; we leave the details to the reader. In
addition, one can determine that $S(\alpha_{1},\alpha_{2},\alpha_{3})$ is
orientable by subdividing each $2$-cell (all of which are squares) into a pair
of triangles and providing consistent orientations across this triangulation.
Thus, $S(\alpha_{1},\alpha_{2},\alpha_{3})$ is homeomorphic to $S_{g}$ for
some $g\in\mathbb{N}\cup\\{0\\}$. The $3$-cell structure on
$W(\alpha_{1},\alpha_{2},\alpha_{3})$ induces a $2$-cell structure on
$S(\alpha_{1},\alpha_{2},\alpha_{3})$, which we denote by $\mathcal{T}_{S}$.
By construction, every face ($2$-cell) of $\mathcal{T}_{S}$ is bounded by a
$4$-cycle.

We define the 1-skeleton of a cell complex, $\Sigma$, as the union of its
$0$-cells and $1$-cells, and refer to this set as
$\operatorname{\text{skel}_{1}}(\Sigma)$. We claim that

$\operatorname{\text{skel}_{1}}(\mathcal{T}_{S})=\bigcup_{(n_{1},n_{2},n_{3})\in
C}\operatorname{\text{skel}_{1}}(T(n_{1},n_{2},n_{3})).$

Suppose there existed a point
$x\in\operatorname{\text{skel}_{1}}(T(n_{1},n_{2},n_{3}))$ where
$(n_{1},n_{2},n_{3})\in C$ such that $x$ belonged to the interior of
$W(\alpha_{1},\alpha_{2},\alpha_{3})$. It must follow then that $x$ is part of
the boundary of at least 4 translated unit cubes
$T_{1},T_{2},T_{3},T_{4}\subseteq W(\alpha_{1},\alpha_{2},\alpha_{3})$.
However, the vectors that determine these unit cubes cannot all be in
$C(\alpha_{1},\alpha_{2},\alpha_{3})$, which implies one of these unit cubes
is not in $W(\alpha_{1},\alpha_{2},\alpha_{3})$. Thus, it must be the case
that every edge in $\operatorname{\text{skel}_{1}}(T(n_{1},n_{2},n_{3}))$ must
lie on the boundary of $W(\alpha_{1},\alpha_{2},\alpha_{3})$. By definition of
$\mathcal{T}_{S}$, we have that

$\bigcup_{(n_{1},n_{2},n_{3})\in
C}\operatorname{\text{skel}_{1}}(T(n_{1},n_{2},n_{3}))\subseteq\operatorname{\text{skel}_{1}}(\mathcal{T}_{S}).$

Inclusion in the other direction follows trivially from the definitions. In
the following proposition, we will show that if $\alpha_{1}$, $\alpha_{2}$,
and $\alpha_{3}$ are all odd, then $G(\alpha_{1},\alpha_{2},\alpha_{3})$
embeds on $S(\alpha_{1},\alpha_{2},\alpha_{3})$ as
$\operatorname{\text{skel}_{1}}(\mathcal{T}_{S})$.

Figure 1: A representation of $W(\alpha_{1},\alpha_{2},\alpha_{3})$ when
$\alpha_{1},\alpha_{2},\alpha_{3}$ are all odd.

######  Proposition 2.

Let $G(\alpha_{1},\alpha_{2},\alpha_{3})$ be a $3$-dimensional grid graph
where all three grid parameters are odd. Then
$G(\alpha_{1},\alpha_{2},\alpha_{3})$ admits a quadrilateral embedding, i.e.,

$\displaystyle\gamma(G(\alpha_{1},\alpha_{2},\alpha_{3}))$
$\displaystyle=1+\frac{|E(G(\alpha_{1},\alpha_{2},\alpha_{3}))|}{4}-\frac{|V(G(\alpha_{1},\alpha_{2},\alpha_{3}))|}{2}.$

###### Proof.

Let $G(\ast)=G(\alpha_{1},\alpha_{2},\alpha_{3})$ be a $3$-dimensional grid
graph with all odd grid parameters. Corollary 1 tells us that
$\gamma(G(\ast))=1+\frac{|E(G(\ast))|}{4}-\frac{|V(G(\ast))|}{2}$ if and only
if $G$ admits a $2$-cell embedding on a surface where every face is bound by a
$4$-cycle in $G(\ast)$. We now describe how to construct a $2$-cell embedding
of $G(\ast)$ on a surface $S$ that meets these qualifications. Let
$S=S(\alpha_{1},\alpha_{2},\alpha_{3})$ be as defined above with corresponding
$2$-cell structure $\mathcal{T}_{S}$.

Consider the following subset of $\mathbb{R}^{3}$:

$\displaystyle Y=$
$\displaystyle\\{(x_{1},x_{2},x_{3})\in\mathbb{R}^{3}:\text{ At least 2
components in $(x_{1},x_{2},x_{3})$ are integers,}$ $\displaystyle\text{ and
}0\leq x_{i}\leq\alpha_{i}\text{, for }i=1,2,3\\}.$

It isn’t too difficult to see that $Y$ is an embedding of $G(\ast)$ in
$\mathbb{R}^{3}$ where vertices of $G(\ast)$ are mapped to their respective
coordinates in $\mathbb{R}^{3}$ and each edge of $G(\ast)$ is mapped to a
straight line segment.

We first show $\operatorname{\text{skel}_{1}}(\mathcal{T}_{S})\subseteq Y$.
Recall that $\operatorname{\text{skel}_{1}}(\mathcal{T}_{S})$ is constructed
by taking the union of 1-skeletons of the translated unit cubes used in the
construction of $W(\alpha_{1},\alpha_{2},\alpha_{3})$. Given how we defined
the unit cube $U$, it follows that any
$(u_{1},u_{2},u_{3})\in\operatorname{\text{skel}_{1}}(U)$ must have that at
least 2 components in $(u_{1},u_{2},u_{3})$ that are integers and $0\leq
u_{i}\leq 1\leq\alpha_{i}\text{ for }i=1,2,3$. By the definition of $Y$, we
can deduce that $\operatorname{\text{skel}_{1}}(U)\subseteq Y$.

Now consider any $T(n_{1},n_{2},n_{3})$ with $(n_{1},n_{2},n_{3})\in
C=C(\alpha_{1},\alpha_{2},\alpha_{3})$. Fix
$(x_{1},x_{2},x_{3})\in\operatorname{\text{skel}_{1}}(T(n_{1},n_{2},n_{3}))$,
and note that $(x_{1},x_{2},x_{3})=(u_{1}+n_{1},u_{2}+n_{2},u_{3}+n_{3})$ for
some $(u_{1},u_{2},u_{3})\in\operatorname{\text{skel}_{1}}(U)$. By definition
of $C$, we have that $0\leq n_{i}<\alpha_{i}$ and $n_{i}\in\mathbb{N}$ for
$i=1,2,3$. Since $0\leq u_{i}\leq 1\text{ for }i=1,2,3$, we have that

$0\leq u_{i}+n_{i}\leq\alpha_{i}\implies 0\leq x_{i}\leq\alpha_{i},\text{ for
}i=1,2,3.$

Also, since at least two components in $(u_{1},u_{2},u_{3})$ must be integers
(otherwise $(u_{1},u_{2},u_{3})\notin\operatorname{\text{skel}_{1}}(U)$) and
$n_{1},n_{2},n_{3}\in\mathbb{Z}$, we can deduce that at least two components
in $(u_{1}+n_{1},u_{2}+n_{2},u_{3}+n_{3})=(x_{1},x_{2},x_{3})$ are also
integers. So then by definition of $Y$, $(x_{1},x_{2},x_{3})\in Y$. Since the
argument holds for any
$(x_{1},x_{2},x_{3})\in\operatorname{\text{skel}_{1}}(T(n_{1},n_{2},n_{3}))$,
we have $\operatorname{\text{skel}_{1}}(T(n_{1},n_{2},n_{3}))\subseteq Y$.
Since the argument holds for any $(n_{1},n_{2},n_{3})\in C$ and
$\operatorname{\text{skel}_{1}}(U)\subseteq Y$, we have that

$\operatorname{\text{skel}_{1}}(\mathcal{T}_{S})=\bigcup_{(n_{1},n_{2},n_{3})\in
C}\operatorname{\text{skel}_{1}}(T(n_{1},n_{2},n_{3}))\subseteq Y,$

as desired. We now must show that
$Y\subseteq\operatorname{\text{skel}_{1}}(\mathcal{T}_{S})$. Let
$(x_{1},x_{2},x_{3})\in Y$. Without loss of generality, suppose $x_{1}=n_{1}$
and $x_{2}=n_{2}$ where $n_{1},n_{2}\in\mathbb{Z}$. Also, let
$n_{3}\in\mathbb{N}_{0}$ be the largest such that $n_{3}\leq x_{3}$ and
$n_{3}<\alpha_{3}$. By definition of $Y$, we can deduce that $0\leq
n_{i}\leq\alpha_{i}$ for $i=1,2,3$. Now consider
$\left(2\left\lfloor\frac{n_{1}}{2}\right\rfloor,2\left\lfloor\frac{n_{2}}{2}\right\rfloor,n_{3}\right)\in\mathbb{N}_{0}^{3}$.
We aim to show that
$\left(2\left\lfloor\frac{n_{1}}{2}\right\rfloor,2\left\lfloor\frac{n_{2}}{2}\right\rfloor,n_{3}\right)\in
C$, and

$(x_{1},x_{2},x_{3})\in\operatorname{\text{skel}_{1}}(T\left(2\left\lfloor\frac{n_{1}}{2}\right\rfloor,2\left\lfloor\frac{n_{2}}{2}\right\rfloor,n_{3}\right))\subseteq\operatorname{\text{skel}_{1}}(\mathcal{T}_{S}).$

Since by assumption $\alpha_{1}$ and $\alpha_{2}$ are both odd, we have

$0\leq n_{i}\leq\alpha_{i}\implies 0\leq
2\left\lfloor\frac{n_{i}}{2}\right\rfloor<\alpha_{i},\text{ for }i=1,2.$

Clearly,
$\left(2\left\lfloor\frac{n_{1}}{2}\right\rfloor,2\left\lfloor\frac{n_{2}}{2}\right\rfloor,n_{3}\right)$
contains 2 even components and since we assumed $n_{3}<\alpha_{3}$, we have by
the definition of $C$ that

$\left(2\left\lfloor\frac{n_{1}}{2}\right\rfloor,2\left\lfloor\frac{n_{2}}{2}\right\rfloor,n_{3}\right)\in
C.$

Now depending on the parity of $n_{1}$ and $n_{2}$, we have that
$(x_{1},x_{2},x_{3})=(n_{1},n_{2},x_{3})$ lies on exactly one of four
1-simplices in
$T\left(2\left\lfloor\frac{n_{1}}{2}\right\rfloor,2\left\lfloor\frac{n_{2}}{2}\right\rfloor,n_{3}\right))$.
Figure 2 illustrates this.

Figure 2: The 1-skeleton of the translated unit cube
$T\left(2\left\lfloor\frac{n_{1}}{2}\right\rfloor,2\left\lfloor\frac{n_{2}}{2}\right\rfloor,n_{3}\right))$.
The parity of $n_{1}$ and $n_{2}$ determine which 1-simplex
$(x_{1},x_{2},x_{3})$ lies in and how $n_{3}$ was defined implies $n_{3}\leq
x_{3}\leq n_{3}+1$.

Since the argument holds for any $(x_{1},x_{2},x_{3})\in Y$, we have that

$Y\subseteq\operatorname{\text{skel}_{1}}(\mathcal{T}_{S}).$

In summary, we have $Y$ is an embedding of $G(\ast)$ in $\mathbb{R}^{3}$ with
$Y=\operatorname{\text{skel}_{1}}(\mathcal{T}_{S})$. By construction,
$\operatorname{\text{skel}_{1}}(\mathcal{T}_{S})$ is the one-skeleton of the
$2$-cell structure $\mathcal{T}_{S}$ for the surface $S$, where each face
bounds a $4$-cycle, completing the proof. ∎

The construction used in the proof of Proposition 2 cannot immediately be
extended to $3$-dimensional grid graphs where some grid parameters are even.
It is always the case that the $1$-skeleton of
$\mathcal{T}_{S(\alpha_{1},\alpha_{2},\alpha_{3})}$ will provide a $2$-cell
embedding of a graph $G$ on the surface $S(\alpha_{1},\alpha_{2},\alpha_{3})$
where every face bounds a $4$-cycle. However, if at least one of the grid
parameters is even, then the graph $G$ will not be isomorphic to the desired
grid graph. For example, one could construct the surface $S(2,2,2)$ with its
corresponding $2$-cell complex $\mathcal{T}_{S(2,2,2)}$. Following the proof
of Proposition 2, one can still show that
$\operatorname{\text{skel}_{1}}(\mathcal{T}_{S(2,2,2)})\subseteq Y$ where $Y$
is the embedding of $G(2,2,2)$ in $\mathbb{R}^{3}$ outlined in the proof.

Trouble arises, however, in showing that
$Y\subseteq\operatorname{\text{skel}_{1}}(\mathcal{T}_{S(2,2,2)})$, since
$0\leq 2\left\lfloor\frac{n_{i}}{2}\right\rfloor<\alpha_{i}$ does not hold for
$n_{i}=\alpha_{i}=2$. Effectively, this implies that
$\operatorname{\text{skel}_{1}}(\mathcal{T}_{S(2,2,2)})$ is a proper subgraph
of $G(2,2,2)$; similar arguments hold for any grid graph with even components.

###  3.2 $G(\alpha_{1},\alpha_{2},\alpha_{3})$ where some grid parameters are
even

Here, we establish effective upper bounds on the genus of any $3$-dimensional
grid graph where some grid parameter is even. Afterwards, we briefly describe
how to construct a general (ineffective) upper bound on the genus of any
$k$-dimensional grid graph.

Let $G(\ast)$ be a grid graph and let $I\subset V(G(\ast))$. We say that
$G_{I}$ is the subgraph of $G(\ast)$ induced by $I$ where $V(G_{I})=I$ and
$E(G_{I})$ is the set of all edges in $G(\ast)$ that connect two vertices in
the set $I$.

######  Proposition 3.

If $G(\alpha_{1},\alpha_{2},\alpha_{3})$ be a $3$-dimensional grid graph with
at least one even grid parameter.

  1. 1.

If exactly one grid parameter is even (the third parameter), then

$\gamma(G(\alpha_{1},\alpha_{2},\alpha_{3}))\leq\gamma(G(\alpha_{1},\alpha_{2},\alpha_{3}-1))+\frac{(\alpha_{1}+1)(\alpha_{2}+1)}{4}-1.$

  2. 2.

If exactly two grid parameters are even (the second $\&$ third parameters),
then

$\gamma(G(\alpha_{1},\alpha_{2},\alpha_{3}))\leq\gamma(G(\alpha_{1},\alpha_{2},-1,\alpha_{3}-1))+\frac{(\alpha_{1}+1)(\alpha_{2}+\alpha_{3})}{4}-1.$

  3. 3.

If all three grid parameters are even, then

$\gamma(G(\alpha_{1},\alpha_{2},\alpha_{3}))\leq\gamma(G(\alpha_{1}-1,\alpha_{2}-1,\alpha_{3}-1))+\frac{\alpha_{1}\alpha_{2}+\alpha_{1}\alpha_{3}+\alpha_{2}\alpha_{3}}{4}-1.$

###### Proof.

Here, we provide full details for proving the third statement. The first two
statements follow from similar arguments and brief details for these are given
at the end of the proof.

Suppose $G(\ast)=G(\alpha_{1},\alpha_{2},\alpha_{3})$ is a $3$-dimensional
grid graph with all three grid parameters even. Let

$I=\\{(\beta_{1},\beta_{2},\beta_{3}):0\leq\beta_{i}\leq\alpha_{i}-1,\hskip
3.61371pt\text{for all}\hskip 3.61371pti=1,2,3\\}\subset V(G(\ast))$

and let

$J=\\{(\beta_{1},\beta_{2},\beta_{3}):\beta_{i}=\alpha_{i}\hskip
3.61371pt\text{for some}\hskip 3.61371pti=1,2,3\\}\subset V(G(\ast)).$

Consider the induced subgraphs $G_{I}$ and $G_{J}$ of $G(\ast)$. It is easy to
see that $G_{I}\cap G_{J}=\emptyset$, $V(G(\ast))=V(G_{I})\cup V(G_{J})$, and
$G_{I}\cong G(\alpha_{1}-1,\alpha_{2}-1,\alpha_{3}-1)$. Let
$E_{B}=E(G(\ast))\setminus\Big{(}E(G_{I})\cup E(G_{J})\Big{)}$. By
construction, we have that $G(\ast)=G_{I}\cup G_{J}\cup E_{B}$.

Since $G_{I}$ is a $3$-dimensional grid graph with all odd parameters, we can
$2$-cell embed $G_{I}$ on a surface $S_{I}$ whose genus is $\gamma(G_{I})$
where every face bounds a $4$-cycle, as done in the proof of Proposition 2. In
particular, the embedding of $(G_{I},S_{I})$ can be realized in
$\mathbb{R}^{3}$ where vertices of $G_{I}\cong
G(\alpha_{1}-1,\alpha_{2}-1,\alpha_{3}-1)$ are placed at their corresponding
coordinates in $\mathbb{R}^{3}$ and where edges are embedded as straight line
segments between these vertices.

We now consider a particular decomposition and embedding of $G_{J}$. First
off, it isn’t difficult to see that $G_{J}$ $2$-cell embeds on a $2$-sphere
$S_{J}\subset\mathbb{R}^{3}$ that is disjoint from
$(G_{I},S_{I})\subset\mathbb{R}^{3}$. Consider $G_{J}$ embedded in
$\mathbb{R}^{3}$ with each vertex of $G_{J}$ placed at its respective
coordinate and where edges of $G_{J}$ are embedded as straight line segments
between vertices. Insert a $2$-cell bounding each $4$-cycle in $G_{J}$ to
create a $2$-cell complex that will be homeomorphic to a $2$-disk, $D_{1}$.
Attach another (topological) $2$-disk, $D_{2}$, to $D_{1}$ glued along their
respective boundaries, where $D_{2}$ is embedded in $\mathbb{R}^{3}$ and is
disjoint from the surface $S_{I}$ (many such $2$-disks exist) to create the
$2$-sphere $S_{J}$ with the necessary conditions.

Let $(G_{J},S_{J})$ denote this particular embedding of $G_{J}$ and let

$J_{1}=\\{(\alpha_{1},\beta_{2},\beta_{3}):0\leq\beta_{i}\leq\alpha_{i}-1\hskip
3.61371pt\text{for i}\hskip 3.61371pt=2,3\\}\subset V(G_{J})\subset V(G),$
$J_{2}=\\{(\beta_{1},\alpha_{2},\beta_{3}):0\leq\beta_{i}\leq\alpha_{i}-1\hskip
3.61371pt\text{for i}\hskip 3.61371pt=1,3\\}\subset V(G_{J})\subset V(G),$
$J_{3}=\\{(\beta_{1},\beta_{2},\alpha_{3}):0\leq\beta_{i}\leq\alpha_{i}-1\hskip
3.61371pt\text{for i}\hskip 3.61371pt=1,2\\}\subset V(G_{J})\subset V(G).$

We consider the induced subgraphs for these respective sets of vertices and
note that $G_{J_{1}}\cong G(\alpha_{2}-1,\alpha_{3}-1)$, $G_{J_{2}}\cong
G(\alpha_{1}-1,\alpha_{3}-1)$, and $G_{J_{3}}\cong
G(\alpha_{1}-1,\alpha_{2}-1)$.

To construct an embedding of $G(\ast)$ on a surface $S$ with the required
genus, we will take $(G_{I},S_{I})$ and $(G_{J},S_{J})$ and add in handles to
connect these two surfaces while adding in the edges from $E_{B}$ along these
handles to connect $G_{I}$ to $G_{J}$ in the required manner. By construction,
$E_{B}$ must connect a vertex from $G_{J}$ to a vertex in $G_{I}$. By
definition of grid graph, this implies that for any edge $[v_{i},v_{j}]\in
E_{B}$ with say $v_{i}\in G_{I}$ and $v_{j}\in G_{J}$, we must have that
$v_{i}$ and $v_{j}$ have the same value for two of their grid parameters while
the remaining grid parameter is $\alpha^{*}-1$ for $v_{i}$ and $\alpha^{*}$
for $v_{j}$, where $\alpha^{*}$ could be either $\alpha_{1},\alpha_{2},$ or
$\alpha_{3}$. Thus, there is a bijective correspondence between $E_{B}$ and
$J_{1}\cup J_{2}\cup J_{3}$. Furthermore, for each vertex
$v_{i}=(\alpha_{1},\beta_{2},\beta_{3})\in J_{1}$, there is a unique edge in
$E_{B}$ connecting $v_{i}$ to the vertex
$v_{j}=(\alpha_{1}-1,\beta_{2},\beta_{3})\in V(G_{I})$, and similarly done for
$J_{2}$ and $J_{3}$. To add in the edges of $E_{B}$ that connect
$G_{J_{1}}\subset G_{J}$ to $G_{I}$, remove the interiors of the faces of
$(G_{J},S_{J})$ centered at $(\alpha_{1},1/2+2m,1/2+2n)$ where
$m=0,\ldots,\frac{\alpha_{2}}{2}-1$ and $n=0,\ldots,\frac{\alpha_{3}}{2}-1$
Likewise, remove the interiors of the corresponding face on $(G_{I},S_{I})$,
i.e. remove the interiors of the faces centered at
$(\alpha_{1}-1,1/2+2m,1/2+2n)$ where $m=0,\ldots,\frac{\alpha_{2}}{2}-1$ and
$n=0,\ldots,\frac{\alpha_{3}}{2}-1$; by construction, the $2$-cell complex for
$S_{I}$ has faces centered at all of these coordinates. Now attach a handle (a
copy of $\mathbb{S}^{1}\times[0,1]$) between corresponding faces that have
been removed, where $\mathbb{S}^{1}\times\\{0\\}$ glues to the face on
$G_{J_{1}}$ and $\mathbb{S}^{1}\times\\{1\\}$ glues to the corresponding face
on $G_{I}$. At the same time, we can embed a set of four edges from $E_{B}$
along each such handle, where each edge connects from a vertex $v_{j}\in
J_{1}$ to the corresponding vertex $v_{I}\in I$ as described above. This will
result in adding $(\frac{\alpha_{2}}{2})(\frac{\alpha_{3}}{2})$ handles
between $(G_{I},S_{I})$ and $(G_{J},S_{J})$. A similar procedure can be
performed for $J_{2}$ and $J_{3}$, which results in adding
$(\frac{\alpha_{1}}{2})(\frac{\alpha_{3}}{2})$ and
$(\frac{\alpha_{1}}{2})(\frac{\alpha_{2}}{2})$ handles, respectively, between
$(G_{I},S_{I})$ and $(G_{J},S_{J})$. At the end of this process, we will have
a $2$-cell embedding of $G(\ast)$ on a surface $S$ with genus

$\displaystyle\gamma(S)$
$\displaystyle=\gamma(S_{I})+\gamma(S_{J})+\Big{(}\frac{\alpha_{2}}{2}\Big{)}\Big{(}\frac{\alpha_{3}}{2}\Big{)}+\Big{(}\frac{\alpha_{1}}{2}\Big{)}\Big{(}\frac{\alpha_{3}}{2}\Big{)}+\Big{(}\frac{\alpha_{1}}{2}\Big{)}\Big{(}\frac{\alpha_{2}}{2}\Big{)}-1$
$\displaystyle=\gamma(G(\alpha_{1}-1,\alpha_{2}-1,\alpha_{3}-1))+\frac{\alpha_{1}\alpha_{2}+\alpha_{1}\alpha_{2}+\alpha_{2}\alpha_{3}}{4}-1.$

We subtract $1$ at the end of this formula since the first handle attached
connecting $S_{I}$ to $S_{J}$ does not contribute to the genus of the
resulting surface.

For items (1) and (2), a similar decomposition of $G(\ast)$ can be used. For
instance, to prove (1), let $I=\\{(\beta_{1},\beta_{2},\beta_{3})\hskip
3.61371pt:\hskip
3.61371pt0\leq\beta_{1}\leq\alpha_{1},0\leq\beta_{2},\leq\alpha_{2},0\leq\beta_{3}\leq\alpha_{3}-1\\}\subset
V(G)$ and let $J=\\{(\beta_{1},\beta_{2},\alpha_{3})\hskip 3.61371pt:\hskip
3.61371pt0\leq\beta_{1}\leq\alpha_{1},0\leq\beta_{2}\leq\alpha_{2}\\}\subset
V(G).$ Consider the induced subgraphs $G_{I}$ and $G_{J}$ of $G(\ast)$, and
define $E_{B}=E(G(\ast))\setminus\Big{(}E(G_{I})\cup E(G_{J})\Big{)}$. By
construction, we have that $G(\ast)=G_{I}\cup G_{J}\cup E_{B}$. Again, use the
$2$-cell embedding of $G_{I}$ on $S_{I}$ coming from Proposition 2 and use the
$2$-cell embedding of $G_{J}$ on a $2$-sphere $S_{J}$ in the same manner as
the previous case. Now, add handles between $(S_{I},G_{I})$ and
$(S_{J},G_{J})$ that contain the edges of $E_{B}$ in order to construct a
$2$-cell embedding of $G(\ast)$ on a surface with the required genus. ∎

######  Remark 1.

By Corollary 1, the upper bounds in Proposition 3 can be computed in terms of
the grid parameters of the given grid graph.

######  Remark 2.

The upper bounds for genus given in Proposition 3 are sharp for infinite
families of grid graphs; see the proofs of Theorem 4.2 and Theorem 4.3. In
fact, we conjecture that this upper bound is always sharp; see Conjecture 1.

The following corollary gives an alternative method for calculating the genus
of any surface constructed in the proof of Proposition 3. In what follows, let
$P=0$ if $G(\ast)$ has no even grid parameters, $P=2\alpha_{1}+2\alpha_{2}$ if
$G(\ast)$ has one even grid parameter (the third parameter), and
$P=2\alpha_{1}+2\alpha_{2}+2\alpha_{3}$ if $G(\ast)$ has two or three even
grid parameters. Intuitively, $P$ stands for the perimeter length of a
particular face constructed in the $2$-cell embedding from Proposition 3.

######  Corollary 2.

Let $G(\alpha_{1},\alpha_{2},\alpha_{3})$ be a $3$-dimensional grid graph.
Then $G(\alpha_{1},\alpha_{2},\alpha_{3})$ $2$-cell embeds on a surface $S$
with genus

$\gamma(S)=\frac{1}{2}+\frac{|E(G(\alpha_{1},\alpha_{2},\alpha_{3}))|}{4}-\frac{|V(G(\alpha_{1},\alpha_{2},\alpha_{3}))|}{2}+\frac{P}{8}.$

###### Proof.

First, if all three grid parameters are odd then $P=0$ and the result
immediately follows from Proposition 2. From here, we follow the same
procedure used in the proof of Corollary 1 while taking into account the
specific $2$-cell embeddings built in the proof of Proposition 3. Let
$(G(\ast),S_{g})$ be a $2$-cell embedding of
$G(\ast)=G(\alpha_{1},\alpha_{2},\alpha_{3})$ on the surface $S_{g}$ from the
proof of Proposition 3. By construction, every face in this $2$-cell embedding
bounds a 4-cycle, except the one “outer” face $F^{*}$ on the $2$-sphere
$S_{J}$; this face is homeomorphic to the $2$-disk $D_{1}$ used to construct
$S_{J}$ in the proof of Proposition 3. The cycle length of the boundary of
$F^{*}$ is exactly $P$. Since every edge bounds exactly $2$-faces, we have
that $|E(G(\ast))|=\frac{4(|F|-1)}{2}+\frac{P}{2}$, which implies that
$|F|=\frac{|E(G(\ast))|}{2}-\frac{P}{4}+1$. Thus,

$\displaystyle 2-2g$
$\displaystyle=\chi(S_{g})=|V(G(\ast))|-|E(G(\ast))|+\Big{(}\frac{|E(G(\ast))|}{2}-\frac{P}{4}+1\Big{)}$
$\displaystyle=|V(G(\ast))|-\frac{|E(G(\ast))|}{2}-\frac{P}{4}+1.$

Solving in terms of $g$ gives the desired result. ∎

Tubing and pasting arguments similar to the ones implemented in White’s work
Wh1970 , could possibly be used to obtain upper bounds on the genus of any
$k$-dimensional grid graph. Here, we provide a quick (ineffective) upper bound
that certainly could be improved upon.

######  Lemma 2.

Let $G(\alpha_{1},\ldots,\alpha_{k})$ be any $k$-dimensional grid graph. Then

$\gamma(G(\alpha_{1},\ldots,\alpha_{k}))\leq\gamma(G(\alpha_{1}-1,\alpha_{2},\ldots,\alpha_{k}))+\gamma(G(\alpha_{2},\ldots,\alpha_{k}))+\Big{[}\prod_{i=2}^{k}(\alpha_{i}+1)\Big{]}-1.$

###### Proof.

Given a $k$-dimensional grid graph $G(\ast)=G(\alpha_{1},\ldots,\alpha_{k})$,
let

$I=\\{(\beta_{1},\beta_{2},\ldots,\beta_{k}):0\leq\beta_{1}\leq\alpha_{1}-1,0\leq\beta_{i},\leq\alpha_{i},\hskip
3.61371pt\text{for}\hskip 3.61371pti=2,\ldots,k\\}\subset V(G(\ast))$

and let

$J=\\{(\alpha_{1},\beta_{2},\ldots,\beta_{k}):0\leq\beta_{i}\leq\alpha_{i},\text{for}\hskip
3.61371pti=2,\ldots,k\\}\subset V(G(\ast)).$

Consider the induced subgraphs $G_{I}$ and $G_{J}$ of $G(\ast)$. It is easy to
see that $G_{I}\cap G_{J}=\emptyset$, $V(G(\ast))=V(G_{I})\cup V(G_{J})$,
$G_{I}\cong G(\alpha_{1}-1,\alpha_{2},\ldots,\alpha_{k})$, and $G_{J}\cong
G(\alpha_{2},\ldots,\alpha_{k})$. Let
$E_{B}=E(G(\ast))\setminus\Big{(}E(G_{I})\cup E(G_{J})\Big{)}$. By
construction, we have that $G(\ast)=G_{I}\cup G_{J}\cup E_{B}$.

Now, $2$-cell embed $G_{I}$ on a surface $S_{I}$ of genus
$\gamma(G(\alpha_{1}-1,\alpha_{2},\ldots,\alpha_{k}))$ and $2$-cell embed
$G_{J}$ on a surface $S_{J}$ of genus
$\gamma(G(\alpha_{2},\ldots,\alpha_{k}))$. Since there is a bijective
correspondence between the set of vertices of $G_{J}\cong
G(\alpha_{2},\ldots,\alpha_{k})$ and the set of edges $E_{B}$, we have that
$|E_{B}|=\prod_{i=2}^{k}(\alpha_{i}+1)$. In a small neighborhood of each
vertex on $(G_{J},S_{J})$, attach one end of a handle (a copy of
$\mathbb{S}^{1}\times[0,1]$) along with the corresponding edge from $E_{B}$
that connects to this vertex and attach the other end of the handle to the
corresponding vertex on $(G_{I},S_{I})$. This will provide an embedding of
$G(\ast)$ on a surface $S$, obtained from attaching
$\Big{[}\prod_{i=2}^{k}(\alpha_{i}+1)\Big{]}$ handles between $S_{I}$ and
$S_{J}$, and so, will have the desired genus. ∎

Given any $k$-dimensional grid graph $G(\ast)$, Lemma 2 could be applied
successively to obtain an upper bound on $\gamma(G(\ast))$ in terms of the
genera of subgraphs of $G(\ast)$, all of which are either $3$-dimensional grid
graphs or grid graphs with at least three odd grid parameters. From here, one
could apply Proposition 3 and Theorem 2.1 to obtain an upper bound on
$\gamma(G(\ast))$ that is exclusively a function of its grid parameters. As
mentioned before the proof, this upper bound is ineffective and could be
improved by embedding more edges from $E_{B}$ on each handle. Determining an
efficient scheme for distributing edges from $E_{B}$ onto handles would
require more explicit details on the embeddings of $(G_{I},S_{I})$ and
$(G_{J},S_{J})$.

##  4 The Genus of a non-quadrilateral grid graph

We now discuss and apply tools needed to determine a sharp lower bound on the
genera of infinitely many non-quadrilateral grid graphs.

A block of a graph $G$ is a maximal $2$-connected subgraph $B$ of $G$. Given a
connected graph $G$, there exists a unique collection of blocks
$\mathcal{B}=\\{B_{1},\ldots,B_{k}\\}$ such that $\cup_{i=1}^{k}B_{i}=G$,
which is called the block decomposition of $G$ in BHKY1962 . The work of
Battle–Harary–Kodama–Youngs BHKY1962  provides a useful characterization of
the genus of a graph in terms of its block decomposition.

######  Theorem 4.1.

BHKY1962  If $G$ is a graph with block decomposition
$\\{B_{1},\ldots,B_{k}\\}$, then $\gamma(G)=\sum_{i=1}^{k}\gamma(B_{i})$.
Furthermore, if $G$ is a graph with $m$ components $G_{1},\ldots,G_{m}$, then
$\gamma(G)=\sum_{i=1}^{m}\gamma(G_{m})$.

The following graphs arise as minors of grid graphs analyzed in this section.

######  Definition 1.

Let $T_{n}$ denote the graph constructed by gluing $n$ copies of $K_{3,3}$
along vertices as seen in Figure 3.

Figure 3:

######  Lemma 3.

For each $n\in\mathbb{N}$, $T_{n}$ consists of $n$ blocks of $K_{3,3}$, and
$\gamma(T_{n})=n$.

###### Proof.

This lemma follows directly from Theorem 4.1 and the fact that
$\gamma(K_{3,3})=1$. ∎

We now plan to use Lemma 3 to help find the genera of an infinite family of
grid graphs that do not admit quadrilateral embeddings in Theorem 4.2. First,
we need a few additional lemmas to deal with special cases that arise in the
proof of Theorem 4.2.

Figure 4: Subgraph $\Gamma$ of $G(\alpha,2,1)$ colored in red.

######  Lemma 4.

For any $\alpha\in\mathbb{N}$ where $\alpha\geq 2$, we have
$\gamma(G(\alpha,2,1))\geq\gamma(\Gamma)\geq\left\lfloor\frac{\alpha}{2}\right\rfloor$,
where $\Gamma$ is the subgraph of $G(\alpha,2,1)$ shown in Figure 4.

###### Proof.

Let $\alpha\in\mathbb{N}$ be arbitrary and let
$a=\left\lfloor\frac{\alpha}{2}\right\rfloor$. The graph $G(\alpha,2,1)$ is
depicted in Figure 4 with a subgraph $\Gamma$ highlighted. We can obtain a
specific minor of $\Gamma$ by contracting certain vertices (see Figure 5).

Figure 5: Orange contracted vertices of $\Gamma$ to get $T_{a}$ .

However, this minor is equivalent to $T_{a}$ as defined in Definition 1. It
then follows from Lemma 3 that $\gamma(T_{a})=a$. So then we can deduce that
$\gamma((G(\alpha,2,1))\geq\gamma(\Gamma)\geq\gamma(T_{a})=a$, as desired. ∎

######  Lemma 5.

For any $\alpha\in\mathbb{N}$, $\gamma(G(\alpha,1,1))=0$, i.e.,
$G(\alpha,1,1)$ is planar.

###### Proof.

Embed $G(\alpha,1,1)$ in $\mathbb{R}^{3}$ with vertices positioned at their
respective coordinates and edges connecting vertices via straight line
segments. Then it is easy to see that $G(\alpha,1,1)$ is the $1$-skeleton of a
$2$-cell structure of a cylinder with a square base. Take a homeomorphism of
this cylinder in $\mathbb{R}^{3}$ to an annulus in $\mathbb{R}^{2}$. Then the
image of $\Gamma$ under this homeomorphism will provide an embedding of
$G(\alpha,1,1)$ in the plane. ∎

######  Theorem 4.2.

For any $\alpha_{1},\alpha_{2}\in\mathbb{N}$ we have that

$\gamma(G(\alpha_{1},\alpha_{2},1))=\left\lfloor\frac{\alpha_{1}}{2}\right\rfloor\left\lfloor\frac{\alpha_{2}}{2}\right\rfloor.$

In addition, infinitely many $G(\alpha_{1},\alpha_{2},1)$ do not admit
quadrilateral embeddings.

###### Proof.

To start, if $\alpha_{1}=1$ or $\alpha_{2}=1$, then
$G(\alpha_{1},\alpha_{2},1)\cong G(\alpha_{1},1,1)$ embeds in the plane by
Lemma 5. Thus,
$\gamma(G(\alpha_{1},1,1))=0=\left\lfloor\frac{\alpha_{1}}{2}\right\rfloor\left\lfloor\frac{1}{2}\right\rfloor$,
as needed.

Now suppose $\alpha_{1},\alpha_{2}\geq 2$. Using the subgraph $\Gamma$ of
$G(\alpha,2,1)$ described in Lemma 4, we can glue together
$\left\lfloor\frac{\alpha_{2}}{2}\right\rfloor$ copies of $G(\alpha,2,1)$
while taking care to keep the subgraphs $\Gamma$ in each copy of
$G(\alpha,2,1)$ disjoint, to get a subgraph of $G(\alpha_{1},\alpha_{2},1)$;
see Figure 6. Since
$\gamma(\Gamma)\geq\left\lfloor\frac{\alpha_{1}}{2}\right\rfloor$ by Lemma 4
and we have $\left\lfloor\frac{\alpha_{2}}{2}\right\rfloor$ disjoint copies of
$\Gamma$ in $G(\alpha_{1},\alpha_{2},1)$, we can deduce that
$\gamma(G(\alpha_{1},\alpha_{2},1))\geq\left\lfloor\frac{\alpha_{1}}{2}\right\rfloor\left\lfloor\frac{\alpha_{2}}{2}\right\rfloor$.

Figure 6: Gluing of $\left\lfloor\frac{\alpha_{2}}{2}\right\rfloor$ copies of
$G(\alpha_{1},2,1)$ contained inside of $G(\alpha_{1},\alpha_{2},1)$. Each
copy of $G(\alpha_{1},2,1)$ contains a subgraph isomorphic to $\Gamma$
(colored in red and blue) and these copies of $\Gamma$ are pairwise disjoint
as subgraphs of $G(\alpha_{1},\alpha_{2},1)$.

To show that
$\gamma(G(\alpha_{1},\alpha_{2},1))\leq\left\lfloor\frac{\alpha_{1}}{2}\right\rfloor\left\lfloor\frac{\alpha_{2}}{2}\right\rfloor$,
we can use Theorem 2.1 and Proposition 3. This requires a few cases depending
on the parity of $\alpha_{1}$ and $\alpha_{2}$. However, in all of these
cases, the upper bounds on genus from Theorem 2.1 and Proposition 3 are
equivalent to
$\left\lfloor\frac{\alpha_{1}}{2}\right\rfloor\left\lfloor\frac{\alpha_{2}}{2}\right\rfloor$.
We leave the details of explicitly checking the algebra for the reader.

It is easy to see that many of these grid graphs do not admit quadrilateral
embeddings. Specifically, Corollary 1 gives
$\gamma(G(\alpha_{1},\alpha_{2},1))\geq\frac{1}{4}(\alpha_{1}-1)(\alpha_{2}-1)$,
with equality if and only if the corresponding grid graph admits a
quadrilateral embedding, i.e., both $\alpha_{1}$ and $\alpha_{2}$ are odd in
this case. Thus, if either $\alpha_{1}$ or $\alpha_{2}$ is even, then
$G(\alpha_{1},\alpha_{2},1)$ does not admit a quadrilateral embedding. ∎

The final paragraph of the proof of Theorem 4.2 shows that there exist grid
graphs that are “arbitrarily far away” from having a quadrilateral embedding,
which contrast the grid graphs studied by White in Wh1970 . More generally,
given a graph $G$ with girth at least 4, define the quadrilateral distance of
$G$ to be the quantity

$d_{Q}(G)=\gamma(G)-\Big{(}1+\frac{|E(G)|}{4}-\frac{|V(G)|}{2}\Big{)}.$

Note that $d_{Q}(G)\geq 0$ and $d_{Q}(G)=0$ if and only if $G$ admits a
quadrilateral embedding. The following corollary immediately follows from
Theorem 4.2.

######  Corollary 3.

Consider the sequence of grid graphs $\\{G(2n,2,1)\\}_{n=1}^{\infty}$. Then

$d_{Q}(G(2n,2,1))\rightarrow\infty\hskip 3.61371pt\text{as}\hskip
3.61371ptn\rightarrow\infty.$

We now determine the genera of a different infinite family of non-
quadrilateral grid graphs.

######  Theorem 4.3.

For any $\alpha\in\mathbb{N}$, we have that $\gamma(G(\alpha,2,2))=\alpha$.
Every $G(\alpha,2,2)$ does not admit a quadrilateral embedding.

###### Proof.

Figure 7 shows how to delete and contract edges of $G(\alpha,2,2)$ to obtain a
$K_{3,4\alpha}$ minor. By the genus formula for complete bipartite graphs
(Ri1965 , Bo1978 ) we have:

$\alpha=\left\lceil\alpha-\frac{1}{2}\right\rceil=\left\lceil\frac{(3-2)(4\alpha-2)}{4}\right\rceil=\gamma(K_{3,{4\alpha}})\leq\gamma(G(\alpha,2,2)).$

Figure 7: Minor of $G(\alpha,2,2)$ to $K_{3,4\alpha}$. The blue, orange, and
purple paths are contracted to single vertices. The red edges are deleted.

To obtain the desired upper bound on any $\gamma(G(\alpha,2,2))$, we apply
results (2) and (3) from Proposition 3, depending on whether $\alpha$ is even
or odd, respectively. First, recall that $G(\alpha,1,1)$ is planar by Lemma 5.
Now, if $\alpha$ is odd, then

$\gamma(G(\alpha,2,2))\leq\gamma(G(\alpha,1,1))+\frac{(\alpha+1)(2+2)}{4}-1=\alpha.$

If $\alpha$ is even, then

$\gamma(G(\alpha,2,2))\leq\gamma(G(\alpha-1,1,1))+\frac{2\alpha+2\alpha+4}{4}-1=\alpha.$

Finally, we note that $G(\alpha,2,2)$ is not quadrilateral for any
$\alpha\in\mathbb{N}$ since the lower bound on its genus from Corollary 1
gives $\gamma(G(\alpha,2,2))\geq\frac{3\alpha-2}{4}$, and
$\gamma(G(\alpha,2,2))=\alpha>\frac{3\alpha-2}{4}$ for all
$\alpha\in\mathbb{N}$. ∎

Consider the sets of grid graphs $\\{G(\alpha,2,2)\\}$ with
$\alpha\in\mathbb{N}$ and $\\{G(\alpha_{1},\alpha_{2},1)\\}$ with some
$\alpha_{i}$ even for $i=1,2$. All of these $3$-dimensional grid graphs have
at least one even grid parameter and a minimal genus $2$-cell embedding for
each such graph can be constructed using the procedure described in the proof
of Proposition 3. This motivates the following conjecture:

######  Conjecture 1.

If $G(\alpha_{1},\alpha_{2},\alpha_{3})$ is a $3$-dimensional grid graph with
at least one even parameter, then the $2$-cell embedding for
$G(\alpha_{1},\alpha_{2},\alpha_{3})$ constructed in Proposition 3 is a
minimal embedding, i.e., the upper bounds in Proposition 3 are in fact
equalities.

Perhaps a generalization of the arguments used in the proofs of Theorem 4.2
and Theorem 4.3 could be modified to prove this conjecture. However, this was
not immediately obvious since different arguments were used to determine sharp
lower bounds on $\gamma(G(\alpha_{1},\alpha_{2},1))$ and
$\gamma(G(\alpha,2,2))$. We tried to find a block decomposition that would
provide a sharp lower bound on $\gamma(G(\alpha,2,2))$ but were unsuccessful.

##  5 The Maximum Genus of a Grid Graph

The maximum genus $\gamma_{M}(G)$ of a graph $G$ is the largest possible $g$
for which $G$ $2$-cell embeds on $S_{g}$. Recall that the Betti number of a
graph $G$ is $\beta(G)=|E|-|V|+1$. If $G$ $2$-cell embeds on $S_{g}$, we have
that $2-2g=\chi(S_{g})=|V|-|E|+|F|.$ Any such embedding must have at least one
face, and so, we always have the upper bound
$\gamma_{M}(G)\leq\lfloor{\frac{\beta(G)}{2}}\rfloor$. A graph $G$ is called
upper-embeddable if $\gamma_{M}(G)=\lfloor{\frac{\beta(G)}{2}}\rfloor$. Here,
we summarize some facts about the maximum genus of a grid graph.

######  Theorem 5.1.

Every grid graph is upper-embeddable.

###### Proof.

First, any $1$-dimensional grid graph $G(\alpha)$ is upper-embeddable since
such a graph is a path with $\alpha+1$ vertices and $\alpha$ edges, and we
obviously have that $\gamma_{M}(G(\alpha))=0$.

Now, Corollary 3.3 in Mohar–Pisanski–S̆koviera MoPiSk1988  states that the
Cartesian product of any two loopless connected non-trivial graphs is upper-
embeddable. Note that any $k$-dimensional grid graph with $k\geq 2$ can be
expressed as the Cartesian product of two subgraphs that are each (lower-
dimensional) grid graphs. At the same time, any grid graph is a loopless
connected non-trivial graph. Thus, by (MoPiSk1988, , Corollary 3.3), any grid
graph is upper-embeddable. ∎

The following corollary characterizes the maximum genus of a grid graph in
terms of its grid parameters.

######  Corollary 4.

The maximum genus of a $k$-dimensional grid graph
$G(\alpha_{1},\ldots,\alpha_{k})$ is exactly

$\gamma_{M}(G(\alpha_{1},\ldots,\alpha_{k}))=\Bigg{\lfloor}{\frac{1}{2}\left(\prod_{i=1}^{k}(\alpha_{i}+1)\right)\Big{(}\left(\sum_{i=1}^{k}\frac{\alpha_{i}}{\alpha_{i}+1}\right)-1\Big{)}+\frac{1}{2}}\Bigg{\rfloor}$

###### Proof.

$G(\alpha_{1},\ldots,\ldots\alpha_{k})$ is upper-embeddable by Theorem 5.1,
which implies that

$\gamma_{M}(G(\alpha_{1},\ldots,\alpha_{k}))=\Big{\lfloor}{\frac{\beta(G(\alpha_{1},\ldots,\alpha_{k}))}{2}}\Big{\rfloor}.$

We get the desired formula by applying Lemma 1 to obtain formulas for $|E|$
and $|V|$, respectively, in terms of the grid parameters
$\alpha_{1},\ldots,\alpha_{k}$. ∎

The genus range of a graph $G$ is the set
$R(G)=\\{g\in\mathbb{N}:\gamma(G)\leq g\leq\gamma_{M}(G)\\}$. The
interpolation theorem of Duke Du1966  shows that $G$ will $2$-cell embed on
every surface $S_{g}$, where $g\in R(G)$. One could combine Corollary 4 with
results from Section 2 to obtain explicit formulas for the genus range of many
grid graphs in terms their respective grid parameters. To give an explicit
example that will also be used in the proof of Theorem 6.1, we consider the
genus range of any $k$-dimensional $G(1,\ldots,1)$. Such a grid graph is
isomorphic to the well studied $k$-dimensional hypercube, $Q_{k}$. An exact
genus formula for $Q_{k}$ was first proved by Ringel in Ri1955  and Beineke
and Harary in BeHa1965 . More recently, Shouman Sh2019  has provided a proof
using the real moment-angle complex. In addition, a maximum genus formula for
$Q_{k}$ was given by Zaks in Za1974 . A genus formula for $Q_{k}$ can be
derived as a special case of Theorem 2.1, while Corollary 4 supplies a maximum
genus formula, both of which are highlighted in the following corollary.

######  Corollary 5.

For any $k\geq 2$, the genus range of the $k$-dimensional grid graph
$G(1,\ldots,1)\cong Q_{k}$ is exactly

$\\{g\in\mathbb{N}:1+(k-4)2^{k-3}\leq g\leq(k-2)2^{k-2}\\}.$

##  6 Planar and Toroidal Grid Graphs

In this section, our main goal is to classify which grid graphs $2$-cell embed
on the torus. First, we classify which grid graphs are planar.

######  Proposition 4.

A grid graph $G(\alpha_{1},\ldots,\alpha_{k})$ is planar if and only if

  1. 1.

$k\leq 2$ or

  2. 2.

$k=3$ and at most one of $\alpha_{1}$, $\alpha_{2}$, $\alpha_{3}$ is greater
than $1$.

###### Proof.

The fact that $k$-dimensional grid graphs are planar for $k=1,2$ is obvious.
For the second case, any such grid graph is isomorphic to $G(\alpha,1,1)$ for
some $\alpha\in\mathbb{N}$. Such grids are planar by Lemma 5.

To show that no other grid graphs are planar, we consider two cases. Any
$3$-dimensional grid graph with at least two of $\alpha_{1}$, $\alpha_{2}$,
and $\alpha_{3}$ greater than 1 contains a subgraph isomorphic to $G(2,2,1)$.
However, Theorem 4.2 shows that $\gamma(G(2,2,1))=1$, and so, any graph
containing $G(2,2,1)$ as a subgraph is non-planar. Now consider any
$k$-dimensional grid graph where $k\geq 4$. Any such grid graph contains a
subgraph isomorphic to $G(1,1,1,1)$. Using Corollary 5, we see that
$G(1,1,1,1)$ is non-planar, and so, any graph containing $G(1,1,1,1)$ as a
subgraph is non-planar, as needed. ∎

######  Theorem 6.1.

A grid graph $G(\alpha_{1},\ldots,\alpha_{k})$ $2$-cell embeds on the torus if
and only if

  1. 1.

$k=2$ and $\alpha_{1}+\alpha_{2}\geq 3$,

  2. 2.

$k=3$ and at most one of $\alpha_{1}$, $\alpha_{2}$, $\alpha_{3}$ is greater
than 1,

  3. 3.

$k=3$ and up to permutation,
$(\alpha_{1},\alpha_{2},\alpha_{3})\in\\{(2,2,1),(3,2,1),(3,3,1)\\}$, or

  4. 4.

$k=4$ and $(\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4})=(1,1,1,1)$.

###### Proof.

We break this proof down into a series of cases, based on the dimension $k$.

For $k=1$, we have that $G(\alpha_{1})$ is a path, which does not $2$-cell
embed on the torus.

For $k=2$, we can apply Corollary 4 to get that the genus range of
$G(\alpha_{1},\alpha_{2})$ is precisely $\\{g\in\mathbb{N}:0\leq
g\leq\lfloor{\frac{1}{2}\alpha_{1}\alpha_{2}}\rfloor\\}.$ Thus,
$G(\alpha_{1},\alpha_{2})$ embeds on the torus if and only if
$\alpha_{1}+\alpha_{2}\geq 3$, as needed.

For $k=3$, multiple subcases are necessary. If at most one of $\alpha_{1}$,
$\alpha_{2}$, $\alpha_{3}$ is greater than $1$, then such a grid graph is
graph isomorphic to $G(\alpha,1,1)$ for some $\alpha\in\mathbb{N}$, which is
planar by Lemma 5. To determine that such a graph $2$-cell embeds on the
torus, apply Corollary 4 to establish that
$\gamma_{M}(G(\alpha,1,1))=\lfloor{\frac{4\alpha+1}{2}\rfloor}$. Thus, the
genus range for such graphs always include $g=1$, as needed. Next, the grid
graphs $G(2,2,1)$, $G(3,2,1)$, and $G(3,3,1)$ all $2$-cell embed on the torus
by Theorem 4.2. Now, we will justify that any other $3$-dimensional grid graph
does not $2$-cell embed on the torus. By Theorem 4.3, $\gamma(G(2,2,2))=2$.
Then if all $\alpha_{i}\geq 2$, we have that
$\gamma(G(\alpha_{1},\alpha_{2},\alpha_{3}))\geq\gamma(G(2,2,2))\geq 2$, and
so, any such $G(\alpha_{1},\alpha_{2},\alpha_{3})$ does not $2$-cell embed on
the torus. Thus, we now only need to consider
$G(\alpha_{1},\alpha_{2},\alpha_{3})$ where exactly one such $\alpha_{i}=1$.
Combined with the fact we just showed $G(2,2,1)$, $G(3,2,1)$, and $G(3,3,1)$
are all toroidal, it only remains to consider $G(\alpha_{1},\alpha_{2},1)$
with $\alpha_{1}\geq 4$ and $\alpha_{2}\geq 2$. By Theorem 4.2, we have that
$\gamma(G(4,2,1))=2$, and so, $G(4,2,1)$ does not $2$-cell embed in the torus.
Thus, the same conclusion holds for any such $G(\alpha_{1},\alpha_{2},1)$ with
$\alpha_{1}\geq 4$ and $\alpha_{2}\geq 2$.

For $k=4$, $G(1,1,1,1)$ is isomorphic to the four dimensional hypercube
$Q_{4}$, which $2$-cell embeds on the torus by Corollary 5. Any other grid
graph in this case contains a subgraph isomorophic to $G(2,1,1,1)$, which does
not $2$-cell embed on the torus by Corollary 1. Thus, the same conclusion
holds for any $4$-dimensional grid graph left in this case.

For $k\geq 5$, every such grid graph contains a subgraph isomorphic to
$G(1,1,1,1,1)$. However, Corollary 1 implies that $G(1,1,1,1,1)$ does not
$2$-cell embed in the torus, and so, the same holds for all other grid graphs
of dimension $k\geq 5$. ∎

We note that there are only trivial examples of grid graphs that embed on the
torus but do not $2$-cell embed on the torus, specifically, any
$G(\alpha_{1},\ldots,\alpha_{k})$ with $k\leq 2$ will meet these
qualifications.

Using the tools we developed in Section 2 along with White’s work Wh1970 , one
could possibly continue to classify which grid graphs minimally embed on a
fixed surface of genus $g\in\mathbb{N}$. In the remainder of this section, we
just show that the set of grid graphs that minimally embed on a fixed surface
$S_{g}$ is always finite for $g>0$.

Define $\mathscr{C}_{g}$ as the set of grid graphs that embed on $S_{g}$ but
not on $S_{g-1}$. Proposition 4 gives a complete description of
$\mathscr{C}_{0}$ and one could easily use Theorem 6.1 to give a complete
description of $\mathscr{C}_{1}$. The following theorem and its proof provide
some evidence for how $\mathscr{C}_{g}$ behaves more generally.

######  Theorem 6.2.

The set $\mathscr{C}_{g}$ is finite if and only if $g\neq 0$. Equivalently,
the collection of grid graphs that minimally embed on any closed orientable
surface with genus $g$ is infinite, if and only if $g=0$.

###### Proof.

Since any graph contained in $\mathscr{C}_{g}$ corresponds with a minimal
embedding, we don’t distinguish between embeddings and $2$-cell embeddings in
this proof. We can easily see that $\mathscr{C}_{0}$ is infinite since for
$k=1,2$, every $k$-dimensional grid graph embeds in the plane.

Now, suppose there exists $g_{0}\in\mathbb{N}$ such that
$|\mathscr{C}_{g_{0}}|=\infty$, say
$\mathscr{C}_{g_{0}}=\\{G_{i}\\}_{i=1}^{\infty}$, where each $G_{i}$ is a grid
graph with genus $\gamma(G_{i})=g_{0}$. Then $\\{G_{i}\\}_{i=1}^{\infty}$
contains a subsequence $\\{G_{i_{j}}\\}$ where

  1. 1.

the dimension of $G_{i_{j}}$ strictly increase to $\infty$ as
$j\rightarrow\infty$ or,

  2. 2.

there are infinitely many $G_{i_{j}}$ with the same dimension.

We will now show that both cases are impossible, giving the desired
contradiction.

For (1), let $\\{G_{k}\\}$ be such a subsequence, where each $k$ designates
the dimension of the corresponding grid graph. So, $k\rightarrow\infty$ by
assumption. Note that, we can assume $k\geq 3$ here since any $k$-dimensional
grid graph with $k\leq 2$ is planar. Now, each $G_{k}$ contains a subgraph
isomorphic to $G(1,\ldots,1)$ with $k$ ones and Corollary 5 implies that

$\gamma(G_{k})\geq\gamma(G(1,\ldots,1))=1+(k-4)2^{k-3}.$

Set $f(k)=1+(k-4)2^{k-3}$. Since
$\displaystyle\lim_{k\rightarrow\infty}f(k)=\infty$, there exists some
$k^{\prime}$ such that $g_{0}\leq f(k)$ for all $k\geq k^{\prime}$. This
implies that any $k$-dimensional grid graph could not embed on $S_{g_{0}}$ for
$k\geq k^{\prime}$. This completes case (1).

For (2), suppose we have a sequence of $k$-dimensional grid graphs,
$\\{G(\alpha_{j_{1}},\ldots,\alpha_{j_{k}})\\}_{j=1}^{\infty}$ for some fixed
$k\geq 3$. Then this sequence contains a subsequence where one of the
$\alpha_{j_{m}}$ parameters heads to infinity as $j\rightarrow\infty$. Without
loss of generality, assume this parameter is $\alpha_{j_{1}}$. Then each grid
graph in this further subsequence contains a subgraph isomorphic to the
$k$-dimensional grid graph $G(\alpha_{j_{1}})=G(\alpha_{j_{1}},1,\ldots,1)$.
Then Corollary 1 implies that

$\displaystyle\gamma(G(\alpha))$ $\displaystyle\geq
1-(\alpha+1)2^{k-2}\Big{[}1-\frac{1}{2}(\frac{\alpha}{\alpha+1}+\frac{k-1}{2})\Big{]}$
$\displaystyle=1-2^{k-2}\Big{[}\alpha+1-\frac{1}{2}(\alpha+\frac{(\alpha+1)(k-1)}{2})\Big{]}$
$\displaystyle=1-2^{k-2}\Big{[}\frac{3}{4}\alpha+\frac{5}{4}-\frac{k}{4}(\alpha-1)\Big{]}$
$\displaystyle=1+2^{k-2}\Big{[}(\frac{k-3}{4})\alpha-\frac{5+k}{4}\Big{]}.$

Now, for any fixed $k>3$, let
$h(\alpha_{j_{1}})=1+2^{k-2}\Big{[}(\frac{k-3}{4})\alpha_{j_{1}}-\frac{5+k}{4}\Big{]}.$
Then we have that
$\displaystyle\lim_{j\rightarrow\infty}h(\alpha_{j_{1}})=\infty$, implying
that (2) can not hold when the dimension is $k>3$ following the same line of
argument as case (1). Finally, for $k=3$, since Lemma 5 implies that
$G(\alpha,1,1)$ is planar, we can conclude that any $3$-dimensional grid graph
in this sequence must contain a subgraph isomorphic to $G(\alpha,2,1)$.
However, Lemma 4 tells us that
$\gamma(G(\alpha,2,1))\geq\left\lfloor\frac{\alpha}{2}\right\rfloor$. Since
$\displaystyle\lim_{j\rightarrow\infty}\left\lfloor\frac{\alpha_{j_{1}}}{2}\right\rfloor=\infty$,
we can again apply the same type of argument used in case (1). Thus, such a
sequence is also impossible when $k=3$. ∎

###### Acknowledgements.

We would like to thank Mark Ellingham and the referee for providing useful
feedback on drafts of this paper.

## Funding

This work was financially supported by the Furman University Department of
Mathematics via the Summer Mathematics Undergraduate Research Fellowships.

## Availability of data and materials

Not applicable.

## Conflict of Interests

The authors have no relevant financial or non-financial interests to disclose.

## References

  * (1) Mohammed Abu-Sbeih and T. D. Parsons, _Embeddings of bipartite graphs_ , J. Graph Theory 7 (1983), no. 3, 325–334.
  * (2) Ian Anderson, _Quadrilateral embeddings of bipartite graphs_ , J. Graph Theory 5 (1981), no. 4, 355–361.
  * (3) Joseph Battle, Frank Harary, Yukihiro Kodama, and J. W. T. Youngs, _Additivity of the genus of a graph_ , Bull. Amer. Math. Soc. 68 (1962), 565–568.
  * (4) Lowell W. Beineke and Frank Harary, _The genus of the $n$-cube_, Canadian J. Math. 17 (1965), 494–496.
  * (5) André Bouchet, _Orientable and nonorientable genus of the complete bipartite graph_ , J. Combin. Theory Ser. B 24 (1978), no. 1, 24–33.
  * (6) Shouman Das, _Genus of the hypercube graph and real moment-angle complexes_ , Topology Appl. 258 (2019), 415–424.
  * (7) Richard A. Duke, _The genus, regional number, and Betti number of a graph_ , Canadian J. Math. 18 (1966), 817–822.
  * (8) Wilfried Imrich, Sandi Klavžar, and Douglas F. Rall, _Topics in graph theory_ , A K Peters, Ltd., Wellesley, MA, 2008, Graphs and their Cartesian product.
  * (9) Bojan Mohar, Tomaž Pisanski, and Martin Škoviera, _The maximum genus of graph bundles_ , European J. Combin. 9 (1988), no. 3, 215–224.
  * (10) Tomaž Pisanski, _Genus of Cartesian products of regular bipartite graphs_ , J. Graph Theory 4 (1980), no. 1, 31–42.
  * (11) , _Nonorientable genus of Cartesian products of regular graphs_ , J. Graph Theory 6 (1982), no. 4, 391–402.
  * (12) , _Orientable quadrilateral embeddings of products of graphs_ , vol. 109, 1992, Algebraic graph theory (Leibnitz, 1989), pp. 203–205.
  * (13) Gerhard Ringel, _Über drei kombinatorische Probleme am $n$-dimensionalen Würfel und Würfelgitter_, Abh. Math. Sem. Univ. Hamburg 20 (1955), 10–19.
  * (14) , _Das Geschlecht des vollständigen paaren Graphen_ , Abh. Math. Sem. Univ. Hamburg 28 (1965), 139–150.
  * (15) Arthur T. White, _The genus of repeated cartesian products of bipartite graphs_ , Trans. Amer. Math. Soc. 151 (1970), 393–404.
  * (16) J. W. T. Youngs, _Minimal imbeddings and the genus of a graph_ , J. Math. Mech. 12 (1963), 303–315.
  * (17) Joseph Zaks, _The maximum genus of Cartesian products of graphs_ , Canadian J. Math. 26 (1974), 1025–1035.