On the Uncrossed Number of Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915347276234752 |
|---|---|
| author | Balko, Martin Hliněný, Petr Masařík, Tomáš Orthaber, Joachim Vogtenhuber, Birgit Wagner, Mirko H. |
| author_facet | Balko, Martin Hliněný, Petr Masařík, Tomáš Orthaber, Joachim Vogtenhuber, Birgit Wagner, Mirko H. |
| contents | Visualizing a graph $G$ in the plane nicely, for example, without crossings, is unfortunately not always possible. To address this problem, Masařík and Hliněný [GD 2023] recently asked for each edge of $G$ to be drawn without crossings while allowing multiple different drawings of $G$. More formally, a collection $\mathcal{D}$ of drawings of $G$ is uncrossed if, for each edge $e$ of $G$, there is a drawing in $\mathcal{D}$ such that $e$ is uncrossed. The uncrossed number $\mathrm{unc}(G)$ of $G$ is then the minimum number of drawings in some uncrossed collection of $G$.
No exact values of the uncrossed numbers have been determined yet, not even for simple graph classes. In this paper, we provide the exact values for uncrossed numbers of complete and complete bipartite graphs, partly confirming and partly refuting a conjecture posed by Hliněný and Masařík. We also present a strong general lower bound on $\mathrm{unc}(G)$ in terms of the number of vertices and edges of $G$. Moreover, we prove NP-hardness of the related problem of determining the edge crossing number of a graph $G$, which is the smallest number of edges of $G$ taken over all drawings of $G$ that participate in a crossing. This problem was posed as open by Schaefer in his book [Crossing Numbers of Graphs 2018]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_21206 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Uncrossed Number of Graphs Balko, Martin Hliněný, Petr Masařík, Tomáš Orthaber, Joachim Vogtenhuber, Birgit Wagner, Mirko H. Combinatorics Computational Geometry Discrete Mathematics 68R10 G.2.2; F.2.2 Visualizing a graph $G$ in the plane nicely, for example, without crossings, is unfortunately not always possible. To address this problem, Masařík and Hliněný [GD 2023] recently asked for each edge of $G$ to be drawn without crossings while allowing multiple different drawings of $G$. More formally, a collection $\mathcal{D}$ of drawings of $G$ is uncrossed if, for each edge $e$ of $G$, there is a drawing in $\mathcal{D}$ such that $e$ is uncrossed. The uncrossed number $\mathrm{unc}(G)$ of $G$ is then the minimum number of drawings in some uncrossed collection of $G$. No exact values of the uncrossed numbers have been determined yet, not even for simple graph classes. In this paper, we provide the exact values for uncrossed numbers of complete and complete bipartite graphs, partly confirming and partly refuting a conjecture posed by Hliněný and Masařík. We also present a strong general lower bound on $\mathrm{unc}(G)$ in terms of the number of vertices and edges of $G$. Moreover, we prove NP-hardness of the related problem of determining the edge crossing number of a graph $G$, which is the smallest number of edges of $G$ taken over all drawings of $G$ that participate in a crossing. This problem was posed as open by Schaefer in his book [Crossing Numbers of Graphs 2018]. |
| title | On the Uncrossed Number of Graphs |
| topic | Combinatorics Computational Geometry Discrete Mathematics 68R10 G.2.2; F.2.2 |
| url | https://arxiv.org/abs/2407.21206 |