Short edges and noncrossing paths in complete topological graphs
share
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č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) = Ω(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 Ω(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.
READ FULL TEXT