TOPICS

# Graph Dimension

The dimension , also called the Euclidean dimension (e.g., Buckley and Harary 1988) of a graph, is the smallest dimension of Euclidean -space in which can be embedded with every edge length equal to 1 and every vertex position distinct (but where edges may cross or overlap and points may lie on edges that are not incident on them; Erdős et al. 1965).

Any connected graph with maximum vertex degree has graph dimension at most , with the exception of the utility graph (Frankl et al. 2018). Furthermore, any graph with chromatic number has graph dimension at most . This can be seen by partitioning the space into orthogonal two-dimensional planes, then in each plane placing the vertices with one color on a circle with radius centred on the plane's origin (so all points have a squared norm of 1/2) (J. Tan, pers. comm., Oct. 26, 2021).

For any nonempty graph , the graph Cartesian product satisfies

 (1)

(Erdős et al. 1965, Buckley and Harary 1988). While the theorem is stated as holding for "any" graph by both references, if is taken as the empty graph , then is isomorphic to the ladder rung graph . Yet for (since vertices may not overlap by the definition of graph dimension) and since each of the paths can be placed on a 1-dimensional line.

The singleton graph has graph dimension , the path graphs for have graph dimension , and in general, any graph with dimension 2 or less is said to be a unit-distance graph.

The dimension of the complete graph is (Erdős et al. 1965, Buckley and Harary 1988). For the complete bipartite graph with ,

 (2)

(Erdős et al. 1965, Buckley and Harary 1988).

The dimension of is given by for (Erdős et al. 1965).

The hypercube graph has dimension for (Erdős et al. 1965).

The wheel graph has graph dimension 2 for (and hence is unit-distance) and dimension 3 otherwise (and hence is not unit-distance) (Erdős et al. 1965, Buckley and Harary 1988).

The following table summarizes the graph dimensions for various families of parametrized graphs.

Metric Dimension, Unit-Distance Graph

## Explore with Wolfram|Alpha

More things to try:

## References

Buckley, F. and Harary, F. "On the Euclidean Dimension of a Wheel." Graphs and Combin. 4, 23-30, 1988.Erdős, P.; Harary, F.; and Tutte, W. T. "On the Dimension of a Graph." Mathematika 12, 118-122, 1965.Frankl, N.; Kupavskii, A.; Swanepoel, K. J. "Embedding Graphs in Euclidean Space." 12 Feb 2018. https://arxiv.org/abs/1802.03092.

## Cite this as:

Weisstein, Eric W. "Graph Dimension." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraphDimension.html