41 citations · 148 across the 19 of their papers we have counts for
18 papers · 1 filter
Hard Diagrams of the Unknot
Benjamin A. Burton, Hsien-Chih Chang, Maarten Löffler +5
We present three "hard" diagrams of the unknot. They require (at least) three extra crossings before they can be simplified to the trivial unknot diagram via Reidemeister moves in…
The unbearable hardness of unknotting
Arnaud de Mesmay, Yo'av Rieck, Eric Sedgwick +1
We prove that deciding if a diagram of the unknot can be untangled using at most Riedemeister moves (where is part of the input) is NP-hard. We also prove that several natu…
On the tree-width of knot diagrams
Arnaud de Mesmay, Jessica Purcell, Saul Schleimer +1
We show that a small tree-decomposition of a knot diagram induces a small sphere-decomposition of the corresponding knot. This, in turn, implies that the knot admits a small essent…
Embeddability in is NP-hard
Arnaud de Mesmay, Yo'av Rieck, Eric Sedgwick +1
We prove that the problem of deciding whether a 2- or 3-dimensional simplicial complex embeds into is NP-hard. Our construction also shows that deciding whether a 3-…
Computing Heegaard genus is NP-hard
David Bachman, Ryan Derby-Talbot, Eric Sedgwick
We show that {\sc Heegaard Genus }, the problem of deciding whether a triangulated 3-manifold admits a Heegaard splitting of genus less than or equal to , is NP-hard. Th…
Locally Helical Surfaces have bounded twisting
David Bachman, Ryan Derby-Talbot, Eric Sedgwick
A topologically minimal surface may be isotoped into a normal form with respect to a fixed triangulation. If the intersection with each tetrahedron is simply connected, then the pi…