Combinatorics, Probability and Computing

Table of Contents - 1997 - Volume 6, Issue 03  


Crossing Numbers and Hard Erdos Problems in Discrete Geometry

LÁSZLÓ A. SZÉKELY a1
a1 Department of Mathematics, University of South Carolina, Columbia, SC 29208, USA (e-mail: laszlo@math.sc.edu)

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.

(Received August 30 1995)
(Revised November 17 1995)