King's graph

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an n \times m king's graph is a king's graph of an n \times m chessboard. It is the map graph formed from the squares of a chessboard by making a vertex for each square and an edge for each two squares that share an edge or a corner. It can also be constructed as the strong product of two path graphs.

For an n \times m king's graph the total number of vertices is n m and the number of edges is 4nm -3(n + m) + 2 . For a square n \times n king's graph this simplifies so that the total number of vertices is n^2 and the total number of edges is (2n-2)(2n-1) . The neighbourhood of a vertex in the king's graph corresponds to the Moore neighborhood for cellular automata.

A generalization of the king's graph, called a kinggraph, is formed from a squaregraph (a planar graph in which each bounded face is a quadrilateral and each interior vertex has at least four neighbors) by adding the two diagonals of every quadrilateral face of the squaregraph.…

In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an n \times m king's graph is a king's graph of an n \times m chessboard. It is the map graph formed from the squares of a chessboard by making a vertex for each square and an edge for each two squares that share an edge or a corner. It can also be constructed as the strong product of two path graphs.

For an n \times m king's graph the total number of vertices is n m and the number of edges is 4nm -3(n + m) + 2 . For a square n \times n king's graph this simplifies so that the total number of vertices is n^2 and the total number of edges is (2n-2)(2n-1) . The neighbourhood of a vertex in the king's graph corresponds to the Moore neighborhood for cellular automata.

A generalization of the king's graph, called a kinggraph, is formed from a squaregraph (a planar graph in which each bounded face is a quadrilateral and each interior vertex has at least four neighbors) by adding the two diagonals of every quadrilateral face of the squaregraph.

In the drawing of a king's graph obtained from an n\times m chessboard, there are (n-1)(m-1) crossings, but it is possible to obtain a drawing with fewer crossings by connecting the two nearest neighbors of each corner square by a curve outside the chessboard instead of by a diagonal line segment. In this way, (n-1)(m-1)-4 crossings are always possible. For the king's graph of small chessboards, other drawings lead to even fewer crossings; in particular every 2\times n king's graph is a planar graph.

However, when both n and m are at least four, and they are not both equal to four, (n-1)(m-1)-4 is the optimal number of crossings.

See also

Knight's graph Queen's graph Rook's graph Bishop's graph Lattice graph

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1369245674 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001369245674 · captured 1786643536.0 · version history

Cite this page as: encyclopegia.org, “King's graph”, snapshot enwiki-001369245674. https://encyclopegia.org/a/king-s-graph

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.