A grid graph in two dimensions, for positive integers 
and 
, also known as a rectangular grid graph or two-dimensional
lattice graph (e.g., Acharya and Gill 1981), is an 
lattice
graph that is the graph Cartesian product 
of path
graphs on 
and 
vertices.
The 
grid graph is sometimes denoted
(e.g., Acharya and Gill 1981).
The particular case of an 
rectangular grid graph is sometimes known as a square grid graph. By analogy with
the KC graph and KP graph,
the 
grid graph could also be called
a "PP graph."
Unfortunately, the convention concerning which index corresponds to width and which to height remains murky. Some authors (e.g., Acharya and Gill 1981) use the same
height by width convention applied to matrix dimensioning
(which also corresponds to the order in which measurements of a painting on canvas
are expressed). The Wolfram Language
implementation GridGraph[
m, n, ...
] also adopts this ordering, returning an embedding
in which 
corresponds to the height and 
the width. Other sources adopt the "width by height"
convention used to measure paper, room dimensions, and windows (e.g., 8 1/2 inch
by 11 inch paper is 8 1/2 inches wide and 11 inches high). Therefore, depending on
convention, the graph illustrated above may be referred
to either as the 
grid graph or the 
grid graph.
Yet another convention wrinkle is used by Harary (1994, p. 194), who does not explicitly state which index corresponds to which dimension, but uses a 0-offset
numbering in defining a 2-lattice as a graph whose points
are ordered pairs of integers 
with 
, 1, ..., 
and 
,
1, ..., 
.
If Harary's ordered pairs are interpreted as Cartesian
coordinates, a grid graph with parameters 
and 
consists of 
vertices along the 
-axis and 
along the 
-axis. This is consistent with the interpretation of 
in the graph
Cartesian product as paths with 
and 
edges (and hence 
and 
vertices), respectively.
The convention that 
is a grid graph made of the graph Cartesian
product of paths of length 
, 
, ... is also used by Millichap and Salinas (2022).
Note that Brouwer et al. (1989, p. 440) use the term "
grid" to refer to the line
graph 
of the complete bipartite graph 
, known in this work as the rook
graph 
.
Precomputed properties for a number of grid graphs are available using GraphData[
"Grid", 
m, ..., r, ...
].
A grid graph 
has 
vertices
and 
edges.
For 
, a grid graph 
is Hamiltonian
if either the number of rows or columns is even (Skiena
1990, p. 148). Grid graphs are also bipartite
(Skiena 1990, p. 148). 
and 
grid graphs are graceful
(Acharya and Gill 1981, Gallian 2025).
Every finite rectangular 
-dimensional
grid graph with positive side lengths is traceable.
A Hamiltonian path can be constructed inductively
by traversing consecutive layers alternately along a Hamiltonian
path of the lower-dimensional grid and its reverse, joining corresponding endpoints
in adjacent layers.
The numbers of directed Hamiltonian paths on the 
grid graph for 
, 2, ... are given by 1, 8, 40, 552, 8648, 458696, 27070560,
... (OEIS A096969). In general, the numbers
of Hamiltonian paths on the 
grid graph for fixed 
are given by a linear
recurrence equation.
The numbers of directed Hamiltonian cycles on the 
grid graph for 
, 2, ... are 0, 2, 0, 12, 0, 2144, 0, 9277152, ... (OEIS
A143246). In general, the numbers of Hamiltonian
cycles on the 
grid graph for fixed 
are given by a linear recurrence equation.
The numbers of (undirected) graph cycles on the 
grid graph for 
, 2, ... are 0, 1, 13, 213, 9349, 1222363, ... (OEIS A140517,
indexed there by 
).
In general the number 
of 
-cycles
on the 
grid graph is given by 
for 
odd and
eventually by a quadratic polynomial in 
for each fixed even 
, with the first few being
 |  |  |
(1)
|
 |  |  |
(2)
|
 |  |  |
(3)
|
 |  | ![{0 for n<4; 4[7(n-3)^2+7(n-3)-1] otherwise](/images/equations/GridGraph/Inline81.svg) |
(4)
|
 |  |  |
(5)
|
 |  |  |
(6)
|
 |  |  |
(7)
|
(E. Weisstein, Nov. 16, 2014).
The domination number of 
is given by
 |
(8)
|
for 
, as conjectured by Chang
(1992), confirmed up to an additive constant by Guichard (2004), and proved by Gonçalves
et al. (2011). Gonçalves et al. (2011) give a piecewise formula
for 
, but the expression given for
width 
is not correct in all cases. A correct
formula for 
attributed to Hare appears as formula (6) in Chang and Clark (1993), which however
then proceeds to give an incorrect reformulation as formula (14).
Mertens (2024) computed the domination polynomial and numbers of dominating sets for 
grid graphs up to 
.
For 
, Huang (2026) completely characterized
and enumerated the minimal resolving sets
of 
. Their possible cardinalities
are 2, 3, and every even integer
from 4 through 
.
Huang also gave a recursive construction for all such sets of cardinality
at least 4 and closed enumeration formulas for every
possible cardinality.
A generalized grid graph, also known as an 
-dimensional lattice graph (e.g.,
Acharya and Gill 1981) can also be defined as the graph
Cartesian product 
(e.g., Harary 1967, p. 28; Acharya and Gill 1981). Such graphs
are sometimes denoted 
or 
(e.g., Acharya and Gill
1981). A generalized grid graph has chromatic number
2, except the degenerate case of the singleton graph,
which has chromatic number 1. Special cases are
illustrated above and summarized in the table below.
| grid graph | special case |
 | path graph  |
 | ladder
graph  |
 | square graph  |
 | domino graph |
 | cubical
graph  |
 | hypercube graph  |
For a grid graph 
with 
, factors of graph
order one may be omitted without changing the graph
up to graph isomorphism. Such a grid graph is
highly irregular iff
it is the singleton graph or a path
graph 
or 
, and is self-complementary iff it is the singleton graph
or the path graph 
.
The vertex degree in a graph Cartesian product is the sum of the degrees in its factors. A grid graph is therefore regular iff each factor has graph order at most two. In that case it is a hypercube graph and hence vertex-transitive. Consequently, no grid graph is semisymmetric.
is graceful
(Liu et al. 2012, Gallian 2025).
The partial-grid recognition problem asks whether a graph admits an injective map of its vertices into 
that maps every graph
edge to a pair at Euclidean distance 1.
Nonadjacent vertices may also be mapped to points
at distance 1, so this does not require an induced
subgraph. For fixed 
,
Binnendyk (2026) gave an algorithm taking 
time on a graph
with 
vertices.
Under the exponential time hypothesis,
the required time is 
in dimension two and 
in dimension three. Here 
and 
denote big-O
notation and big-omega notation. Binnendyk
(2026) reports AI assistance in finding and correcting errors in the cut-edge placement
function and a satisfiability reduction proof.
." 27 Oct 2026. 
and 
Grid Graphs." J. Graph
Th. 17, 81-107, 1993.Faase, F. "On the Number of Specific
Spanning Subgraphs of the Graphs 
." Ars Combin. 49, 129-154, 1998.Gallian,
J. "Dynamic Survey of Graph Labeling." Elec. J. Combin., Dynamic
Survey DS6, Oct. 30, 2025. 
-Dimensional Rectangular Lattices Are Hamilton-Laceable."
In Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory,
and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978) (Ed. F. Hoffman,
D. McCarthy, R. C. Mullin, and R. G. Stanton). Winnipeg,
Manitoba: Utilitas Mathematica Publishing, pp. 649-661, 1978.Skiena,
S. "Grid Graphs." §4.2.4 in