Unavoidable patterns in complete simple topological graphs

Abstract

We show that every complete $n$-vertex simple topological graph contains a topological subgraph on at least $(\log n{)}^{1/4-o(1)}$ vertices that is weakly isomorphic to the complete convex geometric graph or the complete twisted graph. This is the first improvement on the bound $\Omega ({\log }^{1/8}n)$ obtained in 2003 by Pach, Solymosi, and Tóth. We also show that every complete $n$-vertex simple topological graph contains a plane path of length at least $(\log n{)}^{1-o(1)}$.

Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)