2026-07-25T03:04:04Z https://drops.dagstuhl.de/oai

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

Approximating the Crossing Number of Dense Graphs (Poster Abstract) Solé Pi, Oriol Crossing numbers Approximation algorithms Geometric graph theory We present a deterministic n^(2+o(1))-time algorithm that approximates the crossing number of any graph G of order n up to an additive error of o(n⁴), as well as a randomized polynomial-time algorithm that constructs a drawing of G with cr(G)+o(n⁴) crossings. These results imply a (1+o(1))-approximation algorithm for the crossing number of dense graphs. Our work builds on the machinery used by Fox, Pach and Súk [Fox et al., 2016], who obtained similar results for the rectilinear crossing number. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Oriol Solé Pi 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.54 urn:nbn:de:0030-drops-213387 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.54 eng https://creativecommons.org/licenses/by/4.0/legalcode