Short edges and noncrossing paths in complete topological graphs

Let $h(n)$ be the minimum integer such that every complete $n$-vertex simple topological graph contains an edge that crosses at most $h(n)$ other edges. In 2009, Kyn\v{c}l and Valtr showed that $h(n) = O(n^2/\log^{1/4} n)$, and in the other direction, gave constructions showing that $h(n) = \Omega(n^{3/2})$. In this paper, we prove that $h(n) = O(n^{7/4})$. Along the way, we establish a new variant of Chazelle and Welzl's matching theorem for set systems with bounded VC-dimension, which we believe to be of independent interest. We also show that every complete $n$-vertex simple topological graph contains a noncrossing path on $\Omega(n^{1/9})$ vertices. This improves the previously best known bound of $(\log n)^{1 - o(1)}$ due to Aichholzer et al., and independently, the author and Zeng.