## Algorithms for essential surfaces in 3-manifolds.(English)Zbl 1012.57029

Berrick, A. J. (ed.) et al., Topology and geometry: commemorating SISTAG. Proceedings of the Singapore international symposium in topology and geometry (SISTAG), Singapore, July 2-6, 2001. Providence, RI: American Mathematical Society (AMS). Contemp. Math. 314, 107-124 (2002).
Using normal and almost normal surface theory, the authors describe several algorithms to find essential surfaces in $$3$$-manifolds, in particular algorithms to find the Kneser-Milnor decomposition of a $$3$$-manifold and the JSJ decomposition of an irreducible $$3$$-manifold.
To find the connected sum decomposition of a manifold the method can be sketched as follows:
– Start with a $$1$$-vertex triangulation of the manifold;
– Using the Euler characteristic, check if normal spheres, which are not vertex linkings, can be found at the vertices of the projective solution space;
– If such a sphere exists either it does not separate, and an $$S^2\times S^1$$ summand can be split off, or it separates. In the latter case, cut the manifold open along the sphere and crush the boundary of the two components to a point. The two manifolds thus obtained either admit a new triangulation with fewer simplices or are an $$\mathbb{R} P^3$$ or an $$L(3,1)$$ summand.
– Iterate the process until all the pieces (which are not $$S^3$$, $$\mathbb{R} P^3$$ or $$L(3,1)$$) have a $$0$$-efficient triangulation, i.e. all normal spheres are vertex linkings.
– Check which summands are nontrivial.
The method to obtain the JSJ decomposition for an irreducible 3-manifold is analogous but uses $$1$$-efficient instead of $$0$$-efficient triangulations. As a corollary, the authors remark that this method also gives a new algorithm to decide whether a knot is the unknot.
Notice that, during the above procedures, the manifold may be split along non essential surfaces, and non essential pieces are eliminated only at the end. This strategy, together with simplifications of the triangulation occurring at each step, drastically reduces the running time of the algorithms, which is exponential in the number of tetrahedra of the triangulation; indeed it takes exponential time to decide whether a given surface is incompressible.
The paper ends with an algorithm to decide whether a closed irreducible atoroidal manifold admitting a $$1$$-efficient triangulation has an embedded incompressible surface.
For the entire collection see [Zbl 1001.00029].

### MSC:

 57N10 Topology of general $$3$$-manifolds (MSC2010) 57M99 General low-dimensional topology 57M25 Knots and links in the $$3$$-sphere (MSC2010)