Planar point sets determine many pairwise crossing segments

DOI10.1016/j.aim.2021.107779zbMath1467.05050arXiv1904.08845OpenAlexW3170855457MaRDI QIDQ2039541

János Pach, Natan Rubin, Gábor Tardos

Publication date: 5 July 2021

Published in: Advances in Mathematics, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1904.08845

zbMATH Keywords

geometric graphsextremal combinatoricscomputational geometryintersection graphspartial orderscomparability graphscrossing edgesepsilon-netsavoiding edgescrossing familiesavoiding sets

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Erd?s problems and related topics of discrete geometry (52C10) Ramsey theory (05D10) Density (toughness, etc.) (05C42)

Related Items

On crossing-families in planar point sets, Crossing and intersecting families of geometric graphs on point sets, A positive fraction Erdős-Szekeres theorem and its applications, Perfect matchings with crossings, Unnamed Item, A positive fraction mutually avoiding sets theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The clique problem in ray intersection graphs
• Triangle-free intersection graphs of line segments with large chromatic number
• Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
• On the Erdős distinct distances problem in the plane
• Ramsey-type constructions for arrangements of segments
• Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
• A deterministic view of random sampling and its use in geometry
• Extremal problems in discrete geometry
• On the maximum number of edges in quasi-planar graphs
• Separator theorems and Turán-type results for planar intersection graphs
• Geometric graphs with no two parallel edges
• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• \(\epsilon\)-nets and simplex range queries
• Quasi-optimal upper bounds for simplex range searching and new zone theorems
• Cutting hyperplanes for divide-and-conquer
• Crossing families
• Intersection graphs of segments
• Quasi-planar graphs have a linear number of edges
• Improved bounds for planar \(k\)-sets and related problems
• On geometric graphs with no two edges in convex position
• On geometric graphs with no \(k\) pairwise parallel edges
• A crossing lemma for Jordan curves
• Lines, line-point incidences and crossing families in dense sets
• Algebraic methods in discrete analogs of the Kakeya problem
• Cutting algebraic curves into pseudo-segments and applications
• Independent set of intersection graphs of convex objects in 2D
• Turán-type results for complete \(h\)-partite graphs in comparability and incomparability graphs
• Crossing patterns of semi-algebraic sets
• A semi-algebraic version of Zarankiewicz's problem
• Incidence Theorems and Their Applications
• Ramsey-type theorems for lines in 3-space
• A Separator Theorem for String Graphs and its Applications
• Research Problems in Discrete Geometry
• Overlap properties of geometric expanders
• Crossing-Free Subgraphs
• A Ramsey-Type Result for Convex Sets
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• On the Number of Incidences Between Points and Curves
• On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers
• Density and regularity theorems for semi-algebraic hypergraphs
• Intersection patterns of curves
• Applications of a New Separator Theorem for String Graphs
• A Dual of Dilworth's Decomposition Theorem
• String graphs and incomparability graphs