Crossing Numbers and Cutwidths

Authors

  • Hristo Djidjev
  • Imrich Vrťo

DOI:

https://doi.org/10.7155/jgaa.00069

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] ∑vGdv2 = Ω(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.

Downloads

Download data is not yet available.

Downloads

Published

2003-01-01

How to Cite

Djidjev, H., & Vrťo, I. (2003). Crossing Numbers and Cutwidths. Journal of Graph Algorithms and Applications, 7(3), 245–251. https://doi.org/10.7155/jgaa.00069

Issue

Section

Articles

Categories