Crossing Numbers and Hard Erdős Problems in Discrete Geometry

1997/09/01 by Łászló A. Székely · 274 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Data Management and Algorithms #Crossing number (knot theory) #Discrete geometry #Mathematics #Combinatorics #Geometry #Mathematical proof #Plane (geometry) #Unit (ring theory) #Graph #Upper and lower bounds #Mathematical analysis

paper · doi:10.1017/s0963548397002976

published in Combinatorics Probability Computing 6(3), 353-358 (Cambridge University Press)

openalex publication_date 1997/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21

Abstract

We show that an old but not well-known lower bound for the crossing number of a graph yields short proofs for a number of bounds in discrete plane geometry which were considered hard before: the number of incidences among points and lines, the maximum number of unit distances among n points, the minimum number of distinct distances among n points.

Citations

• Combinatorial complexity bounds for arrangements of curves and spheres

Cited by

• Cutting Circles into Pseudo-Segments and Improved Bounds for Incidences% and Complexity of Many Faces
• Erdős’s Unit Distance Problem
• Combinatorial Geometry Problems in Pattern Recognition
• Forbidden patterns and unit distances
• An Improved Constant Factor for the Unit Distance Problem
• Distinct Distances in Graph Drawings
• Arrangement of lines [wikipedia]