2026-08-05T05:22:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25001 2025-11-26T06:44:54Z ddc:004 open_access

Crossing Number of Simple 3-Plane Drawings Goetze, Miriam Hoffmann, Michael Rutter, Ignaz Ueckerdt, Torsten beyond planar graphs edge density crossing number density formula We study 3-plane drawings, that is, drawings of graphs in which every edge has at most three crossings. We show how the recently developed Density Formula for topological drawings of graphs [Kaufmann et al., 2024] can be used to count the crossings in terms of the number n of vertices. As a main result, we show that every 3-plane drawing has at most 5.5(n-2) crossings, which is tight. In particular, it follows that every 3-planar graph on n vertices has crossing number at most 5.5n, which improves upon a recent bound [Bekos et al., 2024] of 6.6n. To apply the Density Formula, we carefully analyze the interplay between certain configurations of cells in a 3-plane drawing. As a by-product, we also obtain an alternative proof for the known statement that every 3-planar graph has at most 5.5(n-2) edges. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Miriam Goetze and Michael Hoffmann and Ignaz Rutter and Torsten Ueckerdt 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.15 urn:nbn:de:0030-drops-250014 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.15 eng https://creativecommons.org/licenses/by/4.0/legalcode