Editing Computational topology (section)

==== Conversion algorithms ====

* [[SnapPea]] implements an algorithm to convert a planar [[Knot (mathematics)|knot]] or [[Knot (mathematics)#knot diagram|link diagram]] into a cusped triangulation.  This algorithm has a roughly linear run-time in the number of crossings in the diagram, and low memory profile.  The algorithm is similar to the Wirthinger algorithm for constructing presentations of the [[fundamental group]] of link complements given by planar diagrams. Similarly, SnapPea can convert [[surgery theory|surgery]] presentations of 3-manifolds into triangulations of the presented 3-manifold.
* D. Thurston and F. Costantino have a procedure to construct a triangulated 4-manifold from a triangulated 3-manifold.  Similarly, it can be used to construct surgery presentations of triangulated 3-manifolds, although the procedure is not explicitly written as an algorithm in principle it should have polynomial run-time in the number of tetrahedra of the given 3-manifold triangulation.<ref>{{cite journal |doi=10.1112/jtopol/jtn017 |title=3-manifolds efficiently bound 4-manifolds |year=2008 |last1=Costantino |first1=Francesco |last2=Thurston |first2=Dylan |s2cid=15119190 |journal=[[Journal of Topology]] |volume=1 |issue=3 |pages=703–745 |arxiv=math/0506577 }}</ref>
* S. Schleimer has an algorithm which produces a triangulated 3-manifold, given input a word (in [[Dehn twist]] generators) for the [[mapping class group]] of a surface.  The 3-manifold is the one that uses the word as the attaching map for a [[Heegaard splitting]] of the 3-manifold. The algorithm is based on the concept of a ''layered triangulation''.