Crossing Numbers and Cutwidths - Djidjev, Hristo; Vrťo, Imrich (Journal of Graph Algorithms and Applications, 2003)
The crossing number of a graph G=(V,E), denoted by cr(G), isthe smallest number of edge crossings in any drawing of G in the plane.Wee assume that the drawing is good, i.e., incident edges do not cross,two edges cross at most once and at most two edges cross in a pointof the plane. Leighton [] proved thatfor any n-vertex graph G of bounded degree, its crossingnumber satisfies cr(G)+n=Ω(bw2(G)),where bw(G) is the bisection width of G.The lower bound method was extended for graphs of arbitrary vertex degreesto cr(G)+[1/16] ∑v ∈ Gdv2 = Ω(bw2(G)) in [,], where dv is the degree of anyvertex v. We improve this bound by showing that the bisectionwidth can bereplaced by a larger parameter - the cutwidth of the graph.Our result also yields an upper boundfor the path-width of G in terms of its crossing number. <!---->