There is a method, attributed variously to Kashaev and to Dylan Thurston, to turn a non-split link diagram in the three-sphere into a partially-ideal triangulation of the link exterior in time polynomial in the number of crossings, called the octahedral decomposition. This method only uses four tetrahedra per crossing. However, to my knowledge there is no known explicit method for doing the opposite—turning a triangulation of a link exterior in the three-sphere into a diagram for an (not “the”) associated link. Neil Hoffman and I recently noticed, as several experts have before us, that several families of knots show that this link diagram reconstruction problem, interpreted naively, is not even in PSPACE. We are working with Eric Sedgwick and Saul Schleimer to show the naive problem is in EXPTIME. We are hopeful that we can retool the notion of “link diagram” to afford a polynomial-time solution to link diagram reconstruction. We are somewhat less hopeful that we can make the associated algorithm amenable to implementation.