It is shown that every complete n-vertex simple topological graph has at least Q(n~(1/3)) pairwise disjoint edges, and these edges can be found in polynomial time. This proves a conjecture of Pach and Toth, which appears as problem 5 from chapter 9.5 in Research Problems in Discrete Geometry by Brass, Moser, and Pach.
展开▼
