![]() | ||
In mathematics, and particularly in graph theory, the dimension of a graph is the least integer n such that there exists a "classical representation" of the graph in the Euclidean space of dimension n with all the edges having unit length.
Contents
- Complete graph
- Complete bipartite graphs
- Euclidean dimension
- Euclidean dimension and maximal degree
- Computational complexity
- References
In a classical representation, the vertices must be distinct points, but the edges may cross one another.
The dimension of a graph G is written:
For example, the Petersen graph can be drawn with unit edges in
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.
Complete graph
In the worst case, every pair of vertices is connected, giving a complete graph.
To immerse the complete graph
In other words, the dimension of the complete graph is the same as that of the simplex having the same number of vertices.
Complete bipartite graphs
All star graphs
The dimension of a complete bipartite graph
To summarise:
Euclidean dimension
The definition of the dimension of a graph given above says, of the minimal-n representation:
This definition is rejected by some authors. A different definition was proposed in 1991 by Alexander Soifer, for what he termed the Euclidean dimension of a graph. Previously, in 1980, Paul Erdős and Miklós Simonovits had already proposed it with the name faithful dimension. By this definition, the minimal-n representation is one such that two vertices of the graph are connected if and only if their representations are at distance 1.
The figures opposite show the difference between these definitions, in the case of a wheel graph having a central vertex and six peripheral vertices, with one spoke removed. Its representation in the plane allows two vertices at distance 1, but they are not connected.
We write this dimension as
Euclidean dimension and maximal degree
Paul Erdős and Miklós Simonovits proved the following result in 1980:
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.