A Bipartite Strengthening of the Crossing Lemma

Fox, Jacob and Pach, János and Tóth, Csaba D. (2008) A Bipartite Strengthening of the Crossing Lemma. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007 , pp. 13-24(Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_4).

Full text not available from this repository.

Abstract

The celebrated Crossing Lemma states that, in every drawing of a graph with n vertices and m geq 4n edges there are 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. We prove for every k N mathbb N that every graph G with n vertices and m geq 3n edges drawn in the plane such that any two edges intersect in at most k points has two disjoint subsets of edges, E_1 and E_2, each of size at least c_km^2/n^2, such that every edge in E_1 crosses all edges in E_2, where c_k>0 only depends on k. This bound is best possible up to the constant c_k for every $kin mathbb N$. We also prove that every graph G with n vertices and $m geq 3n$ edges drawn in the plane with $x$-monotone edges has disjoint subsets of edges, E_1 and E_2, each of size Omega(m^2/ (n^2 , rm polylog , n))$, such that every edge in $E_1$ crosses all edges in $E_2$. On the other hand, we construct x-monotone drawings of bipartite dense graphs where the largest such subsets $E_1$ and E_2 have size O(m^2/(n^2 log (m/n))).

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-77537-9_4
Classifications: G Algorithms and Complexity > G.420 Crossings
URI: http://gdea.informatik.uni-koeln.de/id/eprint/824

Actions (login required)

View Item View Item