Algorithmic construction and recognition of hyperbolic 3-manifolds, links, and graphs

This survey focuses on the computational complexity of some of the fundamental decision problems in 3-manifold theory. The article discusses the wide variety of tools that are used to tackle these problems, including normal and almost surfaces, hierarchies, homomorphisms to finite groups, and hyperbolic structures.

We explicitly construct small triangulations for a number of well-known 3-dimensional manifolds and give a brief outline of some aspects of the underlying theory of 3-manifolds and its historical development.

We give a more geometric approach to an algorithm for deciding whether two hyperbolic 3-manifolds are homeomorphic. We also give a more algebraic approach to the homeomorphism problem for geometric, but non-hyperbolic, 3-manifolds.

Finding a totally geodesic surface, an embedded surface where the geodesics in the surface are also geodesics in the surrounding manifold, has been a problem of interest in the study of 3-manifolds. This has especially been of interest in hyperbolic 3-manifolds and knot complements, complements of piecewise-linearly embedded circles in the 3-sphere. This is due to Menasco-Reid's conjecture stating that hyperbolic knot complements do not contain such surfaces. Here, we present...

In this work we present a complete (no misses, no duplicates) census for closed, connected, orientable and prime 3-manifolds induced by plane graphs with a bipartition of its edge set (blinks) up to $k=9$ edges. Blinks form a universal encoding for such manifolds. In fact, each such a manifold is a subtle class of blinks, \cite{lins2013B}. Blinks are in 1-1 correpondence with {\em blackboard framed links}, \cite {kauffman1991knots, kauffman1994tlr} We hope that this census be...

In this survey we discuss how geometric methods can be used to study topological properties of 3-manifolds such as their Heegaard genus or the rank of their fundamental group. On the other hand, we also discuss briefly some results relating combinatorial descriptions and geometric properties of hyperbolic 3-manifolds.

We describe several methods to construct minimal foliations by hyperbolic surfaces on closed 3-manifolds, and discuss the properties of the examples thus obtained.

We give a bounded runtime solution to the homeomorphism problem for closed hyperbolic 3-manifolds. This is an algorithm which, given two triangulations of hyperbolic 3-manifolds by at most $t$ tetrahedra, decides if they represent the same hyperbolic 3-manifold with runtime bounded by \[ 2^{2^{t^{O(t)}}}.\] We do this by first finding a hyperbolic structure on each manifold given as a geometric triangulation and then comparing the two as geometric manifolds.

This is a survey paper on algorithms for solving problems in 3-dimensional topology. In particular, it discusses Haken's approach to the recognition of the unknot, and recent variations.

Starting from the (apparently) elementary problem of deciding how many different topological spaces can be obtained by gluing together in pairs the faces of an octahedron, we will describe the central role played by hyperbolic geometry within three-dimensional topology. We will also point out the striking difference with the two-dimensional case, and we will review some of the results of the combinatorial and computational approach to three-manifolds developed by different ma...