Content deleted Content added
→Square grid graph: The proper name was defined as "square grid graph" without mentioning that such graphs will be called simply "grid graphs". Grid graphs are not necessarily bipartite as illustrated by the provided figure with the triangular grid graph. |
m →See also: [-lk] |
||
| (One intermediate revision by one other user not shown) | |||
Line 18:
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 27 ⟶ 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==
| |||