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., University of Vermont, Burlington, VT 05401-1455 USA

Send comments to dan.archdeacon@uvm.edu

December 2003