Geometric graphs with each edge crossing at most three others
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 maximum number of edges in a geometric n-vertex graph such that no edge crosses more more than 3 other edges.

It is known that there are graphs with at least 11n/2 + o(n) edges. The best upper bound is 17n/3. The problem obviously generalizes to geometric realizations with no edge crossing more than k other edges.

I do not have references for this problem.
 

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

Send comments to dan.archdeacon@uvm.edu

December 2003