In graph theory, a lattice graph, also known as a mesh or grid graph, is a graph whose embedding in Euclidean space forms a regular tiling. The group of bijective transformations mapping the graph onto itself is a lattice in the group-theoretical sense. Typically, the terms lattice, mesh, or grid are used interchangeably for both infinite graphs and finite sections, such as an “8 × 8 square grid.” The term lattice graph is also applied to other regularly structured graphs, including the Cartesian product of several complete graphs.
Square grid graph
A common type of lattice graph (known under different names, such as grid graph or square grid graph) is the graph whose vertices correspond to the points in the plane with integer coordinates, x-coordinates being in the range 1, ..., n, y-coordinates being in the range 1, ..., m, and two vertices being connected by an edge whenever the corresponding points are at distance one. In other words, it is the unit distance graph for the integer points in a rectangle with sides parallel to the axes.2
Properties
A square grid graph is a Cartesian product of graphs, namely, of two path graphs with n − 1 and m − 1 edges.3 Since a path graph is a median graph, the latter fact implies that the square grid graph is also a median graph. All square grid graphs are bipartite, 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 1 × n {\displaystyle 1\times n} grid. A 2 × 2 {\displaystyle 2\times 2} grid graph is a 4-cycle.4
Every planar graph H is a minor of the h × h grid, where h = 2 | V ( H ) | + 4 | E ( H ) | {\displaystyle h=2|V(H)|+4|E(H)|} .5
Grid graphs are fundamental objects in the theory of graph minors because of the grid exclusion theorem. They play a major role in bidimensionality theory.
Other kinds
A triangular grid graph is a graph that corresponds to a triangular grid.
A Hanan 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.
The rook's graph (the graph that represents all legal moves of the rook chess piece on a chessboard) is also sometimes called the lattice 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 the fairy chess piece the wazir form a square lattice graph.
See also
References
Weisstein, Eric W. "Lattice graph". MathWorld. /wiki/Eric_W._Weisstein ↩
Weisstein, Eric W. "Grid graph". MathWorld. /wiki/Eric_W._Weisstein ↩
Weisstein, Eric W. "Grid graph". MathWorld. /wiki/Eric_W._Weisstein ↩
Weisstein, Eric W. "Grid graph". MathWorld. /wiki/Eric_W._Weisstein ↩
Robertson, N.; Seymour, P.; Thomas, R. (November 1994). "Quickly Excluding a Planar Graph". Journal of Combinatorial Theory, Series B. 62 (2): 323–348. doi:10.1006/jctb.1994.1073. https://doi.org/10.1006%2Fjctb.1994.1073 ↩