Author(s):

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

Title: 
Embeddability in the 3 sphere is decidable

Affiliation 
IST Austria 
Abstract: 
We show that the following algorithmic problem is decidable: given a 2dimensional simplicial complex, can it be embedded (topologically, or equivalently, piecewise linearly) in ℝ3? By a known reduction, it suffices to decide the embeddability of a given triangulated 3manifold X into the 3sphere S3. The main step, which allows us to simplify X and recurse, is in proving that if X can be embedded in S3, 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 S3 nX with length bounded by a computable function of the number of tetrahedra of X.

Keywords: 
Simplicial complex; 3manifold; Embedding

Conference Title:

SoCG: Symposium on Computational Geometry

Conference Dates:

June 811, 2014

Conference Location:

Kyoto, Japan

ISBN:

9781450325943

Publisher:

ACM

Date Published:

20140601

Start Page: 
78

End Page:

84

Sponsor: 
ERC Advanced Grant No. 267165; Grant GRADR Eurogiga GIG/11/E023 (SNSFPP00P2138948); Swiss National Science Foundation (SNSF200020138230)

URL: 

DOI: 
10.1145/2582112.2582137

Notes: 
We thank David Bachman, Ryan DerbyTalbot, and William Jaco for very helpful conversations. We further thank Tony Huynh for kind answers to our questions, Helena Nyklova ́ for help with many pictures, Isaac Mabillard for remarks on a preliminary writeup of the algorithm for EMBED3→3, and an anonymous reviewer for useful comments.

Open access: 
yes (repository) 