An Improved Lower Bound for Crossing Numbers

Djidjev, Hristo and Vrt'o, Imrich (2002) An Improved Lower Bound for Crossing Numbers. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001 , pp. 96-101(Official URL: http://dx.doi.org/10.1007/3-540-45848-4_8).

Full text not available from this repository.

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. Leighton [14] proved that for any n-vertex graph G of bounded degree, its crossing number satisfiescr(G) + n = Ω(bw2(G), wherebw(G) is the bisection width of G. The lower bound method was extended for graphs of arbitrary vertex degrees to cr in [15,19], where dv 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 path-width of G in term of its crossing number.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-45848-4_8
Classifications: Z Theory > Z.001 General
G Algorithms and Complexity > G.420 Crossings
URI: http://gdea.informatik.uni-koeln.de/id/eprint/423

Actions (login required)

View Item View Item