On the Euclidean dimension of graphs

The Euclidean dimension a graph $G$ is defined to be the smallest integer $d$ such that the vertices of $G$ can be located in $\mathbb{R}^d$ in such a way that two vertices are unit distance apart if and only if they are adjacent in $G$. In this paper we determine the Euclidean dimension for twelve well known graphs. Five of these graphs, Dürer, Franklin, Desargues, Heawood and Tietze can be embedded in the plane, while the remaining graphs, Chvátal, Goldner-Harrary, Herschel, Fritsch, Grötzsch, Hoffman and Soifer have Euclidean dimension $3$. We also present explicit embeddings for all these graphs.

No reviews yet.

No comments yet.