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, Sydney, Australia , pp. 13-24 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_4).

Full text not available from this repository.


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
ID Code:824

Repository Staff Only: item control page


M. Ajtai, V. Chvátal, M. Newborn, and E. Szemerédi: Crossing-free subgraphs, in Theory and Practice of Combinatorics, vol. 60 of Mathematical Studies, North-Holland, Amsterdam, 1982, pp. 9-12.

T. K. Dey: Improved bounds for planar k-sets and related problems. Discrete Comput. Geom. 19 (1998), 373-382.

G. Elekes, M. B. Nathanson, and I. Z. Ruzsa: Convexity and sumsets. J. Number Theory 83 (2000), 194-201.

P. Erdös: On sets of distances of n points, Amer. Math. Monthly 53 (1946), 248-250.

J. Fox: A bipartite analogue of Dilworth's theorem, Order 23 (2006), 197-209.

J. Fox, J. Pach, and C. D. Tóth: Intersection patterns of curves, manuscript, 2007. Cf. http://math.nyu.edu/ pach/publications/justcurves050907.pdf

J. Fox, J. Pach, and C. D. Tóth: Turán-type results for partial orders and intersection graphs of convex sets, Israel J. Math. (2007), to appear.

M. C. Golumbic, D. Rotem, and J. Urrutia, Comparability graphs and intersection graphs. Discrete Math. 43 (1983), 37-46.

H. Gazit and G. L. Miller: Planar separators and the Euclidean norm, SIGAL Internat. Sympos. on Algorithms, vol. 450 of LNCS, Springer, 1990, pp. 338-347.

N. H. Katz and G. Tardos: A new entropy inequality for the Erdös distance problem, in Towards a theory of geometric graphs, vol. 342 of Contemp. Math., AMS, 2004, pp. 119-126.

P. Kolman and J. Matousek: Crossing number, pair-crossing number, and expansion, J. Combine. Theory Ser. B 92 (2004), 99-113.

T. Leighton: New lower bound techniques for VLSI, Math. Systems Theory 17 (1984), 47-70.

R. J. Lipton and R. E. Tarjan: A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979), 177-189.

A. Lubotzky, R. Phillips, and P. Sarnak: Ramanujan graphs, Combinatorica 8 (1988), 261-277.

J. Pach, R. Radoicić, G. Tardos, and G. Tóth: Improving the Crossing Lemma by finding more crossings in sparse graphs, Discrete Comput. Geom. 36 (2006), 527-552.

J. Pach, F. Shahrokhi, and M. Szegedy: Applications of the crossing number, Algorithmica 16 (1996), 111-117.

J. Pach and M. Sharir: On the number of incidences between points and curves. Combin. Probab. Comput. 7 (1) (1998), 121-127.

J. Pach and J. Solymosi: Crossing patterns of segments, J. Combin. Theory Ser. A 96 (2001), 316-325.

J. Pach, J. Spencer, and G. Tóth: New bounds on crossing numbers, Discrete Comput. Geom. 24 (4) (2000), 623-644.

J. Pach and G. Tóth: Which crossing number is it anyway? J. Combin. Theory Ser. B 80 (2000), 225-246.

J. Pach and G. Tardos: Isosceles triangles determined by a planar point set. Graphs Combin. 18 (2002), 769-779.

J. Pach, G. Tóth: Comment on Fox News, Geombinatorics 15 (2006), 150-154.

J. Solymosi, C. D. Tóth: Distinct distances in the plane. Discrete Comput. Geom. 25 (2001), 629-634.

J. Solymosi, G. Tardos, and C. D. Tóth: The k most frequent distances in the plane. Discrete Comput. Geom. 28 (2002), 639-648.

L. A. Székely: Crossing numbers and hard Erdös problems in discrete geometry. Combin. Probab. Comput. 6 (1997), 353-358.

E. Szemerédi and W. T. Trotter: Extremal problems in discrete geometry. Combinatorica 3 (1983), 381-392.

T. Tao and V. Vu: Additive combinatorics. Cambridge Studies in Advanced Mathematics, 105. Cambridge University Press, Cambridge, 2006.

P. Valtr, On the pair-crossing number, in Combinatorial and computational geometry, vol. 52 of MSRI Publications, Cambridge Univ. Press, 2005, pp. 569-575.