DIMACS TR: 97-07

On geometric graphs with no $k$ pairwise parallel edges



Author: Pavel Valtr

ABSTRACT

A {\em 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$. Two edges of a geometric graph are said to be {\em parallel\/}, if they are opposite sides of a convex quadrilateral.

In this paper we show that, for any fixed $k\ge3$, any geometric graph on $n$ vertices with no $k$ pairwise parallel edges contains at most $O(n)$ edges, and any geometric graph on $n$ vertices with no $k$ pairwise crossing edges contains at most $O(n\log n)$ edges. We also prove a conjecture of Kupitz that any geometric graph on $n$ vertices with no pair of parallel edges contains at most $2n-2$ edges.

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

DIMACS Home Page