Grid graph

from Wikipedia, the free encyclopedia
A grid graph with 11 × 11 nodes

A grid graph is a planar graph that can be drawn in the plane in such a way that all of its nodes lie on integer points in a Cartesian coordinate system and all edges have length 1. Each grid graph is a unit distance graph .

Mostly grid graphs are considered, the drawing of which forms a rectangular grid. These can be written as

This clearly means that the set of nodes contains the points with the integer coordinates from to on one axis and from to on the other axis of a right-angled coordinate system. Two nodes and are connected by an edge if and only if they have a distance of 1.

The grid graph consists of exactly four nodes and four edges and is isomorphic to the circular graph . The grid graphs of the form are called ladder graphs .

Individual evidence

  1. Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke: Exact algorithms for difficult graph problems . Springer, September 28, 2010, ISBN 9783642044991 , p. 32.