Geometric Thickness of Multigraphs is ∃R-Complete

Henry Förster; Philipp Kindermann; Tillmann Miltzow; Irene Parada; Soeren Terziadis; Birgit Vogtenhuber

doi:10.1007/978-3-031-55598-5_22

Geometric Thickness of Multigraphs is ∃R-Complete

Henry Förster^*
, Philipp Kindermann
, Tillmann Miltzow
, Irene Parada
, Soeren Terziadis
, Birgit Vogtenhuber

^*Corresponding author for this work

Sub Algorithms and Complexity

Wilhelm-Schickard-Institut für Informatik
Trier University
Polytechnic University of Catalonia
Vienna University of Technology
Graz University of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 pseudosegment stretchability with chromatic number 57 are ∃R-complete.

Original language	English
Title of host publication	LATIN 2024: Theoretical Informatics
Subtitle of host publication	16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part I
Editors	José A. Soto, Andreas Wiese
Publisher	Springer
Pages	336-349
Number of pages	14
ISBN (Electronic)	978-3-031-55598-5
ISBN (Print)	978-3-031-55597-8
DOIs	https://doi.org/10.1007/978-3-031-55598-5_22
Publication status	Published - 2024

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	14578

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

Access to Document

10.1007/978-3-031-55598-5_22

Cite this

Förster, H., Kindermann, P., Miltzow, T., Parada, I., Terziadis, S., & Vogtenhuber, B. (2024). Geometric Thickness of Multigraphs is ∃R-Complete. In J. A. Soto, & A. Wiese (Eds.), LATIN 2024: Theoretical Informatics: 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part I (pp. 336-349). (Lecture Notes in Computer Science; Vol. 14578). Springer. https://doi.org/10.1007/978-3-031-55598-5_22

@inproceedings{ceaa0b4284fd419aa948168cede6140c,

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 pseudosegment stretchability with chromatic number 57 are ∃R-complete.",

author = "Henry F{\"o}rster and Philipp Kindermann and Tillmann 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.",

year = "2024",

doi = "10.1007/978-3-031-55598-5\_22",

language = "English",

isbn = "978-3-031-55597-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "336--349",

editor = "Soto, \{Jos{\'e} A.\} and Andreas Wiese",

booktitle = "LATIN 2024: Theoretical Informatics",

}

Förster, H, Kindermann, P, Miltzow, T, Parada, I, Terziadis, S & Vogtenhuber, B 2024, Geometric Thickness of Multigraphs is ∃R-Complete. in JA Soto & A Wiese (eds), LATIN 2024: Theoretical Informatics: 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part I. Lecture Notes in Computer Science, vol. 14578, Springer, pp. 336-349. https://doi.org/10.1007/978-3-031-55598-5_22

Geometric Thickness of Multigraphs is ∃R-Complete. / Förster, Henry; Kindermann, Philipp; Miltzow, Tillmann et al.
LATIN 2024: Theoretical Informatics: 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part I. ed. / José A. Soto; Andreas Wiese. Springer, 2024. p. 336-349 (Lecture Notes in Computer Science; Vol. 14578).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Geometric Thickness of Multigraphs is ∃R-Complete

AU - Förster, Henry

AU - Kindermann, Philipp

AU - Miltzow, Tillmann

AU - Parada, Irene

AU - Terziadis, Soeren

AU - Vogtenhuber, Birgit

PY - 2024

Y1 - 2024

N2 - 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 pseudosegment stretchability with chromatic number 57 are ∃R-complete.

AB - 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 pseudosegment stretchability with chromatic number 57 are ∃R-complete.

U2 - 10.1007/978-3-031-55598-5_22

DO - 10.1007/978-3-031-55598-5_22

M3 - Conference contribution

SN - 978-3-031-55597-8

T3 - Lecture Notes in Computer Science

SP - 336

EP - 349

BT - LATIN 2024: Theoretical Informatics

A2 - Soto, José A.

A2 - Wiese, Andreas

PB - Springer

ER -

Förster H, Kindermann P, Miltzow T, Parada I, Terziadis S, Vogtenhuber B. Geometric Thickness of Multigraphs is ∃R-Complete. In Soto JA, Wiese A, editors, LATIN 2024: Theoretical Informatics: 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part I. Springer. 2024. p. 336-349. (Lecture Notes in Computer Science). doi: 10.1007/978-3-031-55598-5_22

Geometric Thickness of Multigraphs is ∃R-Complete

Abstract

Publication series

Bibliographical note

Access to Document

Fingerprint

Cite this