Dimension (graph theory)

is 2.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 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.

is 2. In mathematics, and particularly in graph theory, the dimension of a graph is the least integer such that there exists a "classical representation" of the graph in the Euclidean space of dimension with all the edges having unit length. In a classical representation, the vertices must be distinct points, but the edges may cross one another.

The dimension of a graph is written \dim G . For example, the Petersen graph can be drawn with unit edges in E^2 , but not in E^1 : its dimension is therefore 2 (see the figure to the right). This concept was introduced in 1965 by Paul Erdős, Frank Harary and William Tutte.

It generalises the concept of unit distance graph to more than 2 dimensions. \dim K_n = n-1 In other words, the dimension of the complete graph is the same as that of the simplex having the same number of vertices. \dim K_{m,n} = 1, 2, 3 \text{ or } 4 , depending on the values of and . We write for the chromatic number of , and assign the integers (1..n) to the colours.

In 2n -dimensional Euclidean space, with its dimensions denoted x_1, x_2, .. x_{2n} , we arrange all the vertices of colour arbitrarily on the circle given by x_{2n-2}^2+x_{2n-1}^2=1/2,\quad x_i|(i\neq 2{n-2}, i\neq 2{n-1}) = 0 . Then the distance from a vertex of colour to a vertex of colour is given by {\sqrt{x_{2p-2}^2+x_{2p-1}^2+x_{2q-2}^2+x_{2q-1}^2}} = {\sqrt{1/2+1/2}} = 1 .

Computational complexity

It is NP-hard, and more specifically complete for the existential theory of the reals, to test whether the dimension or the Euclidean dimension of a given graph is at most a given value. The problem remains hard even for testing whether the dimension or Euclidean dimension is two.

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

Sources cited in this revision

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