Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00069
Crossing Numbers and Cutwidths
Hristo N. Djidjev and
Imrich Vrťo
Vol. 7, no. 3, pp. 245251, 2003. Regular paper.
Abstract The crossing number of a graph G=(V,E), denoted by cr(G), is
the 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 point
of the plane. Leighton [] proved that
for any nvertex graph G of bounded degree, its crossing
number satisfies cr(G)+n=Ω(bw^{2}(G)),
where bw(G) is the bisection width of G.
The lower bound method was extended for graphs of arbitrary vertex degrees
to cr(G)+[1/16] ∑_{v ∈ G}d_{v}^{2} = Ω(bw^{2}(G)) in [,], where d_{v} is the degree of any
vertex v. We improve this bound by showing that the bisection
width can be
replaced by a larger parameter  the cutwidth of the graph.
Our result also yields an upper bound
for the pathwidth of G in terms of its crossing number.

Journal Supporters
