@inproceedings{ca77a0a081d74775931afae6ddb5f962,
title = "Geometric Thickness of Multigraphs is ∃R-Complete",
abstract = "We say that a (multi)graph G=(V,E) has geometric thickness t if there exists a straight-line drawing φ:V→R2 and a t-coloring of its edges where no two edges sharing a point in their relative interior have the same color. The Geometric Thickness problem asks whether a given multigraph has geometric thickness at most t. In this paper, we settle the computational complexity of Geometric Thickness by showing that it is ∃R-complete already for thickness 57. Moreover, our reduction shows that the problem is ∃R-complete for 8280-planar graphs, where a graph is k-planar if it admits a topological drawing with at most k crossings per edge. In this paper we answer previous questions on geometric thickness and on other related problems, in particular that simultaneous graph embeddings of 58 edge-disjoint graphs and pseudo-segment stretchability with chromatic number 57 are ∃R-complete.",
author = "Henry F{\"o}rster and Philipp Kindermann and Tilmann Miltzow and Irene Parada and Soeren Terziadis and Birgit Vogtenhuber",
note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.; 16th Latin American Symposium on Theoretical Informatics : LATIN 2024, LATIN 2024 ; Conference date: 18-03-2024 Through 22-03-2024",
year = "2024",
doi = "10.1007/978-3-031-55598-5_22",
language = "English",
isbn = "9783031555978",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "336--349",
editor = "Soto, {Jos{\'e} A.} and Andreas Wiese",
booktitle = "LATIN 2024",
address = "Germany",
}