DIMACS TR: 99-17
Note on geometric graphs
Author: Géza Tóth
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.
We show that a geometric graph of $n$ vertices
with no $k+1$ pairwise disjoint edges
has at most $2^9k^2n$ edges.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-17.ps.gz
DIMACS Home Page