Graph bandwidth

Summary

In graph theory, the graph bandwidth problem may be visualized as placing the vertices of a given graph at distinct integer positions along the number line so that the length of the longest edge is minimized. Such placement is called linear graph arrangement, linear graph layout or linear graph placement. It may be formalized as labeling the $n$ vertices $v_i$ of a graph $G$ with distinct integers $f(v_i)$ so that the quantity $\max\{\,| f(v_i) - f(v_j)| : v_iv_j \in E \,\}$ is minimized, where $E$ is the edge set of $G$.