## DIMACS TR: 98-22

## Geometric Graphs with Few Disjoint Edges

### Authors: Géza Tóth and Pavel Valtr

**
ABSTRACT
**

A *geometric graph* is a graph drawn in the plane so that
the vertices are represented by points in general position,
the edges are represented by straight line segments connecting the
corresponding points.

Improving a result of Pach and T\"or\H ocsik, we show that a
geometric graph on $n$ vertices
with no $k+1$ pairwise disjoint edges
has at most $k^3(n+1)$ edges.
On the other hand,
we construct geometric graphs with $n$ vertices and approximately
${3\over 2}(k-1)n$ edges,
containing no $k+1$ pairwise disjoint edges.

We also improve both the lower and upper bounds
of Goddard, Katchalski and Kleitman
on the maximum number of edges
in a geometric graph with no four pairwise disjoint edges.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-22.ps.gz

DIMACS Home Page