I was thinking, that has a name, that has a name, and mathoverflow knew it, it was on the related column on the right. The invariant often called the bandwidth of a graph. As Professor Rivin already mentioned it is NP-complete to compute it.
 There is however a pretty $(log n)^c$-approximation algorithm by Fiege, he generalizes Bourgain's embedding theorem and the London-Linial-Rabonovich approximation of the sparsets cut, by first generalizing bilipschitz distortion to something he calls "volume preserving embeddings". It is informally explained in chapter 15 of Matousek's "Lectures on Discrete Geometry", that is available online.