State of the Art in Algorithmic Knot Simplification – Computational Topology

Question

Question: Given a `hard' diagram of a knot, with over a hundred crossings, what is the best algorithm and software tool to simplify it? Will it also simplify virtual knot diagrams, tangle diagrams, and link diagrams?

The reason that I ask this question is that I have been reading:

Lewin, D., Gan O., Bruckstein A.M.,
TRIVIAL OR KNOT: A SOFTWARE TOOL AND ALGORITHMS FOR KNOT SIMPLIFICATION,
CIS Report No 9605, Technion, IIT, Haifa, 1996.

This technical report is notable not only for its mathematical content, but also for its back-story. It was the undergraduate research project of Daniel M. Lewin, who was a few years later to found Akamai Technology which today manages 15-20% of the world's web traffic, to become a billionaire, and to be the first person to be murdered on 9-11. He is the subject of the 2013 biography No Better Time: The Brief, Remarkable Life of Danny Lewin, the Genius Who Transformed the Internet by Molly Knight Raskin, published by Da Capo Press.

The algorithm used by Bruckstein, Lewin, and Gan doesn't use 3-dimensional topology or normal surface theory, but instead relies on an algorithmic technique called simulated annealing. I suspect that this same technique could be used effectively for other problems in algorithmic topology.

To the best of my knowledge, Bruckstein, Lewin, and Gan's algorithm is unknown to the low-dimensional topology community, but it works very well. Despite it having been written a long time ago, I wonder (for reasons beyond mere curiousity) how far it is from being state of the art today.

Answer 1

Here is one piece of software, the Book Knot Simplifier, by Maria Andreeva, Ivan Dynnikov, Sergey Koval, Konrad Polthier, and Iskander Taimanov, largely based on Dynnikov's work:

Here we offer a set of tools for manipulating knots and links in the three-space by using the three-page presentation of links, which was proposed and developed by I. Dynnikov in [1][2][3].

The approach is based on a simple and very well known observation that every link in the three-space is topologically equivalent to a link that lies entirely in a three-page book, i.e. the union of three half-planes with common boundary. Though being not convenient for human perception, this way of presenting links seems to be very efficient for handling knots by computer. It provides a very quick way from a combinatorial description of a link to its three-dimensional presentation. A three-page link admits a lot of transformations that preserve its isotopy class and can be easily found. This fact is used in the knot simplifying tool included herein.

        _{The unknot with 31 crossings.}