Computational cost of converting between 3-manifold presentations Given a 3-manifold presented as a triangulation, a Heegaard splitting, or a Dehn surgery, what is the computational cost of converting to the other two presentations? I would like Heegaard splittings to be given as a word in the standard Dehn twist generators, and Dehn surgery as a word in the standard braid group generators.
For instance, suppose we want to triangulate a Heegaard splitting. Although I can't find a good reference for this, I think it can be done in time which is linear in both the genus and the length of the Dehn word. Start with a triangulation of a handlebody such that there's a strip of triangles along each of the canonical curves. To implement a Dehn twist, glue tetrahedra along the strip so that the result is a sequence of 2-2 Pachner moves on the surface triangulation, like in this picture:
http://www.iqc.ca/~galagic/dehntriangles.jpg
What about the other directions (e.g., converting a triangulation into a Dehn surgery)? Can they also be done efficiently?
edit: to whatever extent it may matter, I am primarily interested in simplicial triangulations, i.e., a single edge may not form a loop.
 A: I believe all these translations are in principle easy. The challenge is in implementing them cleanly and efficiently; the translations can be annoying and confusing.
As you describe, to go from a Heegaard splitting
to a triangulation, it's just a matter of a sequence of Pachner moves.  If you allow (as is
usually sensible to do) non simplicial complex triangulations, where edges are allowed to form a loop in the manifold, then you can use one-vertex triangulations of the surfaces. There is only a finite set of these up to isomorphism, and the Pachner moves correspond to the one-skeleton for an equivariant cell division of Teichmuller space of the surface with a distinguished point (the vertex).   For a finitely generated group, the translation from one set of generators to another has linear cost. The same principle works here, for any
fixed genus: it's a translation from generators for the mapping class group to
a set of generators to a mapping class groupoid generated by the Pachner moves. (Lee Mosher
in particular has studied this correspondence in detail). The linearity still holds,
or at least nearly holds (this depends on the details of definitions)
 when you consider surfaces of every genus together, if you use Dehn twists 
around a system of curves where each curve only meets a bounded number of other 
curves (as is the usual convention). 
If you allow ideal triangulations for the manifold minus some finite collection of curves, you can do even better: the number of simplices needed is linear in the number of powers
of Dehn twists using standard generators.
To go in the other direction, a triangulation is practically a special case of a Heegaard splitting: a regular neighborhood
of the 1-skeleton union its complement.  If you want the handlebodies described in
standard form, it's essentially just a matter of choosing a spanning tree for the 1-skeleton and dual 1-skeleton, plus some method to give a homeomorphism from the regular neighborhood
of the spanning tree to a sphere with a set of distinugished points.
If a Heegaard diagram is described as a nonseparating system of g simple curves on the boundary of a genus g handlebody to which disks are attached in the complementary handlebody,  this can be translated into a gluing map expressed as a word in Dehn twists in a reasonably straightforward way; this also gives a Dehn surgery description.  In fact, Lickorish described a method in his paper showing that all 3-manifolds are obtained by Dehn surgery on links.  I believe the number
of powers of Dehn twists needed should be a linear function of the number of bits used to describe the
$g$ curves using either  traintracks or normal curve coordinates.  
A: You might find this thread interesting: How expensive is knowledge? Knots, Links, 3 and 4-manifold algorithms. 
I believe it's expected there should be a polynomial time algorithm to go from a triangulation to a surgery diagram or Heegaard splitting -- in particular see the Thurston and Costantino reference in the above thread.  I've been hoping to eventually flesh that out and implement it in Regina but I haven't had the time yet.  
For triangulating 3-manifolds given by Heegaard splittings, this was done by Schleimer. See his webpage: http://www.warwick.ac.uk/~masgar/Maths/twister.html there is C-code available, as well. I believe he does something quite comparable to what you describe, using layered triangulations.
