## 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