# Computing topological sort while keeping edges “short”

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|$.

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: