Unavoidable patterns and plane paths in dense topological graphs
Let $C_{s,t}$ be the complete bipartite geometric graph, with $s$ and $t$ vertices on two distinct parallel lines respectively, and all $s t$ straight-line edges drawn between them. In this paper, we show that every complete bipartite simple topological graph, with parts of size $2(k-1)^4 + 1$ and $2^{k^{5k}}$, contains a topological subgraph weakly isomorphic to $C_{k,k}$. As a corollary, every $n$-vertex simple topological graph not containing a plane path of length $k$ has at most $O_k(n^{2 - 8/k^4})$ edges. When $k = 3$, we obtain a stronger bound by showing that every $n$-vertex simple topological graph not containing a plane path of length 3 has at most $O(n^{4/3})$ edges. We also prove that $x$-monotone simple topological graphs not containing a plane path of length 3 have at most a linear number of edges.
Authors
- Gábor Tardos (ORCID: https://orcid.org/0000-0002-4281-1843)
- Balázs Keszegh (ORCID: https://orcid.org/0000-0002-3839-5103)
- Andrew Suk
- Ji Zeng
Publication Details
- Journal
- European Journal of Combinatorics
- Published
- 2026-09-04
- DOI
- https://doi.org/10.1016/j.ejc.2026.104435
- Primary Topic
- Computational Geometry and Mesh Generation
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Science Foundation
- Nemzeti Kutatási és Technológiai Hivatal
- European Research Council
- Nemzeti Kutatási, Fejlesztési és Innovaciós Alap
- National Research, Development and Innovation Office
- Division of Mathematical Sciences