Incidence geometry and crossing arguments

A drawing of a finite simple graph places distinct vertices in the plane and draws edges as curves with no unrelated vertex in an edge interior. We may use a minimum-crossing drawing in general position, with adjacent edges not crossing and no triple crossing. Deleting one edge per crossing leaves a planar simple graph, yielding the rough lower bound crossing number at least E − 3n. This estimate becomes weak when the original graph is dense.

Select every vertex independently with probability p and retain induced edges. Expected vertex and edge counts are pn and p²E. A crossing between two independent edges survives with probability p⁴ because four distinct endpoints must survive. Taking expectations in the rough planar bound and choosing p = 4n/E gives the crossing lemma with constant 1/64, provided E is at least 4n so the chosen probability is at most one. This is a proof sketch with the drawing simplifications stated explicitly.

Let P be n distinct points and L be m distinct lines in the real plane. An incidence is a pair consisting of a point and a line containing it. If either set is empty, the incidence count is zero and the bound is immediate; henceforth assume n and m are positive. Ignore lines with no incident point and call the number of remaining lines m′. Along each such line, join consecutive points of P. A line with k incident points contributes k − 1 edges, so the total edge count is I − m′.

The graph is simple because two distinct points determine only one line, and consecutive-point edges have no other P-point in their interior. Two supporting lines cross at most once, so the displayed drawing has at most m choose two crossings; intersections at graph vertices do not count as edge crossings. If several edges cross concurrently at a point outside P, a local perturbation separates them into ordinary pair crossings without exceeding the same bound from pairs of supporting lines. These facts rely on distinct lines and the real planar setting. Repeated line copies or arbitrary curves can create multiplicities requiring different estimates.

If E is less than 4n, then I = E + m′ is less than 4n + m, already an acceptable incidence bound. Otherwise combine the cubic crossing lower bound with the quadratic upper bound from pairs of supporting lines. Solving gives E at most 32 to the power one-third times n to the power two-thirds times m to the power two-thirds. Adding m′ gives the dense contribution; retaining both branches explains the n + m terms.

The big-O notation hides an absolute constant, not a promise that the leading mixed-power term dominates for all n and m. A single line can contain all n points, so an n term is indispensable. Likewise one point can lie on all m lines, requiring an m term. The bound concerns a worst-case maximum; it does not predict the exact count in one configuration or imply that every configuration achieves that growth. Small examples are useful for checking the construction even when constants make the upper bound loose.