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.
Reviewer: Arthur T.White (Kalamazoo)
MSC:
05C10 | Planar graphs; geometric and topological aspects of graph theory |
05C80 | Random graphs (graph-theoretic aspects) |