2026-08-07T04:59:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21312 2024-10-28T09:51:05Z ddc:004 open_access

On the Edge Density of Bipartite 3-Planar and Bipartite Gap-Planar Graphs Büngener, Aaron Pfister, Maximilian Edge Density Beyond Planarity bipartite Graphs Discharging Method We show that if a bipartite graph G with n ≥ 3 vertices can be drawn in the plane such that (i) each edge is involved in at most three crossings per edge or (ii) each crossing is assigned to one of the two involved edges and each edge is assigned at most one crossing, then G has at most 4n-8 edges. In both cases, this bound is tight up to an additive constant as witnessed by lower-bound constructions. The former result can be used to improve the leading constant for the crossing lemma for bipartite graphs which in turn improves various results such as the biplanar crossing number or the maximum number of edges a bipartite k-planar graph can have. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aaron Büngener and Maximilian Pfister 2024 Is Part Of LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2024.28 urn:nbn:de:0030-drops-213123 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.28 eng https://creativecommons.org/licenses/by/4.0/legalcode