Lattice graph

A lattice graph, mesh graph, or grid graph, is a graph whose drawing, embedded in some Euclidean space Rn, forms a regular tiling. This implies that the group of bijective transformations that send the graph to itself is a lattice 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 a lattice, mesh, or grid. Moreover, these terms are also commonly used for a finite section of the infinite graph, as in "an 8×8 square grid".

The term lattice graph has also been given in the literature to various other kinds of graphs with some regular structure, such as the Cartesian product of a number of complete graphs.[1]

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 1,..., 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 for the described point set.[2]

Properties

A square grid graph is a Cartesian product of graphs, namely, of two path graphs with n - 1 and m - 1 edges.[2] Since a path graph is a median graph, the latter fact implies that the square grid graph is also a median graph. All grid graphs are bipartite, which is easily verified by the fact that one can color the vertices in a checkerboard fashion.

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.[2]

Every planar graph H is a minor of the h×h-grid, where h = 2|V(H)| + 4|E(H)|.[3]

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.

See also

References

  1. ↑ Weisstein, Eric W. "Lattice graph". MathWorld.
  2. 1 2 3 Weisstein, Eric W. "Grid graph". MathWorld.
  3. ↑ 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.
This article is issued from Wikipedia - version of the 4/15/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.