Let $T$ be a rooted tree with root $r$. Say an ordering $v_1,\ldots,v_n$ of the vertices of $T$ is a search order if $v_1=r$ and for all $2 \leq i \leq n$, there is $j < i$ such that $v_j$ is the parent of $v_i$. In other words, parents are explored before their children in the order.
For a given search order $v_1,\ldots,v_n$, let $w(v_i)=\max(j:v_iv_j \in E(T))-\min(j:v_jv_i \in E(T))$. The max is the time the last child of $v_i$ is explored, and the min is the time the parent of $v_i$ is explored. Say the width of the order is $\max(w(v_i):1 \leq i \leq n)$, and say the width of $T$ is the minimum width of an ordering of $T$.
Is anything known about the width? Is it a known concept under another name? Have any theorems been proved about it? Any equivalent characterizations/definitions? Any useful bounds, perhaps in terms of the maximum degree of $T$?
Edit: This is the directed bandwidth, as David Eppstein points out below. I'm still interested in any bounds -- perhaps some upper bound with a simple form, perhaps even with an approximation guarantee?
