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.
Send comments to firstname.lastname@example.org