ON GEOMETRIC GRAPHS WITH NO K PAIRWISE PARALLEL EDGES

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. Two edges of a geometric graph are said to be parallel if they are opposite sides of a convex quadrilateral. In this paper we show that, for any fixed k greater than or equal to 3, any geometric graph on it vertices with n o k pairwise parallel edges contains at most O(n) edges, and any geome tric graph on n vertices with no k pairwise crossing edges contains at most O(n log n) edges, We also prove a conjecture by Kupitz that any geometric graph on n vertices with no pair of parallel edges contains at most 2n - 2 edges.