I just ran across this delightful paper by an amazing triumvirate:

Paul Erdős, Frank Harary, and William Tutte. "On the dimension of a graph."

Mathematika12.118-122 (1965): 20. (Cambridge link) (PDF download link)

They prove that $K_n$ has dimension $n-1$, $K_{n,n}$ has dimension $\le 4$,
and the dimension of the $n$-cube $Q_n$ is $2$. And the Petersen graph has dimension $2$:

Surely there must have been advances on characterizing graphs according to this concept in the last ~half-century(!). Can anyone provide some updates the status on this notion?

**Update**. Here is a modern, metrically accurate drawing of the Petersen graph:

_{(Image from Wikipedia: Unit Distance Graph)}

$d$-realizability: If a graph $G$ has some realization in $\mathbb{R}^k$, there is a realization in $\mathbb{R}^d$ with the same edge lengths. E.g., paths and trees are 1-realizable but triangles are not. $\endgroup$ – Joseph O'Rourke Aug 31 '13 at 0:31