2026-09-05T11:55:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25870 2026-06-23T12:59:57Z ddc:004 open_access

Unavoidable Patterns and Plane Paths in Dense Topological Graphs Keszegh, Balázs Suk, Andrew Tardos, Gábor Zeng, Ji graph drawing topological graph bipartite geometric graph forbidden subgraph extremal graph thrackle 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)⁴ + 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⁴}) 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Balázs Keszegh and Andrew Suk and Gábor Tardos and Ji Zeng 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.63 urn:nbn:de:0030-drops-258706 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.63 eng https://creativecommons.org/licenses/by/4.0/legalcode