A Bipartite Strengthening of the Crossing Lemma

DOI10.1007/978-3-540-77537-9_4MaRDI QIDQ5452205zbMATH OpenOpenAlexFDO

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

Publication date 25 March 2008

Published in Graph Drawing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77537-9_4

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62)

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 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
• Intersection patterns of curves
• 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
• The k most frequent distances in the plane
• Turán-type results for partial orders and intersection graphs of convex sets
• Which crossing number is it anyway?

Cited in

(4)

• A bipartite strengthening of the crossing Lemma
• Applications of the crossing number
• scientific article; zbMATH DE number 5019924 (Why is no real title available?)
• A crossing lemma for multigraphs

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 Q5452205)