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 Omega(m(3)/n(2)) pairs of crossing edges; or equivalently, there is an edge that crosses Omega(m(2)/n(2)) other edges. We strengthen the Crossing Lemma for drawings in which any two edges cross in at most O(1) points. An e-grid in the drawing of G is a pair E-1, E-2 subset of E of disjoint edge subsets each of size l such that every edge in E-1 intersects every edge in E-2. If every pair of edges of G intersect in at most k points, then G contains an e-grid with l >= c(k)m(2)/n(2), where c(k) > 0 only depends on k. Without any assumption on the number of points in which edges cross. we prove that G contains an e-grid with l = m(2)/n(2)polylog(m/n). If G is dense, that is, m = Theta(n(2)), our proof demonstrates that G contains an l-grid with l = Omega(n(2)/ log n). We show that this bound is best possible up to a constant factor by constructing a drawing of the complete bipartite graph K-n,K-n using expander graphs in which the largest l-grid satisfies l = Theta(n(2) / log n). (C) 2009 Elsevier Inc. All rights reserved.