×

Thirteen problems on crossing numbers. (English) Zbl 0957.05026

Thirteen crossing-number problems are surveyed, beginning with the classical conjecture of Zarankiewicz for crossing numbers of complete bipartite graphs. Some of the problems deal with related parameters, such as the rectilinear crossing number, the pairwise crossing number, and the odd-crossing number. The authors make conjectures about the expected value of various crossing numbers of random graphs, and they prove a large-deviation result.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C80 Random graphs (graph-theoretic aspects)