Crossing numbers of dense graphs on surfaces
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915337716367360 |
|---|---|
| author | Hubard, Alfredo de Mesmay, Arnaud Parlier, Hugo |
| author_facet | Hubard, Alfredo de Mesmay, Arnaud Parlier, Hugo |
| contents | In this paper, we provide upper and lower bounds on the crossing numbers of dense graphs on surfaces, which match up to constant factors. First, we prove that if $G$ is a dense enough graph with $m$ edges and $Σ$ is a surface of genus $g$, then any drawing of $G$ on $Σ$ incurs at least $Ω\left(\frac{m^2}{g} \log ^2 g\right)$ crossings. The poly-logarithmic factor in this lower bound is new even in the case of complete graphs and disproves a conjecture of Shahrokhi, Székely and Vrt'o from 1996. Then we prove a geometric converse to this lower bound: we provide an explicit family of hyperbolic surfaces such that for any graph $G$, sampling the vertices uniformly at random on this surface and connecting them with shortest paths yields $O\left(\frac{m^2}{g} \log ^2 g\right)$ crossings in expectation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_09974 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Crossing numbers of dense graphs on surfaces Hubard, Alfredo de Mesmay, Arnaud Parlier, Hugo Combinatorics Computational Geometry Discrete Mathematics Geometric Topology In this paper, we provide upper and lower bounds on the crossing numbers of dense graphs on surfaces, which match up to constant factors. First, we prove that if $G$ is a dense enough graph with $m$ edges and $Σ$ is a surface of genus $g$, then any drawing of $G$ on $Σ$ incurs at least $Ω\left(\frac{m^2}{g} \log ^2 g\right)$ crossings. The poly-logarithmic factor in this lower bound is new even in the case of complete graphs and disproves a conjecture of Shahrokhi, Székely and Vrt'o from 1996. Then we prove a geometric converse to this lower bound: we provide an explicit family of hyperbolic surfaces such that for any graph $G$, sampling the vertices uniformly at random on this surface and connecting them with shortest paths yields $O\left(\frac{m^2}{g} \log ^2 g\right)$ crossings in expectation. |
| title | Crossing numbers of dense graphs on surfaces |
| topic | Combinatorics Computational Geometry Discrete Mathematics Geometric Topology |
| url | https://arxiv.org/abs/2506.09974 |