Crossing Numbers and Hard Erdős Problems in Discrete Geometry (Q4354594)

The main aim of the author is to derive short proofs for a number of theorems in discrete geometry from the following theorem and from a generalization of this theorem. Theorem: For any simple graph \(G\) with \(n\) vertices and \(e\geq 4n\) edges, the crossing number of \(G\) on the plane is at least \(e^{3-}/(10n)^2\). [\textit{M. Ajtai}, \textit{V. Chvatal}, \textit{M. M. Newborn} and \textit{E. Szemerédi}, Ann. Discrete Math. 12, 9--12 (1982; Zbl 0502.05021) and \textit{F. T. Leighton} [Complexity issues in VLSI. Cambridge, MA: MIT Press (1983), pbk (2003)]. For the generalization of a simple graph drawn on an orientable or nonorientable compact 2-manifold see \textit{F. Shahrokhi}, \textit{L. Székely} \textit{O. Sýkora} and \textit{I. Vrtó}, Algorithmica 16, No. 1, 118--131 (1996; Zbl 0854.68074) and Adv. Math. 123, No. 2, 105--119 (1996; Zbl 0865.05036)]. (New) proofs are given for the following theorems (among other): -- For \(n\) points and \(\ell\) lines in the Euclidean plane, the number of incidences among the points and lines is at most \(c[(ne)^{2/3} +n+ \ell]\), where \(c\) is a constant. -- The number of unit distances among \(n\) points in the plane is at most \(cn^{4/3}\). -- When \(G\) is a multigraph with \(n\) nodes, \(e\) edges and maximum edge multiplicity \(m\), then either \(e<5nm\) or crossing number of \(G\geq ce^3/(n^2m)\). The last theorem has immediate consequence for incidences between points and curves in the plane.