Graph ordering with smallest max vertex "discrepancy"
Your problem is known as BANDWIDTH. Another way to describe it is: we are given a matrix, and we want to rearrange the rows and columns (in the same way!) so that the only non-zero entries lie across a narrow band around the diagonal.

BANDWIDTH is known to be NP-complete. Unger showed that it is NP-hard to approximate to within any constant factor.
Feige gave an $\tilde{O}(\log^3 n)$-approximation algorithm which uses metric embeddings.

Among the many variants of BANDWIDTH, let me mention the MINIMAL LINEAR ARRANGEMENT problem (known by various other names), in which the goal is to minimize $\displaystyle\sum_{(u,v) \in E} |f(u)-f(v)|$ rather than $\displaystyle\max_{(u,v) \in E} |f(u)-f(v)|$.