Consider an undirected graph $G=(V,E)$ and a bijective function $f:V \rightarrow [|V|]$ which orders the vertices by mapping them onto the first $|V|$ natural numbers.
Define the cost of an ordering of a graph to be:
$$\text{cost}(G,f) = \max_{(u,v) \in E} f(u)-f(v)$$
(I refer to $f(u) - f(v)$ in the title as "discrepancy" to avoid confusion with terms such as length or distance)
Intuitively, if we were to construct $G$ by adding on one vertex at a time and adding the appropriate edges to the already-existing vertices, the cost is how far back in our list of vertices we'd have to go and add edges to.
Question: How difficult is the problem of minimizing this cost? Is there an efficient algorithm for finding an optimal ordering? Also is there a name for this cost that i'm not aware of?
Ideas:
A BFS ordering can do arbitrarily bad on this problem: Consider a complete binary tree -- the optimal cost is $O(\log N)$ but a BFS ordering can cost up to $O(N)$.
A DFS ordering can do arbitrarily bad on this problem: Consider a path graph modified such that each vertex is connected to an additional leaf vertex -- the optimal cost is $2$ but a DFS ordering can cost up to $O(N)$.