## DIMACS TR: 97-22

## Graph drawings with no *k* pairwise crossing edges

### Author: Pavel Valtr

**
ABSTRACT
**

A geometric graph is a graph $G=(V,E)$ drawn in the
plane so that the vertex set $V$ consists of points in general
position and the edge set $E$ consists of straight line
segments between points of $V$.
It is known that,
for any fixed $k$, any geometric graph $G$ on $n$ vertices
with no $k$ pairwise crossing
edges contains at most $O(n log n)$ edges.
In this paper we give a new, simpler proof of this bound, and show
that the same bound holds also when the edges of $G$ are
represented by $x$-monotone curves (Jordan arcs).

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

DIMACS Home Page