Geometric Thickness of Multigraphs is $\exists \mathbb{R}$-complete
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929402444513280 |
|---|---|
| author | Förster, Henry Kindermann, Philipp Miltzow, Tillmann Parada, Irene Terziadis, Soeren Vogtenhuber, Birgit |
| author_facet | Förster, Henry Kindermann, Philipp Miltzow, Tillmann Parada, Irene Terziadis, Soeren Vogtenhuber, Birgit |
| contents | We say that a (multi)graph $G = (V,E)$ has geometric thickness $t$ if there exists a straight-line drawing $φ: V \rightarrow \mathbb{R}^2$ and a $t$-coloring of its edges where no two edges sharing a point in their relative interior have the same color. The \textsc{Geometric Thickness} problem asks whether a given multigraph has geometric thickness at most $t$. This problem was shown to be NP-hard for $t=2$ [Durocher, Gethner, and Mondal, CG 2016]. In this paper, we settle the computational complexity of \textsc{Geometric Thickness} by showing that it is $\exists \mathbb{R}$-complete already for thickness $30$. Moreover, our reduction shows that the problem is $\exists \mathbb{R}$-complete for $4392$-planar graphs, where a graph is $k$-planar if it admits a topological drawing with at most $k$ crossings per edge. In the course of our paper, we answer previous questions on geometric thickness and on other related problems, in particular that simultaneous graph embeddings of $31$ edge-disjoint graphs and pseudo-segment stretchability with chromatic number $30$ are $\exists \mathbb{R}$-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_05010 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Geometric Thickness of Multigraphs is $\exists \mathbb{R}$-complete Förster, Henry Kindermann, Philipp Miltzow, Tillmann Parada, Irene Terziadis, Soeren Vogtenhuber, Birgit Computational Geometry Discrete Mathematics Data Structures and Algorithms We say that a (multi)graph $G = (V,E)$ has geometric thickness $t$ if there exists a straight-line drawing $φ: V \rightarrow \mathbb{R}^2$ and a $t$-coloring of its edges where no two edges sharing a point in their relative interior have the same color. The \textsc{Geometric Thickness} problem asks whether a given multigraph has geometric thickness at most $t$. This problem was shown to be NP-hard for $t=2$ [Durocher, Gethner, and Mondal, CG 2016]. In this paper, we settle the computational complexity of \textsc{Geometric Thickness} by showing that it is $\exists \mathbb{R}$-complete already for thickness $30$. Moreover, our reduction shows that the problem is $\exists \mathbb{R}$-complete for $4392$-planar graphs, where a graph is $k$-planar if it admits a topological drawing with at most $k$ crossings per edge. In the course of our paper, we answer previous questions on geometric thickness and on other related problems, in particular that simultaneous graph embeddings of $31$ edge-disjoint graphs and pseudo-segment stretchability with chromatic number $30$ are $\exists \mathbb{R}$-complete. |
| title | Geometric Thickness of Multigraphs is $\exists \mathbb{R}$-complete |
| topic | Computational Geometry Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2312.05010 |