Cutwidth

Summary

In graph theory, the cutwidth of an undirected graph is the smallest integer $k$ with the following property: there is an ordering of the vertices of the graph, such that every cut obtained by partitioning the vertices into earlier and later subsets of the ordering is crossed by at most $k$ edges. That is, if the vertices are numbered $v_1,v_2,\dots v_n$, then for every $\ell=1,2,\dots n-1$, the number of edges $v_iv_j$ with $i\le\ell$ and $j>\ell$ is at most $k$.