Publication at Faculty of Mathematics and Physics |
2005
Abstract
A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position and edges are represented by straight line segments. We show that a geometric graph on n vertices with no three pairwise disjoint edges has at most 2.5n edges.
This result is tight up to an additive constant.