Geometric graphs with few disjoint edges
Gézá Tóth, Pável Valtr · 1998
A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position, the edges are represented by straight line segments connecting the corresponding points. Improving a result of Pach and Töröcsik, we show that a geometric graph on n vertices with no k + 1 pairwise disjoint edges has at most k³(n + 1) edges. On the other hand, we construct geometric graphs with n vertices and approximately 3/2 (k - 1)n edges, containing no k + 1 pairwise disjoint edges. We also improve both the lower and upper bounds of Goddard, Katchalski and Kleitman on the maximum number of edges in a geometric graph with no four pairwise disjoint edges.