Are different notions of the crossing number the same?
The crossing number of a graph is the minimum number of edge crossings in any drawing of in the plane. In the pairwise crossing number , we minimize the number of pairs of edges that cross.
Obviously we have .
The problem was first posed by Pach and Tóth in~[PT], who first spotted the possibility that the pairwise crossing number might be different from the crossing number. They proved for graphs with pairwise crossing number , which was later improved by Valtr~[V05] to and by Tóth~[T08] to .
[T08] Géza Tóth, Note on the pair-crossing number and the odd-crossing number, Discrete Comput. Geom., 39 (2008), no. 4, 791--799. MathSciNet
* indicates original appearance(s) of problem.