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.
DIMACS Home Page