Geometric embeddability of complexes is -complete
From MaRDI portal
Publication:6854557
Logic in computer science (03B70) Simplicial sets and complexes in algebraic topology (55U10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites work
- A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
- A history of algebraic and differential topology 1900--1960
- A Linear Time Planarity Algorithm for 2-Complexes
- A Nonpolyhedral Triangulated Mobius Strip
- A note on geometric embeddings of simplicial complexes in a Euclidean space
- Algorithmic solvability of the lifting-extension problem
- An alternative proof that 3-manifolds can be triangulated
- Approximating Embeddings of Polyhedra In Codimension Three
- Charakterisierung der Komplexe der Ebene und der 2-Sphäre
- Complexity of some geometric and topological problems
- Computing all maps into a sphere
- Dimensionstheorie.
- Efficient Planarity Testing
- Embeddability in R^3 is NP-hard
- Embeddability in the 3-sphere is decidable
- Embeddability of Simplicial Complexes is Undecidable
- Embedding dimensions of simplicial complexes on few vertices
- Extendability of continuous maps is undecidable
- Extendability of simplicial maps is undecidable
- Framework for ER-completeness of two-dimensional packing problems
- Hardness of almost embedding simplicial complexes in \(\mathbb {R}^d\)
- Hardness of embedding simplicial complexes in R^d
- 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 3515486 (Why is no real title available?)
- scientific article; zbMATH DE number 3283314 (Why is no real title available?)
- scientific article; zbMATH DE number 3047038 (Why is no real title available?)
- scientific article; zbMATH DE number 3102263 (Why is no real title available?)
- Imbeddings of simplicial complexes
- Integer realizations of disk and segment graphs
- Invariants of graph drawings in the plane
- Knots and links in spatial graphs: a survey
- Komplexe in euklidischen Räumen
- Necessary Conditions for Geometric Realizability of Simplicial Complexes
- Obstructions to the imbedding of a complex in a euclidean space. I: The first obstruction
- On classifying continuous constraint satisfaction problems
- On embeddability of joins and their `factors'
- On the Complexity of Nash Equilibria and Other Fixed Points
- On the generation of oriented matroids
- Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension
- Polynomial-time homology for simplicial Eilenberg-MacLane spaces
- Polytopes, graphs, and complexes
- Realization of Posets
- Realization spaces of 4-polytopes are universal
- Recognition and complexity of point visibility graphs
- Smoothing the gap between NP and ER
- The art gallery problem is \(\exists \mathbb{R}\)-complete
- The complexity of drawing a graph in a polygonal region
- The Product of Nonplanar Complexes does not Imbed in 4-Space
- Van Kampen's embedding obstruction is incomplete for 2-complexes in \(\mathbb{R}^ 4\)
- Who needs crossings? Hardness of plane graph rigidity
This page was built for publication: Geometric embeddability of complexes is \(\exists\mathbb{R}\)-complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6854557)
