Fox, Jacob and Pach, János and Tóth, Csaba D. (2008) A Bipartite Strengthening of the Crossing Lemma. [Conference Paper]
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 $kin 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 |
|---|---|
| Classifications: | G Algorithms and Complexity > G.420 Crossings |
| ID Code: | 824 |
| Deposited By: | GDEA, Administration |
| Deposited On: | 24 Jun 2008 |
| Last Modified: | 18 Sep 2008 13:09 |
| Alternative Locations: | http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=4875&spage=13 |
Repository Staff Only: item control page
