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 ≥ 3 , 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 by Kupitz that any geometric graph on n vertices with no pair of parallel edges contains at most 2n-2 edges. 26 June, 1998 Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; 19n3p461.pdf yes no no yes Received January 27, 1997, and in revised form March 4, 1997, and June 16, 1997.