Algorithms for Finding Proper Essential Surfaces in 3-Manifolds

In this paper, we present an algorithm which, for a given compact orientable irreducible boundary irreducible 3-manifold $M$, verifies whether $M$ contains an essential orientable surface (possibly, with boundary), whose genus is at most $N$. The algorithm is based on Haken's theory of normal surfaces, and on a trick suggested by Jaco and consisting in estimating the mean length of boundary curves in an unknown essential surface of a given genus in the given manifold.