97-22: Graph drawings with no k pairwise crossing edges

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