The terms lattice graph, mesh graph, or grid graph refer to a number of categories of graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

s whose drawing

Graph drawing

Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...

 corresponds to some grid/mesh/lattice, i.e., its vertices correspond to the nodes of the mesh and its edges correspond to the ties between the nodes.

Square grid graph

A common type of a lattice graph (known under different names, such as square grid graph) is the graph whose vertices correspond to the points in the plane with integer coordinates, x-coordinates being in the range 0,..., n, y-coordinates being in the range 1,...m, and two vertices are connected by an edge whenever the corresponding points are at distance 1. In other words, it is a unit distance graph

Unit distance graph

In mathematics, and particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points by an edge whenever the distance between the two points is exactly one...

 for the described point set.

Properties

A square grid graph is a Cartesian product of graphs

Cartesian product of graphs

In graph theory, the Cartesian product G \square H of graphs G and H is a graph such that* the vertex set of G \square H is the Cartesian product V × V; and...

, namely, of two path graph

Path graph

In the mathematical field of graph theory, a path graph or linear graph is a particularly simple example of a tree, namely a tree with two or more vertices that is not branched at all, that is, contains only vertices of degree 2 and 1...

s with n and m edges. Since a path graph is a median graph

Median graph

In mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m that belongs to shortest paths between any two of a, b, and c.The concept of median graphs has long been studied, for instance by or ...

, the latter fact implies that the square grid graph is also a median graph. All grid graphs are bipartite

Bipartite graph

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...

.

A path graph may also be considered to be a grid graph on the grid n times 1. A 2x2 grid graph is a 4-cycle

Cycle graph

In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...

.

Other kinds

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

A Hanan grid

Hanan grid

In geometry, the Hanan grid H of a finite set S of points in the plane is obtained by constructing vertical and horizontal lines through each point in S....

 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

Rook's graph

In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard: each vertex represents a square on a chessboard and each edge represents a legal move...

 (the graph that represents all legal moves of the rook

Rook (chess)

A rook is a piece in the strategy board game of chess. Formerly the piece was called the castle, tower, marquess, rector, and comes...

 chess

Chess

Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...

 piece

Chess piece

Chess pieces or chessmen are the pieces deployed on a chessboard to play the game of chess. The pieces vary in abilities, giving them different values in the game...

 on a chessboard

Chessboard

A chessboard is the type of checkerboard used in the board game chess, and consists of 64 squares arranged in two alternating colors...

) is also sometimes called the lattice graph.