2026-07-25T00:40:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8778 2024-03-06T10:42:38Z ddc:004 open_access

A Crossing Lemma for Multigraphs Pach, János Tóth, Géza crossing number Crossing Lemma multigraph separator theorem Let G be a drawing of a graph with n vertices and e>4n edges, in which no two adjacent edges cross and any pair of independent edges cross at most once. According to the celebrated Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi and Leighton, the number of crossings in G is at least c{e^3 over n^2}, for a suitable constant c>0. In a seminal paper, Székely generalized this result to multigraphs, establishing the lower bound c{e^3 over mn^2}, where m denotes the maximum multiplicity of an edge in G. We get rid of the dependence on m by showing that, as in the original Crossing Lemma, the number of crossings is at least c'{e^3 over n^2} for some c'>0, provided that the "lens" enclosed by every pair of parallel edges in G contains at least one vertex. This settles a conjecture of Bekos, Kaufmann, and Raftopoulou. Schloss Dagstuhl – Leibniz-Zentrum für Informatik János Pach and Géza Tóth 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.65 urn:nbn:de:0030-drops-87781 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.65 eng https://creativecommons.org/licenses/by/3.0/legalcode