A traditional, important graph invariant similar to what you are asking about is the [genus of a graph](http://mathworld.wolfram.com/GraphGenus.html). 

I am aware that one *may* argue that this does not capture the intuition of 'dimension'. But then again, you yourself tagged this a 'soft-question', so this answer should be sort-of-acceptable to you. 

Also worth pointing out: as you will probably known, for any fixed dimension $d\geq 3$, *any countable graph can be embedded into $\mathbb{R}^d$*, a fact which by the way can be proved directly by induction (you do not need the usual argument via a Vandermonde matrix).