DIMACS TR: 97-22
Graph drawings with no k pairwise crossing edges
Author: Pavel Valtr
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:
DIMACS Home Page