Embeddability in the 3-sphere is decidable

DOI10.1145/3078632zbMATH Open1426.68276arXiv1402.0815OpenAlexW2785162637WikidataQ105336375 ScholiaQ105336375MaRDI QIDQ3177893FDOQ3177893

Jiří Matoušek, Uli Wagner, Eric Sedgwick, Martin Tancer

Publication date: 2 August 2018

Published in: Journal of the ACM, Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

Abstract: We show that the following algorithmic problem is decidable: given a $2$-dimensional simplicial complex, can it be embedded (topologically, or equivalently, piecewise linearly) in $mathbf{R}^3$? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold $X$ into the 3-sphere $S^3$. The main step, which allows us to simplify $X$ and recurse, is in proving that if $X$ can be embedded in $S^3$, then there is also an embedding in which $X$ has a short meridian, i.e., an essential curve in the boundary of $X$ bounding a disk in $S^{3}setminusX$ with length bounded by a computable function of the number of tetrahedra of $X$.

Full work available at URL: https://arxiv.org/abs/1402.0815

Recommendations

• Embeddability in the 3-sphere is decidable
• Embeddability in \(\mathbb R^3\) is NP-hard
• Embeddability in \(R^3\) is NP-hard
• Hardness of embedding simplicial complexes in \(\mathbb R^d\)
• scientific article; zbMATH DE number 7051255

zbMATH Keywords

computational topologysimplicial complexembedding3-manifoldembeddability3-manifoldsnormal surfaces

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) General topology of complexes (57Q05) Embeddings and immersions in PL-topology (57Q35) Triangulating manifolds (57Q15) General topology of 3-manifolds (57K30)

Cited In (18)

• The complexity of recognizing geometric hypergraphs
• Computing simplicial representatives of homotopy group elements
• Title not available (Why is that?)
• The Complexity of Drawing Graphs on Few Lines and Few Planes
• Multibranched surfaces in 3-manifolds
• Low-dimensional topology. Abstracts from the workshop held January 15--21, 2023
• Atomic Embeddability, Clustered Planarity, and Thickenability
• Invariants of graph drawings in the plane
• Untangling two systems of noncrossing curves
• Finding non-orientable surfaces in 3-manifolds
• Shortest path embeddings of graphs on surfaces
• Geometric proof of Neuwirth's theorem on the construction of 3-manifolds from 2-dimensional polyhedra
• Computing Heegaard Genus is NP-Hard
• Title not available (Why is that?)
• Title not available (Why is that?)
• Adjacency graphs of polyhedral surfaces
• Frontiers of sphere recognition in practice
• An obstruction to embedding 2-dimensional complexes into the 3-sphere

This page was built for publication: Embeddability in the 3-sphere is decidable

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