Ingraph theory, alattice graph,mesh graph, orgrid graph is agraph whosedrawing,embedded in someEuclidean space⁠${\displaystyle {\mathbb{R}}^n}$⁠, forms aregular tiling. This implies that thegroup ofbijective transformations that send the graph to itself is alattice in the group-theoretical sense.

Typically, no clear distinction is made between such a graph in the more abstract sense of graph theory, and its drawing in space (often the plane or 3D space). This type of graph may more shortly be called just alattice,mesh, orgrid. Moreover, these terms are also commonly used for a finite section of the infinite graph, as in "an 8 × 8 square grid".

The termlattice graph has also been given in the literature to various other kinds of graphs with some regular structure, such as theCartesian product of a number ofcomplete graphs.^[1]

A common type of lattice graph (known under different names, such asgrid graph orsquare grid graph) is the graph whose vertices correspond to the points in the plane withinteger coordinates,x-coordinates being in the range1, ..., n,y-coordinates being in the range1, ..., m, and two vertices being connected by an edge whenever the corresponding points are at distance 1. In other words, it is theunit distance graph for the integer points in a rectangle with sides parallel to the axes.^[2]

A square grid graph is aCartesian product of graphs, namely, of twopath graphs withn − 1 andm − 1 edges.^[2] Since a path graph is amedian graph, the latter fact implies that the square grid graph is also a median graph. All square grid graphs arebipartite, which is easily verified by the fact that one can color the vertices in a checkerboard fashion.

A path graph is a grid graph on the${\displaystyle 1\times n}$  grid. A${\displaystyle 2\times 2}$  grid graph is a4-cycle.^[2]

Everyplanar graphH is aminor of theh × h grid, where${\displaystyle h=2|V(H)|+4|E(H)|}$ .^[3]

Grid graphs are fundamental objects in the theory of graph minors because of thegrid exclusion theorem. They play a major role inbidimensionality theory.

Atriangular grid graph is a graph that corresponds to a triangular grid.

AHanan grid graph for a finite set of points in the plane is produced by the grid obtained by intersections of all vertical and horizontal lines through each point of the set.

Therook's graph (the graph that represents all legal moves of therookchess piece on achessboard) is also sometimes called thelattice graph, although this graph is different from the lattice graph described here because all points in one row or column are adjacent. The valid moves of thefairy chess piece thewazir form a square lattice graph.

• Lattice path
• Pick's theorem
• Integer triangles in a 2D lattice
• Regular graph