Embeddability of Simplicial Complexes is Undecidable

DOI10.1137/1.9781611975994.47MaRDI QIDQ5146816zbMATH OpenOpenAlexFDO

Authors Marek Filakovský, Stephan Zhechev, Uli Wagner

Publication date 2 February 2021

Published in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611975994.47

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(9)

• Extendability of simplicial maps is undecidable
• scientific article; zbMATH DE number 7051255 (Why is no real title available?)
• Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
• Some `converses' to intrinsic linking theorems
• Hardness of embedding simplicial complexes in R^d
• Adjacency graphs of polyhedral surfaces
• Geometric embeddability of complexes is \(\exists\mathbb{R}\)-complete
• Adjacency graphs of polyhedral surfaces
• Embedding into \(l_{\infty }^{2}\) is easy, embedding into \(l_{\infty}^{3}\) is NP-complete

This page was built for publication: Embeddability of Simplicial Complexes is Undecidable

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