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
geometric graphsextremal combinatoricscomputational geometryintersection graphspartial orderscomparability graphscrossing edgesepsilon-netsavoiding edgescrossing familiesavoiding sets
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
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
