Motivation: I want to compute a topological sort order in which the connected vertices are close to each other.
Problem statement: Given a DAG $G(V,E)$ with $n$ vertices, compute a topological sort with minimum maximum edge length (MEL), where MEL in a valid topological sort order $v_1, v_2 \ldots v_n$ is defined as $\max_{(v_i, v_j) \in E} \ |j - i|$.
Your problem is known under the name MINIMUM DIRECTED BANDWIDTH.
It is NP-complete:
M.R. Garey, R.L. Graham, D.S. Johnson and D.E. Knuth:
"Complexity Results for Bandwidth Minimization"
SIAM Journal on Applied Mathematics 34, (1978), pp. 477-495
It is problem [GT41] in the NP-completeness book by Garey and Johnson.
The special case where every vertex in $G=(V,E)$ has indegree $\Theta(|V|)$ has a polynomial time approximation algorithm with worst case guarentee 2:
https://www.nada.kth.se/~viggo/wwwcompendium/node54.html
