Content deleted Content added
Joel Brennan (talk | contribs) m added wikilinks |
m →See also: [-lk] |
||
| (4 intermediate revisions by 4 users not shown) | |||
Line 1:
{{Short description|Graph whose embedding in a Euclidean space forms a regular tiling}}
[[File:Square grid graph.svg|thumb|Square grid graph]]▼
[[File:
A '''lattice graph''', '''mesh graph''', or '''grid graph''', is a [[Graph (discrete mathematics)|graph]] whose [[graph drawing|drawing]], [[Embedding|embedded]] in some [[Euclidean space]] '''R'''<sup>''n''</sup>, forms a [[regular tiling]]. This implies that the [[group (mathematics)|group]] of [[Bijection|bijective transformation]]s that send the graph to itself is a [[lattice (group)|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".▼
▲Typically, no clear distinction is made between such a graph in the more abstract sense of
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 graphs|Cartesian product]] of a number of [[complete graph]]s.<ref name= weiss-lg>{{mathworld|urlname=LatticeGraph|title=Lattice graph}}</ref>
Line 11 ⟶ 13:
===Properties===
A square grid graph is a [[Cartesian product of graphs]], namely, of two [[path graph]]s with ''n'' − 1 and ''m'' − 1 edges.<ref name= weiss-gg/> 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 graph|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 [[cycle graph|4-cycle]].<ref name= weiss-gg>{{mathworld|urlname=GridGraph|title=Grid graph}}</ref>
Every [[planar graph]] ''H'' is a [[graph minor|minor]] of the ''h'' × ''h'' grid, where <math>h = 2|V(H)| + 4|E(H)|</math>.<ref>{{cite journal|last1=Robertson|first1=N.|last2=Seymour|first2=P.|last3=Thomas|first3=R.|title=Quickly Excluding a Planar Graph|journal=Journal of Combinatorial Theory, Series B|date=November 1994|volume=62|issue=2|pages=323–348|doi=10.1006/jctb.1994.1073|doi-access=free}}</ref>
Grid graphs are fundamental objects in the theory of graph minors because of the [[Treewidth#Grid_minor_size|grid exclusion theorem]]. They play a major role in [[Bidimensionality|bidimensionality theory]].
==Other kinds==
Line 25 ⟶ 29:
The [[rook's graph]] (the graph that represents all legal moves of the [[Rook (chess)|rook]] [[chess piece]] on a [[chessboard]]) 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 (chess)|wazir]] form the square lattice graph.
== See also ==
* [[Lattice path]]
* [[Pick's theorem]]
* [[Integer triangle#Heronian triangles in a 2D lattice|Integer triangles in a 2D lattice]]
* [[
==References==
| |||