An algorithm for estimating the crossing number of dense graphs, and continuous analogs of the crossing and rectilinear crossing numbers
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912182418014208 |
|---|---|
| author | Solé-Pi, Oriol |
| author_facet | Solé-Pi, Oriol |
| contents | 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^4)$. We also provide a randomized polynomial-time algorithm that constructs a drawing of $G$ with $\text{cr}(G)+o(n^4)$ crossings. These results yield a $1+o(1)$ approximation algorithm for the crossing number of dense graphs. Our work complements a paper of Fox, Pach and Súk, who obtained similar results for the rectilinear crossing number.
The results of Fox, Pach and Súk and in this paper imply that the (normalized) crossing and rectilinear crossing numbers are estimable parameters. Motivated by this, we introduce two graphon parameters, the \textit{crossing density} and the \textit{rectilinear crossing density}, and we prove that, in a precise sense, these are the correct continuous analogs of the crossing and rectilinear crossing numbers of graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_00665 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An algorithm for estimating the crossing number of dense graphs, and continuous analogs of the crossing and rectilinear crossing numbers Solé-Pi, Oriol Combinatorics 05C10, 05C85 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^4)$. We also provide a randomized polynomial-time algorithm that constructs a drawing of $G$ with $\text{cr}(G)+o(n^4)$ crossings. These results yield a $1+o(1)$ approximation algorithm for the crossing number of dense graphs. Our work complements a paper of Fox, Pach and Súk, who obtained similar results for the rectilinear crossing number. The results of Fox, Pach and Súk and in this paper imply that the (normalized) crossing and rectilinear crossing numbers are estimable parameters. Motivated by this, we introduce two graphon parameters, the \textit{crossing density} and the \textit{rectilinear crossing density}, and we prove that, in a precise sense, these are the correct continuous analogs of the crossing and rectilinear crossing numbers of graphs. |
| title | An algorithm for estimating the crossing number of dense graphs, and continuous analogs of the crossing and rectilinear crossing numbers |
| topic | Combinatorics 05C10, 05C85 |
| url | https://arxiv.org/abs/2401.00665 |