Geometric Graphs Without Three Disjoint Edges

A geometric graph is a graph drawn in the plane such that a) no three vertices are colinear and b) edges are straight line segments. Edges are allowed to cross, but only transversally at interior points.

Problem: Find the largest number of edges in a geometric graph with n vertices that does not have 3 disjoint edges.

Constructions of geometric graphs with n vertices and 5n/2 + O(1) edges are known. The best known upper bound on the number of edges in a geometric graph is 3n.

I do not have references for this problem.

Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of VermontBurlingtonVT 05401-1455 USA

Send comments to

December 2003