Fox, J. and Pach, János and Suk, A. (2024) A Structure Theorem for Pseudo-Segments and Its Applications. In: 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics, LIPIcs (293). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Wadern, p. 59. ISBN 9783959773164
|
Text
2312.01028v1.pdf Download (392kB) | Preview |
Abstract
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. © Jacob Fox, János Pach, and Andrew Suk.
| Item Type: | Book Section |
|---|---|
| Additional Information: | Export Date: 30 December 2024; Cited By: 0; Correspondence Address: ; ; ; Conference name: 40th International Symposium on Computational Geometry, SoCG 2024; Conference date: 11 June 2024 through 14 June 2024; Conference code: 199976 |
| Uncontrolled Keywords: | Computation theory; Graph theory; Bipartite graphs; Vertex set; Graphic methods; Intersection graphs; Disjoint edges; Topological graphs; Intersection graph; Regularity lemma; Regularity lemma; ITS applications; Simple++; pseudo-segments; Pseudo-segment; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 31 Dec 2024 05:19 |
| Last Modified: | 31 Dec 2024 05:19 |
| URI: | https://real.mtak.hu/id/eprint/212578 |
Actions (login required)
 |
Edit Item |
