Unavoidable patterns and plane paths in dense topological graphs
By: Balázs Keszegh , Andrew Suk , Gábor Tardos and more
Potential Business Impact:
Finds hidden patterns in connected dots.
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.
Similar Papers
A note on non-crossing path partitions in the plane
Computational Geometry
Counts ways to connect points without lines crossing.
A Simplified Proof for the Edge-Density of 4-Planar Graphs
Combinatorics
Untangles messy drawings with fewer lines.
A Simplified Proof for the Edge-Density of 4-Planar Graphs
Combinatorics
Makes drawings with fewer crossings possible.