2026-07-18T10:39:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20004 2024-06-06T06:21:16Z ddc:004 open_access

A Structure Theorem for Pseudo-Segments and Its Applications Fox, Jacob Pach, János Suk, Andrew Regularity lemma pseudo-segments intersection graphs We prove a far-reaching strengthening of Szemerédi’s regularity lemma for intersection graphs of pseudo-segments. It shows that the vertex set of such graphs can be partitioned into a bounded number of parts of roughly the same size such that almost all of the bipartite graphs between pairs of parts are complete or empty. We use this to get an improved bound on disjoint edges in simple topological graphs, showing that every n-vertex simple topological graph with no k pairwise disjoint edges has at most n(log n)^O(log k) edges. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jacob Fox and János Pach and Andrew Suk 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.59 urn:nbn:de:0030-drops-200040 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.59 eng https://creativecommons.org/licenses/by/4.0/legalcode