Cutwidth
In graph theory, the cutwidth of an undirected graph is the smallest integer k {\displaystyle 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 {\displaystyle k} edges. That is, if the vertices are numbered v 1 , v 2 , … v n {\displaystyle v_{1},v_{2},\dots v_{n}} , then for every ℓ = 1 , 2 , … n − 1 {\displaystyle \ell =1,2,\dots n-1} , the number of edges v i v j {\displaystyle v_{i}v_{j}} with i ≤ ℓ {\displaystyle i\leq \ell } and j > ℓ {\displaystyle j>\ell } is at most k {\displaystyle k} .