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. 245-251, 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 n-vertex graph G of bounded degree, its crossing
number 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 degrees
to cr(G)+[1/16] ∑v ∈ Gdv2 = Ω(bw2(G)) in [,], 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 terms of its crossing number.
|
Journal Supporters
|