The Crossing Number of
Dense Graphs
The crossing number of a graph G,
cr(G), is the minimum number
of crossings over all proper drawings of G. Any planar graph on n vertices has at most 3n-6 edges, so intuition suggests
that the crossing number should increase as the number of edges e grows large. The best known
general lower bound is due to [ACNS]
Theorem: If G has n vertices and e edges with e at least 7.5 n, then cr(G) is at least e^3/(33.75 n^2)
The constant factor may be improved, but otherwise the result is
tight. The following asks for the best possible constant.Let f(n) >> g(n) denote that the
limit of f(n)/g(n) approaches
infinity as n approaches infinity. Let K_0 = lim min(cr(G))/(e^3/n^2)
where the limit is taken over all graphs with n << e << n^2 as n approaches infinity.
Problem: Determine the exact value of K_0
It is known [PST] that K_0
lies between .029 and .06.
References:
[ACNS} M. Ajtai, V. Chvatal, M. Newborn, and E. Szemeredi,
Crossing-free subgraphs, Annals of
Discret Math. 12 (1982)
9-12
[PST] J. Pach, J. Spencer, and G. Toth, New bounds for crossing
numbers, in Proceedings of 15th
Annual Symposium on Computational Geometry, ACM Press, 1999,
124-133. Also in Discrete and
Computational Geometry.
Submitted by: Dan Archdeacon, Dept. of Math.
and Stat.,
Send comments to dan.archdeacon@uvm.edu
December 2003