DIMACS TR: 99-17

Note on geometric graphs

Author: Géza Tóth


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