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.

graph	dimension
complete bipartite graph
complete graph
cycle graph	2
empty graph
generalized Petersen graph	2
grid graph
hypercube graph
path graph
star graph
wheel graph

---

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.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength