Note on geometric graphs (Q1971016)

The vertices of a geometric graph are points in the plane in a general position and the edges are (possibly crossing) line segments connecting the vertices. The article addresses the problem of determining the smallest number \( e_k(n) \) such that any geometric graph with \( n \) vertices and \( m > e_k(n) \) edges contains \( k+1 \) pairwise disjoint edges. The best previously known upper bound \( e_k(n) \leq k^3(n+1) \), for all \( k \leq n/2 \), is due to \textit{G. Tóth} and \textit{P. Valtr} [Geometric graphs with few disjoint edges, Discrete Comput. Geom. 22, No. 4, 633-642 (1999; Zbl 0939.68097)]. In the article under review, the upper bound is improved to \( e_k(n) \leq 2^9k^2n \), for all \( k < n/2 \), and this upper bound is shown to be sharp apart from the value of the constant for all \( k \) in \( O(\sqrt{n}) \). The nice simple proof of the upper bound takes advantage of a clever organization of the edges of the geometric graphs with no more than \( k \) pairwise disjoint edges into a limited number of length-limited ``zig-zag'' paths.