Recognition of unit segment and polyline graphs is R -complete

DOI10.1007/978-3-031-75409-8_19MaRDI QIDQ6988713zbMATH OpenFDO

Authors Tillmann Miltzow, Simon Weber, Lasse Wulf

Publication date 2 May 2025

Full work available at URL https://doi.org/10.1007/978-3-031-75409-8_19

zbMATH Keywords

intersection graphsrecognitionpolylineunit segment

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Cites work

• scientific article; zbMATH DE number 4142090 (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?)
• A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
• Complexity of geometric \(k\)-planarity for fixed \(k\)
• Complexity of some geometric and topological problems
• Covering polygons is even Harder
• Decidability of string graphs
• EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
• Fine-grained complexity of coloring unit disks and balls
• Fixed points, Nash equilibria, and the existential theory of the reals
• Framework for ER-completeness of two-dimensional packing problems
• Integer realizations of disk and segment graphs
• Integer representations of convex polygon intersection graphs
• Intersection graphs of rays and grounded segments
• Intersection graphs of segments
• On restricted nonnegative matrix factorization
• On the computational complexity of decision problems about multi-player Nash equilibria
• Outerstring graphs are -bounded
• Realization spaces of 4-polytopes are universal
• Recognition of Circle Graphs
• Recognizing string graphs in NP
• Smoothing the gap between NP and ER
• Sphere and dot product representations of graphs
• String graphs. I: The number of critical nonstring graphs is infinite
• String graphs. II: Recognizing string graphs is NP-hard
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Art Gallery Problem is ∃ℝ-complete
• The complexity of drawing a graph in a polygonal region
• The complexity of positive semidefinite matrix factorization
• The complexity of tensor rank
• Thirty Essays on Geometric Graph Theory
• Who needs crossings? Hardness of plane graph rigidity
• \(\exists\mathbb{R}\)-complete decision problems about symmetric Nash equilibria in symmetric multi-player games
• \(\forall\exists\mathbb {R}\)-completeness and area-universality

Cited in

(1)

• The complexity of recognizing geometric hypergraphs

This page was built for publication: Recognition of unit segment and polyline graphs is \(\exists \mathbb{R} \)-complete

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