A bipartite strengthening of the crossing Lemma

DOI10.1016/J.JCTB.2009.03.005MaRDI QIDQ968451zbMATH OpenOpenAlexFDO

Authors Jacob Fox, János Pach, Csaba D. Tóth

Publication date 5 May 2010

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL http://infoscience.epfl.ch/record/129375

zbMATH Keywords

intersection graphpartially ordered setcrossing numberbisection width

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• A Bipartite Strengthening of the Crossing Lemma
• Improving the crossing lemma by finding more crossings in sparse graphs
• Improving the crossing lemma by finding more crossings in sparse graphs
• A crossing lemma for multigraphs
• A crossing lemma for multigraphs

Cites work

• scientific article; zbMATH DE number 2145235 (Why is no real title available?)
• scientific article; zbMATH DE number 1849959 (Why is no real title available?)
• scientific article; zbMATH DE number 5019924 (Why is no real title available?)
• scientific article; zbMATH DE number 5035595 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• A bipartite analogue of Dilworth's theorem
• Additive combinatorics
• Applications of the crossing number
• Comparability graphs and intersection graphs
• Convexity and sumsets
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• Crossing number, pair-crossing number, and expansion
• Crossing patterns of segments
• Crossing-Free Subgraphs
• Distinct distances in the plane
• Extremal problems in discrete geometry
• Improved bounds for planar \(k\)-sets and related problems
• Improving the crossing lemma by finding more crossings in sparse graphs
• Isosceles triangles determined by a planar point set
• New bounds on crossing numbers
• New lower bound techniques for VLSI
• On Sets of Distances of n Points
• On the Number of Incidences Between Points and Curves
• Ramanujan graphs
• String graphs and incomparability graphs
• The \(k\) most frequent distances in the plane
• Topological graphs with no large grids
• Which crossing number is it anyway?

Cited in

(9)

• A crossing lemma for multigraphs
• Crossings in grid drawings
• Separators in region intersection graphs
• Clique-based separators for geometric intersection graphs
• Optimality program in segment and string graphs
• Applications of a new separator theorem for string graphs
• A Bipartite Strengthening of the Crossing Lemma
• String graphs and incomparability graphs
• On grids in topological graphs

This page was built for publication: A bipartite strengthening of the crossing Lemma

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q968451)