Geometric thickness of multigraphs is R-complete

DOI10.1007/S00453-025-01351-7MaRDI QIDQ6894403zbMATH OpenFDO

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

Publication date 25 November 2025

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00453-025-01351-7

zbMATH Keywords

colorabilityexistential theory of the realsgeometric simultaneous embeddinggeometric thicknesssegment stretchability

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• \(\forall\exists\mathbb {R}\)-completeness and area-universality
• Algorithms and Data Structures
• Area-efficient static and incremental graph drawings
• Beyond the Existential Theory of the Reals
• Bounded-degree graphs have arbitrarily large geometric thickness
• Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality
• Complexity of geometric \(k\)-planarity for fixed \(k\)
• Complexity of some geometric and topological problems
• Computational complexity of decision problems about Nash equilibria in win-lose multi-player games
• Computational complexity of multi-player evolutionarily stable strategies
• Covering polygons is even Harder
• Determining the thickness of graphs is NP-hard
• Drawing partially embedded and simultaneously planar graphs
• Drawing partially embedded and simultaneously planar graphs
• Enumerating order types for small point sets with applications
• Every planar graph with nine points has a nonplanar complement
• Exotic quantifiers, complexity classes, and complete problems
• Exotic Quantifiers, Complexity Classes, and Complete Problems
• Fixed points, Nash equilibria, and the existential theory of the reals
• Framework for ER-completeness of two-dimensional packing problems
• Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
• Geometric embeddability of complexes is \(\exists\mathbb{R}\)-complete
• Geometric embeddability of complexes is \(\exists\mathbb{R}\)-complete
• Geometric Thickness of Complete Graphs
• Graph product structure for non-minor-closed classes
• scientific article; zbMATH DE number 3144962 (Why is no real title available?)
• scientific article; zbMATH DE number 4092241 (Why is no real title available?)
• scientific article; zbMATH DE number 17663 (Why is no real title available?)
• scientific article; zbMATH DE number 2145231 (Why is no real title available?)
• scientific article; zbMATH DE number 2159655 (Why is no real title available?)
• scientific article; zbMATH DE number 3199421 (Why is no real title available?)
• scientific article; zbMATH DE number 7724206 (Why is no real title available?)
• Intersection graphs of rays and grounded segments
• Intersection graphs of rays and grounded segments
• Intersection graphs of segments
• IS CAUSAL REASONING HARDER THAN PROBABILISTIC REASONING?
• Minimum partition into plane subgraphs: the CG:SHOP challenge 2022
• Mnëv's universality theorem revisited
• Non-separable and planar graphs.
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On classifying continuous constraint satisfaction problems
• On classifying continuous constraint satisfaction problems
• On compatible triangulations with a minimum number of Steiner points
• On representations of some thickness-two graphs
• On simultaneous planar graph embeddings
• On the complexity of some geometric problems with fixed parameters
• On the geometric thickness of 2-degenerate graphs
• Order properties of lines in the plane and a conjecture of G. Ringel
• Planar graphs have bounded queue-number
• Planar graphs have bounded queue-number
• Planar graphs: Theory and algorithms
• Realizability of graphs and linkages
• Realization spaces of 4-polytopes are universal
• Realization spaces of polytopes
• Recursive Concurrent Stochastic Games
• Recursive Concurrent Stochastic Games
• Robust equilibria in mean-payoff games
• Simultaneous Geometric Graph Embeddings
• Smoothing the gap between NP and ER
• Smoothing the Gap Between NP and ER
• Stationary equilibria in discounted stochastic games
• Straight-line drawings of 1-planar graphs
• The art gallery problem is \(\exists \mathbb{R}\)-complete
• The Art Gallery Problem is ∃ℝ-complete
• The complexity of ergodic mean-payoff games
• The complexity of positive semidefinite matrix factorization
• The complexity of simultaneous geometric graph embedding
• The complexity of tensor rank
• The complexity of the Hausdorff distance
• The complexity of the Hausdorff distance
• The geometric thickness of low degree graphs
• The Non-Biplanar Character of the Complete 9-Graph
• The number of bits needed to represent a unit disk graph
• The real computational complexity of minmax value and equilibrium refinements in multi-player games
• The real computational complexity of minmax value and equilibrium refinements in multi-player games
• THE THICKNESS OF AN ARBITRARY COMPLETE GRAPH
• The thickness of graphs: A survey
• The Thickness of the Complete Graph
• Thickness and Antithickness of Graphs
• Thickness and colorability of geometric graphs
• Thickness and colorability of geometric graphs
• Universality theorems for inscribed polytopes and Delaunay triangulations

This page was built for publication: Geometric thickness of multigraphs is \(\exists \mathbb{R}\)-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6894403)