A bipartite strengthening of the Crossing Lemma

Let G=(V,E) be a graph with n vertices and m⩾4n edges drawn in the plane. The celebrated Crossing Lemma states that G has at least Ω(m3/n2) pairs of crossing edges; or equivalently, there is an edge that crosses Ω(m2/n2) other edges. We strengthen the Crossing Lemma for drawings in which any two edges cross in at most O(1) points. An ℓ-grid in the drawing of G is a pair E1,E2⊂E of disjoint edge subsets each of size ℓ such that every edge in E1 intersects every edge in E2. If every pair of edges of G intersect in at most k points, then G contains an ℓ-grid with ℓ⩾ckm2/n2, where ck>0 only depends on k. Without any assumption on the number of points in which edges cross, we prove that G contains an ℓ-grid with ℓ=m2/n2polylog(m/n). If G is dense, that is, m=Θ(n2), our proof demonstrates that G contains an ℓ-grid with ℓ=Ω(n2/logn). We show that this bound is best possible up to a constant factor by constructing a drawing of the complete bipartite graph Kn,n using expander graphs in which the largest ℓ-grid satisfies ℓ=Θ(n2/logn).