On the Degenerate Crossing Number
The degenerate crossing number of a graph is the minimum number of crossing points of edges in any drawing of as a simple topological graph in the plane. This notion was introduced by Pach and Tth who showed that for a graph with vertices and edges . In this paper we completely resolve the main open question about degenerate crossing numbers and show that , provided that . This bound is best possible (apart for the multiplicative constant) as it matches the tight lower bound for the standard crossing number of a graph.
crossing number simple topological graphs crossing lemma