41 citations · 148 across the 19 of their papers we have counts for
23 papers
Spiraling and Folding: The Topological View
Jan Kynčl, Marcus Schaefer, Eric Sedgwick +1
For every , we construct two curves in the plane that intersect at least times and do not form spirals. The construction is in three stages: we first exhibit closed curves o…
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…
Link Crossing Number is NP-hard
Arnaud de Mesmay, Marcus Schaefer, Eric Sedgwick
We show that determining the crossing number of a link is NP-hard. For some weaker notions of link equivalence, we also show NP-completeness.
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-…