HOME

TheInfoList



OR:

In graph theory, a lattice graph, mesh graph, or grid graph is a
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discr ...
whose
drawing Drawing is a form of visual art in which an artist uses instruments to mark paper or other two-dimensional surface. Drawing instruments include graphite pencils, pen and ink, various kinds of paints, inked brushes, colored pencils, crayo ...
, embedded in some
Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean ...
, forms a
regular tiling Euclidean plane tilings by convex regular polygons have been widely used since antiquity. The first systematic mathematical treatment was that of Kepler in his ''Harmonices Mundi'' (Latin: ''The Harmony of the World'', 1619). Notation of Euc ...
. 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 In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\tim ...
of a number of
complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
s.


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 An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
coordinates, being in the range , being in the range , 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 In mathematics, 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 whenever the distance between them is exactly one. To distinguish these graph ...
for the described point set.


Properties

A square grid graph is a
Cartesian product of graphs Cartesian means of or relating to the French philosopher René Descartes—from his Latinized name ''Cartesius''. It may refer to: Mathematics * Cartesian closed category, a closed category in category theory *Cartesian coordinate system, moder ...
, namely, of two
path graph In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two terminal ...
s with ''n'' − 1 and ''m'' − 1 edges. Since a path graph is a
median graph In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices ''a'', ''b'', and ''c'' have a unique ''median'': a vertex ''m''(''a'',''b'',''c'') that belongs to shortest paths between each pair o ...
, 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 may also be considered to be a grid graph on the grid ''n'' times 1. A 2 × 2 grid graph is a 4-cycle. Every
planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...
''H'' is a minor of the ''h'' × ''h'' grid, where h = 2, V(H), + 4, E(H), .


Other kinds

A triangular grid graph is a graph that corresponds to a triangular grid. A
Hanan grid In geometry, the Hanan grid of a finite set of points in the plane In mathematics, a plane is a Euclidean ( flat), two-dimensional surface that extends indefinitely. A plane is the two-dimensional analogue of a point (zero dimensions), a ...
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 A chess piece, or chessman, is a game piece that is placed on a chessboard to play the game of chess. It can be either white or black, and it can be one of six types: king, queen, rook, bishop, knight, or pawn. Chess sets generally come wit ...
on a
chessboard A chessboard is a used to play chess. It consists of 64 squares, 8 rows by 8 columns, on which the chess pieces are placed. It is square in shape and uses two colours of squares, one light and one dark, in a chequered pattern. During play, the b ...
) is also sometimes called the lattice graph, although this graph is strictly different than the lattice graph described in this article. The valid moves of fairy chess piece wazir form the square lattice graph.


See also

*
Lattice path In combinatorics, a lattice path in the -dimensional integer lattice of length with steps in the set , is a sequence of vectors such that each consecutive difference v_i - v_ lies in . A lattice path may lie in any lattice in , but the int ...
*
Pick's theorem In geometry, Pick's theorem provides a formula for the area of a simple polygon with integer vertex coordinates, in terms of the number of integer points within it and on its boundary. The result was first described by Georg Alexander Pick in ...
* Integer triangles in a 2D lattice *
Lattice (order) A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum (also called a least upper bo ...
*
Regular graph In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegre ...


References

{{reflist Planar graphs Graph families