Computing closed essential surfaces in knot complements

Burton, Benjamin A., Coward, Alexander and Tillmann, Stephen (2013). Computing closed essential surfaces in knot complements. In: Proceedings of the Annual Symposium on Computational Geometry. 29th Annual Symposium on Computational Geometry (SoCG 2013), Rio de Janeiro, Brazil, (405-414). 17-20 June 2013. doi:10.1145/2462356.2462380

Author Burton, Benjamin A.
Coward, Alexander
Tillmann, Stephen
Title of paper Computing closed essential surfaces in knot complements
Conference name 29th Annual Symposium on Computational Geometry (SoCG 2013)
Conference location Rio de Janeiro, Brazil
Conference dates 17-20 June 2013
Proceedings title Proceedings of the Annual Symposium on Computational Geometry   Check publisher's open access policy
Journal name Proceedings of the twenty-ninth annual symposium on Computational geometry (SoCG '13)   Check publisher's open access policy
Place of Publication New York, NY United States
Publisher Association for Computing Machinery Inc.
Publication Year 2013
Year available 2013
Sub-type Fully published paper
DOI 10.1145/2462356.2462380
ISBN 9781450320313
ISSN 1055-6257
Start page 405
End page 414
Total pages 10
Collection year 2014
Language eng
Formatted Abstract/Summary
We present a new, practical algorithm to test whether a knot complement contains a closed essential surface. This
property has important theoretical and algorithmic consequences.  However systematically testing it has until now
been infeasibly slow, and current techniques only apply to specic families of knots. As a testament to its practicality,
we run the algorithm over a comprehensive body of 2979 knots, including the two 20-crossing dodecahedral knots,
yielding results that were not previously known.  The algorithm derives from the original Jaco-Oertel framework,
involves both enumeration and optimisation procedures, and combines several techniques from normal surface theory. This represents substantial progress in the practical implementation of normal surface theory. Problems of this kind have a doubly-exponential time complexity; nevertheless, with our new algorithm we are able to solve it for a large and  comprehensive class of inputs. Our methods are relevant for other difficult computational problems in 3-manifold theory, ranging from testing for Haken-ness to the recognition problem for knots, links and 3-manifolds.
Subjects 2605 Computational Mathematics
2608 Geometry and Topology
2614 Theoretical Computer Science
Keyword Computational topology
Essential surface
Incompressible surface
Knot theory
Normal surface
Q-Index Code E1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Conference Paper
Collections: School of Mathematics and Physics
Official 2014 Collection
Version Filter Type
Citation counts: Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Thu, 28 Nov 2013, 16:56:26 EST by System User on behalf of Examinations