ABSTRACT
The bisection width, bw(G), of a graph G = (V, E) is the smallest |E(V 1, V 2)| for any partition (V 1, V 2) of V with | V 1 | , | V 2 | ≥ 1 3 | V | https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315152394/76a56b35-285a-4240-990f-b454c3e374e6/content/eq185.tif"/> , where E(V 1, V 2) is the set of all edges between V 1 and V 2. Bisection width is closely related to the crossing number. This connection was discovered by Leighton [225] in his work on VLSI layout, while looking for tools to bound the area necessary to draw a network. We present a slightly stronger version of his original result. For this we need the parameter ssqd ( G ) : = ∑ v ∈ V ( G ) deg G 2 ( v ) https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315152394/76a56b35-285a-4240-990f-b454c3e374e6/content/eq186.tif"/> , the sum of squared degrees.
