Embeddability in the 3-Sphere is decidable Journal Article


Author(s): Matoušek, Jiří; Sedgwick, Eric; Tancer, Martin; Wagner, Uli
Article Title: Embeddability in the 3-Sphere is decidable
Affiliation IST Austria
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 R3? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold X into the 3-sphere 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, that is, an essential curve in the boundary of X bounding a disk in S3 \ X with length bounded by a computable function of the number of tetrahedra of X.
Keywords: Computational topology; Normal surfaces; Embeddability; 3-manifolds
Journal Title: Journal of the ACM
Volume: 65
Issue 1
ISSN: 0004-5411
Publisher: ACM  
Date Published: 2018-01-01
Start Page: Article number: 5
URL:
DOI: 10.1145/3078632
Notes: This research was supported by the European Research Council (ERC Advanced Grant No. 267165). The research by Jiří Matoušek was also partially supported by the European Science Foundation (Grant GRADR Eurogiga GIG/11/E023). The research by Uli Wagner was supported by the Swiss National Science Foundation (Grants SNSF-PP00P2-138948 and SNSF-200020-138230). Part of this research was done while Martin Tancer was affiliated with Institutionen för matematik, Kung-liga Tekniska Högskolan, Sweden, and with IST Austria, respectively; during these periods, his work was supported by a Göran Gustafsson postdoctoral fellowship and by an ISTFELLOW scholarship (Marie Skłodowska-Curie Action COFUND Grant 291734), respectively.
Open access: yes (repository)
IST Austria Authors
  1. Uli Wagner
    50 Wagner
Related IST Austria Work