requiring $\Omega(n^2)$ homotopy moves to be simplified. The proof of Theorem 7.2.1 builds on a strong structural result of Hass and Scott [93] on the self-intersections of closed curves on surfaces, and involves repeatedly identifying so-called singular bigons and providing a way to simplify those with a controlled number of moves. This requires some intricate bookkeeping: while bigons in general are easy to simplify using homotopy moves, here the bigons are degenerate enough that we need to be very careful of not making one more complicated during the process of undoing it.

The answer to the third question is positive, and follows from independent work of de Graaf and Schrijver [48] and Hass and Scott [94]. In a follow-up paper with Hsien-Chih Chang [A], we refined these techniques to provide a polynomial upper bound for the third question, and at the same time generalize the results for the other questions to the more general setting of multicurves.

**Theorem 7.2.2 ([A]).** • On an orientable surface of genus $g$ with non-empty boundary, any multi-curve with $n$ self-intersections can be tightened monotonically using $O((g+b)n^3)$ homotopy moves.

• On an orientable surface without boundary that is not a torus, any multi-curve with $n$ self-intersections can be tightened monotonically using $O(n^5 \log^3 g/g^2 + gn^3)$ homotopy moves.

Furthermore, the moves can be computed efficiently, thus also yielding the first algorithms to put a multi-curve in minimal position in polynomial time. It is a striking fact that this theorem does not apply to the torus, as problems on tori tend generally to be easier than on surfaces of higher genus. The reason here is that our arguments leverage hyperbolic geometry, which has distinctive features which are lacking for the Euclidean geometry that a torus can naturally be endowed with. A second tool that we rely on to prove Theorem 7.2.2 is a combinatorial model that we call a *pipe system* and that gets iteratively refined as the tightening process happens. It originates from recent algorithms to draw planar graphs with restrictions [35, 40, 71].

Let us now provide some additional motivation for Theorem 7.2.2 by explaining its connections to **electrical transformations** on (embedded) graphs. Given $G$ an embedded graph on a surface $S$, the set of electrical moves pictured in Figure 7.3 provides rules to transform $G$ into another graph<fnref n="1" />. The origin of these moves (and of their names) is that they provide simplification rules to compute the equivalent resistances of resistance networks (see for example [3]), but these moves also have numerous applications in other fields. For example they are used in Steinitz’s original proof of his theorem that 3-connected planar graphs coincide with the graphs of three-dimensional convex polyhedra [174], or they are prominently featured in the structural theory of linkless graphs [160]. In many

<footnote n="1">1. We focus in this chapter on *embedded* electrical moves, i.e., we insist that faces pictured in Figure 7.3 be empty for the move to be allowed. The more general theory is more subtle, we refer to the thesis of Chang [34] for more details.</footnote>
<figure><img src="image_42.png" /><figcaption>FIGURE 7.3 – The four electrical moves (top), their effect on the medial graph (middle) and their similarity to homotopy moves (bottom)</figcaption></figure>
applications, the goal is to simplify as much as possible a graph using these transformations, i.e., transform the graph into a graph with a minimal number of vertices.

The connection between electrical transformations and homotopy moves operates via the *medial graph*, which obtained from an embedded graph by placing a vertex on each edge, and connecting two vertices placed on adjacent edges, where two edges are considered adjacent if they occur consecutively on a facial cycle. Note that a medial graph has all its vertices of degree 4, and thus can be interpreted as a multicurve. As pictured in Figure 7.3, electrical transformations *almost* amount to homotopy moves on this multicurve. The key difference is that the second homotopy move is different, instead of an $H_2$ move we get what we denote by an $E_2$ move, which yields interesting difficulties.

Our Theorem 7.2.2 can be applied to the problem of simplifying an embedded graph using electrical transformations as much as possible as follows. We first compute the medial graph. Then we compute a monotonic sequence of homotopy moves to tighten these curves, and apply them, until we encounter an $H_2$ move. At this stage, we apply the $E_2$ move instead. This completely rearranges the multicurve and their homotopy classes, but we can start the process again: compute a new monotonic sequence of homotopy moves, and apply them until we encounter an $H_2$ move, etc. Since the $E_2$ moves reduces the number of self-intersections by 1, this process only lasts for a polynomial time, and thus we obtain a polynomial sequence of electrical transformation moves to simplify our graph. At this stage, two remarks are in order:

* It is not clear that we are done. It could be that we obtain an embedded graph, and the corresponding medial multicurve is in minimal position from the perspective of homotopy moves, but that applying a well-chosen $E_2$-move in reverse shuffles everything and provides a way for further simplification. It is a delicate theorem of Chang, Cossarini and Erickson [33] that this actually does not happen.

* For this argument to work, it is crucial that we work with a *monotonic* sequence of homotopy moves, and thus that we have at our disposition Theorem 7.2.2 instead of just Theorem 7.2.1. Indeed, in a non-monotonic sequence, a move $H_2$ increasing the number of vertices would have to be exchanged with an increasing $E_2$, completely shuffling the topology of the curves, and there would be no way of controlling the resulting number of moves.

Thus, the previous discussion yields the following corollary.

**Corollary 7.2.3.** [*A] Any graph embedded on a surface can be reduced as much as possible using electrical transformations in polynomial time.

This result also applies in a setting with *terminals*, i.e., vertices that have to be left invariant by the electrical transformations, although this involves some subtleties regarding *terminal-leaf reductions* that we will not discuss here (we refer to [A, Section 5.3]). Before our work, the result of Corollary 7.2.3 was only known in the setting of planar graphs with up to four terminals [53].
CHAPTER 8

# Other works on knots and 3-manifolds

## 8.1 Treewidth of knots

The material in this section comes from the article [F] which was co-authored with Jessica Purcell, Saul Schleimer and Eric Sedgwick.

As we surveyed in Chapter 6, computational problems involving knots are generally hard, or at least they seem to be in the sense that we do not know efficient algorithms to solve them. In the past decades, a vast literature in theoretical computer science was devoted to developing new angles of attacks to solve hard problems, primarily focusing on two directions: approximation algorithms (see for example Vazirani [180]) on the one hand, and parameterized algorithms (see for example Cygan et al. [45]) on the other hand. This section is devoted to the latter approach. A widely beloved parameter enabling tractability of hard problems is the *treewidth* of a graph: in intuitive terms, it measures quantitatively how close to a tree a graph is. This parameter is very relevant for algorithmic purposes since most algorithmic problems are easy to solve on trees (generally using some form of dynamic programming), and therefore can also be solved efficiently for graphs that "look like trees". More precisely, many **NP**-hard problems are FPT when parameterized by the treewidth, i.e., can be solved on graphs of treewidth at most *k* in time $f(k)poly(n)$, where *f* is some computable function.

Parameterized algorithms can be applied to problems in knot theory via knot diagrams. Indeed, a knot diagram, once one forgets the information of which strand goes over or under at a crossing, is merely a 4-valent planar graph, with a well-defined treewidth, and thus
one can hope that standard knot-theoretical questions become easier under the hypothesis
that this treewidth is small. Unfortunately, even this is unknown for the most important
questions: in particular it is unknown whether UNKNOT RECOGNITION can be solved in
polynomial time when the input diagram has fixed treewidth (the best known result is such
an algorithm for inputs of treewidth 2 [17]). Yet this approach is known to be successful
for a host of easier questions, notably for the problem of computing a wide family of
knot invariants, such as the Jones polynomial [130], the HOMFLY-PT polynomial [22] and
more refined versions of those [131]. Note that a well-known conjecture posits that the
Jones polynomial detects the unknot, which thus would yield a positive answer to the FPT
status of UNKNOT RECOGNITION parameterized by the treewidth.

A question that immediately arises from these endeavors is to understand which knots
admit knot diagrams of small treewidth. The question was asked in the reverse direction
by Burton [21]: does there exist a constant *c* such that every knot *K* admits a diagram of
treewidth at most *c*? Makowsky and Mariño asked a similar question in [130]. The motiva-
tion is clear: if the answer is positive, and furthermore such a small-treewidth diagram can
be computed efficiently, then the previous parameterized algorithms provide a very plausi-
ble approach towards solving UNKNOT RECOGNITION in polynomial time. Of course, the
consensus was that the answer should be negative, but while it is easy to build diagrams
of a given knot with arbitrarily high treewidth, proving the nonexistence of small treewidth
diagrams for a given knot seems much harder.

In a joint work with Jessica Purcell, Saul Schleimer and Eric Sedgwick, we resolved
the question in the negative. A *torus knot* $T_{p,q}$ is a knot defined by taking the standard
embedding of a torus as a torus of revolution in $\mathbb{R}^3$, and considering a curve winding *p*
times around a circle in the interior of the torus and *q* times around the axis of symmetry.

**Theorem 8.1.1.** [F] Any diagram of the torus knot $T(k, k + 1)$ has treewidth $\Omega(k)$.

Our theorem is actually more general, and provides topological criteria for a knot to
not admit a diagram of low treewidth, in terms of its *bridge number* and the existence
of *incompressible planar surfaces* in its complement, we refer to the article [F] for more
details.

The idea of the proof is to connect the very combinatorial notion of treewidth to more
topological notions that have been heavily investigated in knot theory. An impressionis-
tic description is as follows: we assume by contradiction that a torus knot $T(k, k + 1)$
admits a diagram of low treewidth and reach a contradiction. Famous work of Seymour
and Thomas [170] shows that a planar graph of low treewidth can be interpreted geometri-
cally as a graph which can be swept by disjoint simple closed curves such that each of these
closed curves intersects the graph a bounded number of times, and the family that they form
nests in the shape of a tree. When the input graph is a knot diagram, we show that these
closed curves can be lifted to spheres in $\mathbb{R}^3$, yielding what we call a *sphere decomposition*:
a family of disjoint spheres in $\mathbb{R}^3$, each of them having small intersection with the knot
*K*, nested in a tree-like fashion, and such that the layout of the knot with respect to these
spheres is very constrained. The last ingredient is to show that such a sphere decomposition is very closely related to the classical notion of a *Heegaard splitting* of a 3-manifold. More precisely, we show how to upgrade a sphere decomposition into a *multiple Heegaard splitting* (see Hayashi and Shimokawa [96]) for the knot $T(k, k+1)$ in $\mathbb{R}^3$, and the low treewidth hypothesis implies that the *complexity* of this splitting has to be low. But leveraging the work of Hayashi and Shimokawa [96], we show that such a low-width splitting would prove the existence of some particular surfaces in the knot complement, which are known not to exist for torus knots (and other families of knots), concluding the proof.

## 8.2 Hardness of the link crossing number

> The material in this section comes from the article [B] which was co-authored with Marcus Schaefer and Eric Sedgwick.

The *crossing number* of a knot or a link is the minimum number of intersections in a diagram of the knot or link. While it is arguably the most natural numerical invariants to consider for knots, and indeed most knot tables classify those by their crossing number [23], it is also famously intricate, as it is hard to relate the crossing number to topological properties of the knots. For example, it is a famous open question whether $cr(K_1#K_2) = cr(K_1) + cr(K_2)$, where # denotes the connected sum of knots (see Lackenby [118] for the best known bounds on this question). However, the discovery of the Jones polynomial in the 80s led to renewed interest in the crossing number and more generally in a diagrammatic approach to knot theory, in particular because it led to easy proofs of the famous Tait conjectures (we refer for example to the book of Kaufmann [104]).

With Marcus Schaefer and Eric Sedgwick [B], we undertook the study of the crossing number of knots and links from a computational perspective. Our path here was guided by the analogous notion in graph theory: the *crossing number* of a graph $G$ is the minimum number of crossings of a drawing of $G$ in the plane. The crossing number of graphs is also a notoriously delicate quantity. For example, computing it is NP-hard [75], and the value of the crossing number of complete or complete bipartite graphs is famously unknown [165]. This suggests trying to encode a graph crossing number in an instance of computing the crossing number of a knot or a link, which we succeeded in doing, establishing the following theorem.

**Theorem 8.2.1.** [B] Let $L$ be a link described by a sequence of segments (or a diagram) and $k$ be an integer. Deciding whether $L$ has crossing number at most $k$ is NP-hard.
<figure><img src="image_43.png" /><figcaption>FIGURE 8.1 – A naive reduction from graphs to links.</figcaption></figure>

Let us observe that this is far from telling a complete story on the complexity of computing the crossing numbers of knots and links. Indeed, the best algorithm known for this problem seems to be to try all the possible diagrams up to *k* crossings, and for each of them test whether it is equivalent to the input link, using the galactic algorithms mentioned in Chapter 6. Bridging the gap between the lower and upper bound seems like a formidable open problem. Furthermore, Theorem 8.2.1 only applies to links, for the same reason as most of our reductions in Chapter 6: links provide more rigidity and control than knots, making it easier to devise reductions. Proving an analogue of Theorem 8.2.1 for knots, or even for links with a fixed number of connected components, seems out of reach of our techniques.

The proof of Theorem 8.2.1 follows an expected pattern until one encounters an unexpected difficulty, which I would like to explain here, leaving the interested reader to check its resolution in the article [B]. We start from an instance of the graph crossing number problem that is known to be **NP**-hard and try to transform it into a link, so that the crossings of the link necessarily mirror the crossings of the graph. A naive version of this reduction is pictured in Figure 8.1, where we see a first difficulty: the topological type of the link that we obtain will depend on the rotation scheme of the starting graph. Therefore, we want to start from an instance of the graph crossing number that is **NP**-hard even when fixing the rotation scheme, we chose one due to Muñoz, Unger and Vrt'o [144].

Then, we want to argue that a diagram of the link with a minimal number of crossings corresponds to a drawing of the original graph. This is a matter of *rigidity*: the goal is to show that the flexibility in diagrams of the link exactly mirrors the flexibility of the graph drawing. In order to enforce this rigidity, an important trick that is used in many graph-theoretical reductions on crossing numbers is to put weights on edges, which can easily be simulated using multiple edges (if these are forbidden, one can subdivide those). Indeed, in a drawing of a graph of minimal crossing number, one can always arrange parallel edges so that they are drawn just next to each other, since drawing those in a small neighborhood
of the one with a minimal number of crossings does not increase the crossing number. Yet interestingly, this trick is hard to apply in the context of links, as a component might self-intersect in the optimal diagram, and copies of self-intersecting components yield a crossing number growing quadratically with the number of components. Basically, we were unable to argue that in a crossing-minimal drawing, all copies of a knot would have to be drawn the same way. In order to circumvent this issue, we still rely on a weighting scheme, but change the equivalence notion that we use for knots to argue about the weighting, before ultimately connecting back this new equivalence notion with the classical one.
<figure><img src="image_44.png" /></figure>
# CHAPTER 9

## Perspectives

We conclude this habilitation thesis with some perspectives on ongoing and future research directions. We start by highlighting ongoing work with PhD and Masters students, and then outline further research topics. In line with the organization of this document, we place a specific emphasis on the open problems stemming from the three lines of research presented in Chapters 4, 5 and 6.

### 9.1 Work with students

I have worked on numerous occasions with PhD students, which are identified with stars in my list of publications. In particular, the articles [A, I] and [C, G, J] are the results of long collaborations respectively with Hsien-Chih Chang and Tim Ophelders during their PhD theses.

I am currently co-supervising three PhD students, and for two of them I have also (co-) supervised their master theses.

With Niloufar Fuladi, a PhD student co-supervised with Éric Colin de Verdière and Alfredo Hubbard, we investigate topics in the continuation of the results on intersections of embedded graphs and shortest path embeddings presented in Chapter 7. As mentioned in that chapter, the directions are multiple as most questions one can ask remain wide open. Our first focus is on non-orientable surfaces, which were a blind spot of our initial work [M]. The following preliminary results have already been obtained during Niloufar Fuladi's master thesis: first, there is a subtle flaw in Negami's proof that two graphs embeddable on a non-orientable surface of genus $g$ can be reembedded so as to cross $O(gn_1n_2)$ times, which we corrected using a different argument. Second, we were able to generalize the fourth item of Theorem 7.1.4 to the setting of non-orientable surfaces by providing a new decomposition scheme for those, akin to the octagonal decomposition defined by
É. Colin de Verdière and Erickson [38] for orientable surfaces. The next natural direction, topic of ongoing work that is nearing conclusion, is to obtain an analogue of Theorem 7.1.1 for non-orientable surfaces and non-orientable canonical systems of loops. Here, the main starting point is a recent result of Schaefer and Stefankovič [166] providing very strong bounds on how to embed a non-orientable map with a geometrized model of crosscaps.

With Jean Chartier, a PhD student co-supervised with Laurent Hauswirth and Stéphane Sabourau, we investigate questions related to min-max techniques akin to those presented in Chapter 5 on homotopy height. As we explained in that chapter, optimal homotopies and their higher dimensional generalizations (sweep-outs) are widely studied in minimal surface theory as they provide a powerful tool to prove the existence of geodesics, or more generally minimal surfaces. These techniques have been under the spotlight in recent years, leading to the resolution of longstanding conjectures such as the Willmore conjecture [133] or Yau's conjecture [173]. Yet many open questions remain, even in two dimensions. We pursue two directions. First, while geodesics can be proved to exist using minmax techniques, no tools seem to exist to compute those, even in metric structures which should be amenable to computation. For instance, a theorem of Pogorelov [153] proves that there always exist at least three distinct simple *quasi-geodesics*<fnref n="1" /> on convex polyhedra, yet it is an open problem to compute such a quasi-geodesic in polynomial time. As mentioned in Demaine, Hertserberg and Ku [52], even the existence of an algorithm is not clear, since there is no obvious bound on the number of edges that these geodesics intersect. We are investigating how minmax techniques can be made algorithmic to actually compute these quasi-geodesics. In a different direction, an open question of Hass and Morgan [92] asks whether any Riemannian 2-sphere possesses a geodesic *net* with three faces, i.e. an embedded graph with three faces where each edge is a geodesic and the angles at each vertex are balanced (i.e., the sum of vectors of norm 1 tangent to each incident edge is 0). They proved the existence of such a *net* when the manifold has positive curvature, but the argument does not generalize to a curvature-free setting. Our aim is to develop min-max techniques to capture the existence of such objects.

With Corentin Lunel, a masters student who is now starting a PhD thesis co-supervised with Éric Colin de Verdière and Pierre Dehornoy, we pursue the work described in Chapter 8 on treewidth of knots. The main result of our article [F] requires quite a bit of topological background, in the form of the reliance on Hayashi-Shimokawa [96], as it aims at proving the *non-existence* of some topological sweep-out of the knot, and proving non-existence is often harder than proving existence. Structural graph theory provides tools to alleviate this difficulty, in the form of *obstructions* to small decompositions. For example, such an obstruction for branch-width is a *tangle* (completely unrelated to the knot-theoretical concept bearing the same name), and it works like this: a graph has branch-width at least *k* if and only if it admits a tangle of size *k*. This turns the problem of lower-bounding the

<footnote n="1">1. A quasi-geodesic is a geodesic except at the singular points of the polyhedron, where it is required to form an angle at most $\pi$ on both sides.</footnote>
branchwidth upside down, instead of proving the non-existence of a specific branch decomposition, we "just" have to prove the existence of a tangle. The main result of the master thesis is to properly define a topological version of this concept of tangle in order to recover Theorem 8.1.1. The technical aspects of this construction build on an unexpected connection with the tools used by Pardon [149] to bound from below another invariant called the *distortion* of the knot. During his PhD thesis, we aim at developing our understanding of this connection between structural graph theory and knot theory to develop new algorithmic and combinatorial tools surrounding small-width decompositions of knots.

## 9.2 Further research directions

**Algorithms for graphs on surfaces.** In Chapter 4, we saw that topological ideas and algorithms can be crucial when developing algorithms for graphs embedded on surfaces: our approximation algorithm for the very combinatorial in nature MULTICUT problem relies under the hood heavily on topological primitives such as covering spaces and homotopic shortest paths or cycles. A natural extension of this chapter is to develop exact or approximate algorithms for other algorithmic problems, where geometric and topological ingredients can prove relevant. Here, a great pool of problems comes from problems for which efficient algorithms are known for planar graphs. While this line of work has been very active in the past decades, leading to extensive algorithmic techniques for graphs on surfaces for problems involving shortest paths [24], flows [29] or cuts [28], there are still many remaining open problems. For example, there is an $n^{O(g)}$ algorithm to compute an optimal SPARSEST CUT for graphs embedded on orientable surfaces of genus $g$ [151] (generalizing the planar algorithm of Park and Philips [150]), but it is open whether the problem is fixed parameter tractable with respect to the genus. The MAX CUT problem is famously solvable in polynomial time for planar graphs [87], and this has been generalized for unweighted surface-embedded graphs in [73], but a general, combinatorial algorithm is still elusive. Computing the BRANCHWIDTH of a planar graph is solvable in polynomial time [170], but generalizing the algorithm to any other surface (even the projective plane or the torus) is still open (see Inkmann [99] for an interesting discussion of the challenges involved). In Chapter 4, we also developed techniques towards proving lower bounds for problems for graphs embedded on surfaces, and I am hopeful that our 4-Regular Graph Tiling problem might be used as a general reduction tool for more problems involving non-planar graphs.

Besides these classical algorithmic problems, it is also striking that many algorithmic questions specific to decompositions of graphs embedded on surfaces remain very unexplored. While our work [D] pretty much settled the exact parameterized complexity of the SHORTEST CUT GRAPH problem, it is still a tantalizing question whether we can improve on the $O(\log^2 g)$-approximation algorithm of Erickson and Har-Peled [63]. Other types of decompositions yield equally open questions. For example, a pants decomposition is a family of closed curves cutting a surface into a family of *pairs of pants*, i.e., spheres with
three boundaries. It is unknown whether computing the shortest pants decomposition of a surface is doable in polynomial time or whether the problem is NP-hard. Strikingly, this even seems to be the case in the case of the Euclidean plane with boundaries (see Eppstein [62]). Similarly, while, as we mentioned in Chapter 7, one can compute efficiently a canonical system of loops for a surface-embedded graph with good bounds on its length, the complexity of the problem of computing the shortest one is still unknown (see Erickson and Whittlesey [64]). A more general question is to investigate the best algorithms for the very general SHORTEST MAP EMBEDDING problem presented in Chapter 4: while it is W[1]-hard, it seems plausible that a fixed parameter tractable approximation scheme similar to the one we presented for MULTICUT could exist.

**Homotopy Height and sweep-outs.** The main question that motivated most of the work presented in Chapter 5 is still open: can we compute the HOMOTOPY HEIGHT of a planar graph (i.e., any of the presented variants) in polynomial time? An even easier question also begs to be answered: in Section 5.4, we saw that a variant of the problem is fixed-parameter tractable when parameterized by the output, but the algorithm is unknown. Figuring out such an algorithm, even for the small values of the output, is a natural first step towards progress. A more disguised perspective is the following one: homotopy height can be perceived as an analogue of path-like width parameters (such as path-width or cut-width) with more topological structure: at any step of the decomposition, both sides of the decomposition form topological disks. In the case of tree-like width parameters, such a strong topological structure is already present for free for branch decompositions, as was demonstrated by Seymour and Thomas [170], and this was efficiently leveraged in order to design improved algorithms, see for example the sphere-cut decompositions introduced in [57]. Could it be that the topological structure of homotopy height makes it the correct parameter to design parameterized algorithms for specific problems on planar graphs?

As discussed in Chapter 5, one reason to be optimistic that HOMOTOPY HEIGHT may be solvable in polynomial time is that BRANCHWIDTH is, and they display a similar topological structure. The polynomial-time algorithm for BRANCHWIDTH on planar graphs leverages deep results in Robertson-Seymour theory [161], and developing an analogue of those for linear sweep-outs is a natural direction. Furthermore, our study of HOMOTOPY HEIGHT was partly motivated by similar Riemannian questions on the existence and the length of geodesics on spheres, and it turns out that tree-like sweepouts are also relevant for such questions, see for example Balacheff [8], Guth [84] and Liokumovitch [129]. In ongoing work with Alfredo Hubard and Francis Lazarus, we leverage the strong structural theory underlying branchwidth on planar graphs to prove new results on the geometry of Riemannian 2-spheres and obtain improved bounds on the lengths of their geodesics.

**Algorithms and hardness in 3 dimensions.** As the attentive reader probably noticed, none of the key questions mentioned in the introduction of Chapter 6 was actually solved in that chapter, and for the fundamental problems of UNKNOT RECOGNITION, KNOT EQUIVALENCE or UNKNOTTING NUMBER, the gaps between the computational lower bounds and upper bounds are still significant and beg to be investigated further. Let us insist again
that for UNKNOTTING NUMBER, no lower bound is known but the problem is not even known to be decidable: from that perspective, a key natural step for our hardness reductions is to strengthen them so that they apply to *knots* instead of *links*, thus bridging the gap between UNLINKING NUMBER and UNKNOTTING NUMBER. While we succeeded to do so for the problem of finding the optimal number of Reidemeister moves to untangle an unknot, new techniques seem to be required as our arguments currently rely heavily on linking numbers. On the side of upper bounds, at the time of writing, it is expected that the new quasi-polynomial time algorithm for UNKNOT RECOGNITION announced by Lackenby [123] will pave the way towards a host of new results in algorithmic knot theory. Yet, as a polynomial-time algorithm still seems out of reach, a natural line of inquiry lies here again on parameterized algorithms: given a knot diagram of bounded treewidth, can we detect in polynomial time whether it is an unknot? This question seems to be still open (see [17] for an algorithm for knot diagrams of treewidth 2), despite the fact that many knot invariants are fixed parameter tractable when parameterized by the treewidth, such as the Jones polynomial [130] (which is conjectured to detect the unknot), the HOMFLY-PT polynomial [22] or some quantum knot invariants [131]. A fascinating open question is whether stronger invariants of homological nature, such as Khovanov Homology [106] or Knot Floer Homology [148, 156] can also be computed in polynomial time for knot diagrams of bounded treewidth– this would be particularly interesting since those are known to detect the unknot [113] (see Bar-Natan [9] for a proposed approach).

Finally, it is also worthwhile to work the other way around and try to identify simple 3-dimensional problems for which we can design (somewhat) efficient algorithms. Colin de Verdière and Parsa [49, 50] launched the investigation of the complexity of deciding whether a (possibly non-simple) closed curve on the boundary of a 3-manifold is contractible, providing an exponential-time algorithm on it. In very recent work with Chambers, Lazarus and Parsa [O], we improved on their algorithm, showing that the problem is in NP, and more strikingly showing that the problem is fixed parameter tractable when parameterized by the underlying 3-manifold: in other terms, after a fixed exponential-time preprocessing depending only on the 3-manifold *M* one can solve any number of contractibility tests for a curve on the boundary of the manifold in polynomial time. The next steps are to devise a more general free homotopy test under the same conditions and running times, and to tackle the case of a curve not on the boundary of the manifold (although we expect that more general problem to be much more difficult).
<figure><img src="image_45.png" /></figure>
Bibliography

The publications that I have co-authored are listed at the beginning of this document, with alphabetic keys.

[1] S. I. ADYAN, *Unsolvability of some algorithmic problems in the theory of groups*, Trudy Moskov. Mat. Obšč, 6 (1957), pp. 231–298. Cited on page 57

[2] I. AGOL, J. HASS, AND W. THURSTON, *The computational complexity of knot genus and spanning area*, Transactions of the American Mathematical Society, 358 (2006), pp. 3821–3850. Cited on page 62

[3] S. B. AKERS JR, *The use of wye-delta transformations in network simplification*, Operations Research, 8 (1960), pp. 311–323. Cited on page 80

[4] H. ALT AND M. GODAU, *Computing the Fréchet distance between two polygonal curves*, International Journal of Computational Geometry & Applications, 5 (1995), pp. 75–91. Cited on page 44

[5] D. ARCHDEACON AND C. P. BONNINGTON, *Two maps on one surface*, Journal of Graph Theory, 36 (2001), pp. 198–216. Cited on page 77

[6] S. ARORA, *Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems*, Journal of the ACM (JACM), 45 (1998), pp. 753–782. Cited on page 28

[7] S. ARORA AND B. BARAK, *Computational complexity: a modern approach*, Cambridge University Press, 2009. Cited on page 13, 19

[8] F. BALACHEFF, *Measurements of Riemannian two-disks and two-spheres*, Pacific Journal of Mathematics, 275 (2015), pp. 167–181. Cited on page 92

[9] D. BAR-NATAN, *Fast Khovanov homology computations*, Journal of Knot Theory and Its Ramifications, 16 (2007), pp. 243–255. Cited on page 93
[10] L. BARRIÈRE, P. FLOCCHINI, F. V. FOMIN, P. FRAIGNIAUD, N. NISSE, N. SANTORO, AND D. M. THILIKOS, *Connected graph searching*, Information and Computation, 219 (2012), pp. 1–16. Cited on page 45

[11] E. A. BENDER AND E. R. CANFIELD, *The asymptotic number of rooted maps on a surface*, Journal of Combinatorial Theory, Series A, 43 (1986), pp. 244–257. Cited on page 79

[12] S. BESPAMYATNIKH, *Computing homotopic shortest paths in the plane*, Journal of Algorithms, 49 (2003), pp. 284–303. Cited on page 79

[13] D. BIENSTOCK, *Graph searching, path-width, tree-width and related problems (a survey)*, in Reliability Of Computer And Communication Networks, 1989. Cited on page 45

[14] R. H. BING, *The geometric topology of 3-manifolds*, AMS, Providence, RI, 1983. Cited on page 69

[15] G. D. BIRKHOFF, *Dynamical systems with two degrees of freedom*, Proceedings of the National Academy of Sciences of the United States of America, 3 (1917), p. 314. Cited on page 46

[16] S. A. BLEILER, *A note on unknotting number*, in Mathematical Proceedings of the Cambridge Philosophical Society, vol. 96, Cambridge University Press, 1984, pp. 469–471. Cited on page 59

[17] H. L. BODLAENDER, B. BURTON, F. V. FOMIN, AND A. GRIGORIEV, *Knot diagrams of treewidth two*, in International Workshop on Graph-Theoretic Concepts in Computer Science, Springer, 2020, pp. 80–91. Cited on page 84, 93

[18] W. W. BOONE, *The word problem*, Proceedings of the National Academy of Sciences of the United States of America, 44 (1958), p. 1061. Cited on page 57

[19] G. BORRADAILE, P. KLEIN, AND C. MATHIEU, *An $O(n \log n)$ approximation scheme for Steiner tree in planar graphs*, ACM Transactions on Algorithms (TALG), 5 (2009), pp. 1–31. Cited on page 29

[20] G. R. BRIGHTWELL AND P. WINKLER, *Submodular percolation*, SIAM Journal on Discrete Mathematics, 23 (2009), pp. 1149–1178. Cited on page 45

[21] B. BURTON, H. EDELSBRUNNER, J. ERICKSON, AND S. TILLMANN, eds., *Computational geometric and algebraic topology. Abstracts from the workshop held October 11–17, 2015.*, vol. 12, European Mathematical Society (EMS) Publishing House, Zurich; Mathematisches Forschungsinstitut Oberwolfach, Oberwolfach, 2015. Cited on page 84
[22] B. A. BURTON, *The HOMFLY-PT polynomial is Fixed-Parameter Tractable*, in 34th International Symposium on Computational Geometry (SoCG 2018), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Cited on page 84, 93

[23] —, *The next 350 million knots*, in 36th International Symposium on Computational Geometry (SoCG 2020), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Cited on page 85

[24] S. CABELLO, E. W. CHAMBERS, AND J. ERICKSON, *Multiple-source shortest paths in embedded graphs*, SIAM Journal on Computing, 42 (2013), pp. 1542–1571. Cited on page 32, 91

[25] S. CABELLO, Y. LIU, A. MANTLER, AND J. SNOEYINK, *Testing homotopy for paths in the plane*, Discrete & Computational Geometry, 31 (2004), pp. 61–81. Cited on page 79

[26] E. W. CHAMBERS, É. COLIN DE VERDIÈRE, J. ERICKSON, S. LAZARD, F. LAZARUS, AND S. THITE, *Homotopic Fréchet distance between curves — or, walking your dog in the woods in polynomial time*, Computational Geometry: Theory and Applications, 43 (2010), pp. 295–311. Cited on page 44

[27] E. W. CHAMBERS, É. COLIN DE VERDIÈRE, J. ERICKSON, F. LAZARUS, AND K. WHITTLESEY, *Splitting (complicated) surfaces is hard*, Computational Geometry: Theory and Applications, 41 (2008), pp. 94–110. Cited on page 32

[28] E. W. CHAMBERS, J. ERICKSON, K. FOX, AND A. NAYYERI, *Minimum cuts in surface graphs*, arXiv preprint arXiv:1910.04278, (2019). Cited on page 91

[29] E. W. CHAMBERS, J. ERICKSON, AND A. NAYYERI, *Homology flows, cohomology cuts*, SIAM Journal on Computing, 41 (2012), pp. 1605–1634. Cited on page 91

[30] E. W. CHAMBERS AND D. LETSCHER, *On the height of a homotopy*, in Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG), 2009, pp. 103–106. Cited on page 43, 45, 48

[31] G. R. CHAMBERS AND Y. LIOKUMOVICH, *Converting homotopies to isotopies and dividing homotopies in half in an effective way*, Geometric and Functional Analysis, 24 (2014), pp. 1080–1100. Cited on page 47, 48

[32] G. R. CHAMBERS AND R. ROTMAN, *Contracting loops on a Riemannian 2-surface*. arXiv 1311.2995v2, 2013. Cited on page 48, 49

[33] H. CHANG, M. COSSARINI, AND J. ERICKSON, *Lower bounds for electrical reduction on surfaces*, in 35th International Symposium on Computational Geometry,
SoCG 2019, June 18-21, 2019, Portland, Oregon, USA, G. Barequet and Y. Wang, eds., vol. 129 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, pp. 25:1–25:16. Cited on page 82

[34] H.-C. CHANG, *Tightening curves and graphs on surfaces*, PhD thesis, University of Illinois at Urbana-Champaign, 2018. Cited on page 80

[35] H.-C. CHANG, J. ERICKSON, AND C. XU, *Detecting weakly simple polygons*, in Proceedings of the twenty-sixth annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2014, pp. 1655–1670. Cited on page 80

[36] É. COLIN DE VERDIÈRE, *Topological algorithms for graphs on surfaces*, PhD thesis, École normale supérieure, 2012. Habilitation thesis, available at http://www.di.ens.fr/~colin/. Cited on page 32

[37] É. COLIN DE VERDIÈRE, *Multicuts in planar and bounded-genus graphs with bounded number of terminals*, Algorithmica, 78 (2017), pp. 1206–1224. Preliminary version in *Proceedings of the 23rd European Symposium on Algorithms (ESA)*, 2015, and in arXiv:1502.00911. Cited on pages 24, 27, 32, 33

[38] É. COLIN DE VERDIÈRE AND J. ERICKSON, *Tightening nonsimple paths and cycles on surfaces*, SIAM Journal on Computing, 39 (2010), pp. 3784–3813. Cited on page 16, 78, 79, 90

[39] Y. COLIN DE VERDIÈRE, *Comment rendre géodésique une triangulation d'une surface?*, L'Enseignement Mathématique, 37 (1991), pp. 201–212. Cited on page 75, 78

[40] P. F. CORTESE, G. DI BATTISTA, M. PATRIGNANI, AND M. PIZZONIA, *On embedding a cycle in a plane graph*, Discrete Mathematics, 309 (2009), pp. 1856–1869. Cited on page 80

[41] M. COSSARINI, *Discrete surfaces with length and area and minimal fillings of the circle*, arXiv preprint arXiv:2009.02415, (2020). Cited on page 17

[42] A. COWARD AND M. LACKENBY, *An upper bound on Reidemeister moves*, American Journal of Mathematics, 136 (2014), pp. 1023–1066. Cited on page 58

[43] C. CROKE AND M. KATZ, *Universal volume bounds in Riemannian manifolds*, Surveys in Differential Geometry, 8 (2003), pp. 109–137. Cited on page 46

[44] M. CULLER, C. GORDON, J. LUECKE, AND P. B. SHALEN, *Dehn surgery on knots*, Annals of Mathematics, (1987), pp. 237–300. Cited on page 73
[45] M. CYGAN, F. V. FOMIN, L. KOWALIK, D. LOKSHTANOV, D. MARX, M. PILIPCZUK, M. PILIPCZUK, AND S. SAURABH, *Parameterized algorithms*, Springer, 2015. Cited on page 13, 19, 20, 35, 83

[46] E. DAHLHAUS, D. S. JOHNSON, C. H. PAPADIMITRIOU, P. D. SEYMOUR, AND M. YANNAKAKIS, *The complexity of multiterminal cuts*, SIAM Journal on Computing, 23 (1994), pp. 864–894. Cited on page 24, 26

[47] H. DE FRAYSSEIX, J. PACH, AND R. POLLACK, *Small sets supporting Fáry embeddings of planar graphs*, in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), 1988, pp. 426–433. Cited on page 55

[48] M. DE GRAAF AND A. SCHRIJVER, *Making curves minimally crossing by Reide-meister moves*, Journal of Combinatorial Theory, Series B, 70 (1997), pp. 134–156. Cited on page 79, 80

[49] É. C. DE VERDIÈRE AND S. PARSA, *Deciding contractibility of a non-simple curve on the boundary of a 3-manifold*, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2017, pp. 2691–2704. Cited on page 93

[50] ——, *Deciding contractibility of a non-simple curve on the boundary of a 3-manifold: A computational loop theorem*, arXiv preprint arXiv:2001.04747, (2020). Cited on page 93

[51] M. DEHN, *Transformation der Kurven auf zweiseitigen Flächen*, Mathematische Annalen, 72 (1912), pp. 413–421. Cited on page 44

[52] E. D. DEMAINE, A. C. HESTERBERG, AND J. S. KU, *Finding closed quasi-geodesics on convex polyhedra*, arXiv preprint arXiv:2008.00589, (2020). Cited on page 90

[53] L. DEMASI AND B. MOHAR, *Four terminal planar delta-wye reducibility via rooted$K_{2,4}$ minors*, in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2014, pp. 1728–1742. Cited on page 82

[54] M. DESBRUN, M. MEYER, AND P. ALLIEZ, *Intrinsic parameterizations of surface meshes*, in Eurographics conference proceedings, 2002, pp. 209–218. Cited on page 24

[55] V. DESPRÉ AND F. LAZARUS, *Computing the geometric intersection number of curves*, Journal of the ACM (JACM), 66 (2019), pp. 1–49. Cited on page 79

[56] D. DOLEV, T. LEIGHTON, AND H. TRICKEY, *Planar embedding of planar graphs*, Advances in Computing Research, 2 (1984), pp. 147–161. Cited on page 55
[57] F. DORN, E. PENNINKX, H. L. BODLAENDER, AND F. V. FOMIN, *Efficient exact algorithms on planar graphs: exploiting sphere cut branch decompositions*, Algorithmica, 58 (2010), pp. 790–810. Cited on page 92

[58] R. G. DOWNEY AND M. R. FELLOWS, *Parameterized complexity*, Springer Science & Business Media, 2012. Cited on page 20

[59] S. E. DREYFUS AND R. A. WAGNER, *The Steiner problem in graphs*, Networks, 1 (1972), pp. 195–207. Cited on page 25, 28, 30

[60] V. DUJMOVIĆ, M. R. FELLOWS, M. KITCHING, G. LIOTTA, C. MCCARTIN, N. NISHIMURA, P. RAGDE, F. ROSAMOND, S. WHITESIDES, AND D. R. WOOD, *On the parameterized complexity of layered graph drawing*, Algorithmica, 52 (2008), pp. 267–292. Cited on page 55

[61] J. A. ELLIS-MONAGHAN AND I. MOFFATT, *Graphs on surfaces: dualities, polynomials, and knots*, vol. 84, Springer, 2013. Cited on page 16

[62] D. EPPSTEIN, *Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition*, ACM Transactions on Algorithms, 5 (2009). Cited on page 92

[63] J. ERICKSON AND S. HAR-PELED, *Optimally cutting a surface into a disk*, Discrete & Computational Geometry, 31 (2004), pp. 37–59. Cited on page 3, 9, 24, 29, 32, 33, 37, 91

[64] J. ERICKSON AND K. WHITTLESEY, *Greedy optimal homotopy and homology generators*, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005, pp. 1038–1046. Cited on page 32, 92

[65] B. FARB AND D. MARGALIT, *A primer on mapping class groups*, Princeton University Press, 2011. Cited on page 78

[66] I. FÁRY, *On straight line representations of planar graphs*, Acta scientiarum mathematicarum (Szeged), 11 (1948), pp. 229–233. Cited on page 55, 75

[67] S. FELSMER, G. LIOTTA, AND S. WISMATH, *Straight-line drawings on restricted integer*, Graph Algorithms and Applications 4, 4 (2006), p. 363. Cited on page 55

[68] M. FILAKOVSKÝ, U. WAGNER, AND S. ZHECHEV, *Embeddability of simplicial complexes is undecidable*, in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2020, pp. 767–785. Cited on page 61

[69] R. H. FOX, *On the imbedding of polyhedra in 3-space*, Annals of Mathematics, (1948), pp. 462–470. Cited on page 70
[70] M. H. FREEDMAN ET AL., *The topology of four-dimensional manifolds*, Journal of Differential Geometry, 17 (1982), pp. 357–453. Cited on page 2, 8

[71] R. FULEK AND C. D. TÓTH, *Crossing minimization in perturbed drawings*, Journal of Combinatorial Optimization, 40 (2020), pp. 279–302. Cited on page 80

[72] D. GABAI, *Foliations and the topology of 3-manifolds. iii*, Journal of Differential Geometry, 26 (1987), pp. 479–536. Cited on page 72

[73] A. GALLUCCIO, M. LOEBL, AND J. VONDRÁK, *Optimization via enumeration: a new algorithm for the max cut problem*, Mathematical Programming, 90 (2001), pp. 273–290. Cited on page 91

[74] M. GAREY AND D. S. JOHNSON, *Computers and Intractability: A Guide to the Theory of NP-Completeness*, W. H. Freeman, 1979. Cited on page 62

[75] M. R. GAREY AND D. S. JOHNSON, *Crossing number is NP-complete*, SIAM Journal on Algebraic Discrete Methods, 4 (1983), pp. 312–316. Cited on page 85

[76] N. GARG, V. V. VAZIRANI, AND M. YANNAKAKIS, *Primal-dual approximation algorithms for integral flow and multicut in trees*, Algorithmica, 18 (1997), pp. 3–20. Cited on page 26

[77] J. GEELEN, T. HUYNH, AND R. B. RICHTER, *Explicit bounds for graph minors*, Journal of Combinatorial Theory, Series B, 132 (2018), pp. 80–106. Cited on page 77

[78] J. R. GILBERT, J. P. HUTCHINSON, AND R. E. TARJAN, *A separator theorem for graphs of bounded genus*, Journal of Algorithms, 5 (1984), pp. 391–407. Cited on page 40

[79] C. GORDON AND J. LUECKE, *Knots are determined by their complements*, J. Amer. Math. Soc., 2 (1989), pp. 371–415. Cited on page 19, 58, 72

[80] C. M. GORDON AND R. LITHERLAND, *Incompressible planar surfaces in 3-manifolds*, Topology and its Applications, 18 (1984), pp. 121–144. Cited on page 72

[81] M. GROMOV, *Quantitative homotopy theory*, Prospects in Mathematics: Invited Talks on the Occasion of the 250th Anniversary of Princeton University (H. Rossi, ed.), (1999), pp. 45–49. Cited on page 46

[82] J. L. GROSS AND T. W. TUCKER, *Topological graph theory*, Wiley, 1987. Cited on page 16
[83] X. GU AND S.-T. YAU, *Global conformal surface parameterization*, in Proceedings of the Eurographics/ACM Symposium on Geometry Processing, 2003, pp. 127–137. Cited on page 24

[84] L. GUTH, *Lipschitz maps from surfaces*, Geometric and Functional Analysis, 15 (2005), pp. 1052–1090. Cited on page 92

[85] ——, *Recent progress in quantitative topology*, Surveys in Differential Geometry, 22 (2017), pp. 191–216. Cited on page 46

[86] L. GUTH, H. PARLIER, AND R. YOUNG, *Pants decompositions of random surfaces*, Geometric and Functional Analysis, 21 (2011), pp. 1069–1090. Cited on page 78

[87] F. HADLOCK, *Finding a maximum cut of a planar graph in polynomial time*, SIAM Journal on Computing, 4 (1975), pp. 221–225. Cited on page 91

[88] W. HAKEN, *Theorie der Normalflachen, ein Isotopiekriterium für den Kreisnoten*, Acta Mathematica, 105 (1961), pp. 245–375. Cited on page 58

[89] S. HAR-PELED, A. NAYYERI, M. SALAVATIPOUR, AND A. SIDIROPOULOS, *How to walk your dog in the mountains with no magic leash*, in Proceedings of the 28th Annual Symposium on Computational Geometry (SOCG), ACM, 2012, pp. 121–130. Cited on page 44, 51, 52

[90] ——, *How to walk your dog in the mountains with no magic leash*, Discrete & Computational Geometry, 55 (2016), pp. 39–73. Cited on page 45

[91] J. HASS, J. C. LAGARIAS, AND N. PIPPENGER, *The computational complexity of knot and link problems*, Journal of the ACM, 46 (1999), pp. 185–211. Cited on page 58

[92] J. HASS AND F. MORGAN, *Geodesic nets on the 2-sphere*, Proceedings of the American Mathematical Society, 124 (1996), pp. 3843–3850. Cited on page 90

[93] J. HASS AND P. SCOTT, *Intersections of curves on surfaces*, Israel Journal of Mathematics, 51 (1985), pp. 90–120. Cited on page 80

[94] ——, *Shortening curves on surfaces*, Topology, 33 (1994), pp. 25–43. Cited on page 79, 80

[95] A. HATCHER, *Algebraic topology*, Cambridge University Press, 2002. Available at http://www.math.cornell.edu/~hatcher/. Cited on page 13

[96] C. HAYASHI AND K. SHIMOKAWA, *Thin position of a pair (3-manifold, 1-submanifold)*, Pacific Journal of Mathematics, 197 (2001), pp. 301–324. Cited on page 85, 90
[97] J. HERSHBERGER AND J. SNOEYINK, *Computing minimum length paths of a given homotopy class*, Computational Geometry: Theory and Applications, 4 (1994), pp. 63–98. Cited on page 79

[98] J. HOPCROFT AND R. TARJAN, *Efficient planarity testing*, Journal of the ACM, 21 (1974), pp. 549–568. Cited on page 61

[99] T. INKMANN, *Tree-based decompositions of graphs on surfaces and applications to the Traveling Salesman Problem*, Georgia Institute of Technology, 2008. Cited on page 91

[100] A. ISHII, K. KISHIMOTO, H. MORIUCHI, AND M. SUZUKI, *A table of genus two handlebody-knots up to six crossings*, Journal of Knot Theory and Its Ramifications, 21 (2012), p. 1250035. Cited on page 72

[101] G. F. ITALIANO, Y. NUSSBAUM, P. SANKOWSKI, AND CH. WULFF-NILSEN, *Improved algorithms for Min Cut and Max Flow in undirected planar graphs*, in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), 2011, pp. 313–322. Cited on page 27

[102] S. V. IVANOV ET AL., *Recognizing the 3-sphere*, Illinois Journal of Mathematics, 45 (2001), pp. 1073–1117. Cited on page 61

[103] R. KARASEV AND A. SKOPENKOV, *Some converses' to intrinsic linking theorems*, arXiv preprint arXiv:2008.02523, (2020). Cited on page 61

[104] L. H. KAUFFMAN, *Formal knot theory*, Courier Corporation, 2006. Cited on page 85

[105] B. KERÉKJÁRTÓ, *Vorlesung über Topologie*, Springer-Verlag, 1923. Cited on page 19

[106] M. KHOVANOV, *A categorification of the Jones polynomial*, Duke Mathematical Journal, 101 (2000), pp. 359–426. Cited on page 93

[107] R. KIRBY, *A calculus for framed links in $S^3$*, Inventiones mathematicae, 45 (1978), pp. 35–56. Cited on page 71

[108] P. N. KLEIN, *A subset spanner for planar graphs, with application to subset TSP*, in Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, 2006, pp. 749–756. Cited on page 29

[109] —, *A linear-time approximation scheme for tsp in undirected planar graphs with edge-weights*, SIAM Journal on Computing, 37 (2008), pp. 1926–1952. Cited on page 29
[110] P. N. KLEIN AND D. MARX, *Solving PLANAR *k*-TERMINAL CUT in O(n<sup>c√k</sup>) time, in Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP), 2012, pp. 569–580. Cited on page 27

[111] D. KOENIG AND A. TSVIETKOVA, *NP-hard problems naturally arising in knot theory*, arXiv preprint arXiv:1809.10334, (2018). Cited on page 60

[112] —, *Unlinking, splitting, and some other NP-hard problems in knot theory*, in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2021, pp. 1496–1507. Cited on page 60

[113] P. B. KRONHEIMER AND T. S. MROWKA, *Khovanov homology is an unknot-detector*, Publications mathématiques de l'IHÉS, 113 (2011), pp. 97–208. Cited on page 93

[114] G. KUPERBERG, *Knottedness is in NP, modulo GRH*, Advances in Mathematics, 256 (2014), pp. 493–506. Cited on page 58

[115] —, *How hard is it to approximate the Jones polynomial?*, Theory of Computing, 11 (2015), pp. 183–219. Cited on page 60

[116] —, *Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization*, Pacific Journal of Mathematics, 301 (2019), pp. 189–241. Cited on page 58

[117] G. KUPERBERG AND E. SAMPERTON, *Coloring invariants of knots and links are often intractable*, Algebraic & Geometric Topology, (2021). To appear. Cited on page 60

[118] M. LACKENBY, *The crossing number of composite knots*, Journal of Topology, 2 (2009), pp. 747–768. Cited on page 85

[119] —, *A polynomial upper bound on Reidemeister moves*, Annals of Mathematics, (2015), pp. 491–564. Cited on page 58

[120] —, *The efficient certification of knottedness and Thurston norm*. To appear in Advances in Mathematics, 2016. Cited on page 58

[121] —, *Some conditionally hard problems on links and 3-manifolds*, Discrete & Computational Geometry, 58 (2017), pp. 580–595. Cited on page 58, 59

[122] —, *Links with splitting number one*, Geometriae Dedicata, (2021), pp. 1–33. Cited on page 59

[123] M. LACKENBY, *Unknot recognition in quasi-polynomial time*, 2021. Slides available on the author's webpage. Cited on page 58, 93
[124] F. LAZARUS, *Combinatorial graphs and surfaces from the computational and topological viewpoint followed by some notes on the isometric embedding of the square flat torus*, 2014. Habilitation Thesis, Université de Grenoble. Cited on page 17, 77

[125] F. LAZARUS, M. POCCHIOLA, G. VEGTER, AND A. VERROUST, *Computing a canonical polygonal schema of an orientable triangulated surface*, in Proceedings of the 17th Annual Symposium on Computational Geometry (SOCG), ACM, 2001, pp. 80–89. Cited on page 76

[126] F. LAZARUS AND J. RIVAUD, *On the homotopy test on surfaces*, in Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2012, pp. 440–449. Cited on page 57

[127] A. S. LEVINE, *Slicing mixed Bing-Whitehead doubles*, Journal of Topology, 5 (2012), pp. 713–726. Cited on page 66

[128] B. LÉVY AND J.-L. MALLET, *Non-distorted texture mapping for sheared triangulated meshes*, in Proceedings of the 25th Annual Conference on Computer Graphics (SIGGRAPH), 1998, pp. 343–352. Cited on page 24

[129] Y. LIOKUMOVICH, *Slicing a 2-sphere*, Journal of Topology and Analysis, 06 (2014), pp. 573–590. Cited on page 92

[130] J. A. MAKOWSKY AND J. P. MARIÑO, *The parametrized complexity of knot polynomials*, Journal of Computer and System Sciences, 67 (2003), pp. 742–756. Cited on page 84, 93

[131] C. MARIA, *Parameterized complexity of quantum knot invariants*, in 37th International Symposium on Computational Geometry (SoCG 2021), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Cited on page 84, 93

[132] A. A. MARKOV, *Unsolvability of certain problems in topology*, in Doklady Akademii Nauk, vol. 123, Russian Academy of Sciences, 1958, pp. 978–980. Cited on page 57

[133] F. C. MARQUES AND A. NEVES, *Min-max theory and the Willmore conjecture*, Annals of mathematics, (2014), pp. 683–782. Cited on page 90

[134] D. MARX, *Can you beat treewidth?*, in 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), IEEE, 2007, pp. 169–179. Cited on page 38, 39

[135] —, *A tight lower bound for planar multiway cut with fixed number of terminals*, in International Colloquium on Automata, Languages, and Programming, Springer, 2012, pp. 677–688. Cited on page 27, 32, 33, 34, 35
[136] J. MATOUŠEK, E. SEDGWICK, M. TANCER, AND U. WAGNER, *Untangling two systems of noncrossing curves*, in Graph Drawing, S. Wismath and A. Wolff, eds., vol. 8242 of Lecture Notes in Computer Science, Springer International Publishing, 2013, pp. 472–483. Cited on page 77

[137] J. MATOUŠEK, E. SEDGWICK, M. TANCER, AND U. WAGNER, *Embeddability in the 3-sphere is decidable*, Journal of the ACM (JACM), 65 (2018), pp. 1–49. Cited on page 61, 69

[138] J. MATOUSŠEK, M. TANCER, AND U. WAGNER, *Hardness of embedding simplicial complexes in $R^d$*, Journal of the European Mathematical Society, 13 (2011), pp. 259–295. Cited on page 61

[139] M. MIRZAKHANI, *Growth of Weil-Petersson volumes and random hyperbolic surface of large genus*, Journal of Differential Geometry, 94 (2013), pp. 267–300. Cited on page 78

[140] J. S. B. MITCHELL, *Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems*, SIAM Journal on Computing, 28 (1999), pp. 1298–1309. Cited on page 28

[141] B. MOHAR, *The genus crossing number*, ARS Mathematica Contemporanea, 2 (2009), pp. 157–162. Cited on page 77

[142] B. MOHAR AND C. THOMASSEN, *Graphs on surfaces*, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, 2001. Cited on page 13, 16

[143] E. E. MOISE, *Geometric topology in dimensions 2 and 3*, Springer-Verlag, 1977. Cited on page 19

[144] X. MUÑOZ, W. UNGER, AND I. VRT'O, *One sided crossing minimization is NP-hard for sparse graphs*, in International Symposium on Graph Drawing, Springer, 2001, pp. 115–123. Cited on page 86

[145] Y. NAKANISHI, *Unknotting numbers and knot diagrams with the minimum crossings*, Math. Sem. Notes Kobe Univ, 11 (1983), pp. 257–258. Cited on page 59

[146] S. NEGAMI, *Crossing numbers of graph embedding pairs on closed surfaces*, Journal of Graph Theory, 36 (2001), pp. 8–23. Cited on page 77

[147] P. S. NOVIKOV, *Über die algorithmische Unentscheidbarkeit des Wortproblems in der Gruppentheorie*. Tr. Mat. Inst. Steklova 44, 140 S. (1955)., 1955. Cited on page 57
[148] P. OZSVÁTH AND Z. SZABÓ, *Holomorphic disks and knot invariants*, Advances in Mathematics, 186 (2004), pp. 58–116. Cited on page 93

[149] J. PARDON, *On the distortion of knots on embedded surfaces*, Annals of mathematics, (2011), pp. 637–646. Cited on page 91

[150] J. K. PARK AND C. A. PHILLIPS, *Finding minimum-quotient cuts in planar graphs*, in Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), 1993, pp. 766–775. Cited on page 91

[151] V. PATEL, *Determining edge expansion and other connectivity measures of graphs of bounded genus*, in Proceedings of the 18th European Symposium on Algorithms (ESA), no. 6346 in Lecture Notes in Computer Science, 2010, pp. 561–572. Cited on page 91

[152] G. PERELMAN, *The entropy formula for the Ricci flow and its geometric applications*, arXiv preprint math/0211159, (2002). Cited on page 2, 8

[153] A. V. POGORELOV, *Quasi-geodesic lines on a convex surface*, Matematicheskii Sbornik, 67 (1949), pp. 275–306. Cited on page 90

[154] T. RADO, *Über den Begriff der Riemannschen Fläche*, Acta scientiarum mathematicarum (Szeged), 2 (1924), pp. 101–121. Cited on page 19

[155] A. A. RANICKI, *On the Hauptvermutung*, in *The Hauptvermutung* book, vol. 1 of K-Monogr. Math., Kluwer Acad. Publ., Dordrecht, 1996, pp. 3–31. Cited on page 19

[156] J. A. RASMUSSEN, *Floer homology and knot complements*, Harvard University, 2003. Cited on page 93

[157] K. REIDEMEISTER, *Elementare Begründung der Knotentheorie*, in Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, vol. 5, Springer, 1927, pp. 24–32. Cited on page 18

[158] R. B. RICHTER AND G. SALAZAR, *Two maps with large representativity on one surface*, Journal of Graph Theory, 50 (2005), pp. 234–245. Cited on page 77

[159] N. ROBERTSON, P. SEYMOUR, AND R. THOMAS, *Quickly excluding a planar graph*, Journal of Combinatorial Theory, Series B, 62 (1994), pp. 323–348. Cited on page 52

[160] —, *Sachs' linkless embedding conjecture*, Journal of Combinatorial Theory, Series B, 64 (1995), pp. 185–227. Cited on page 80
[161] N. ROBERTSON AND P. D. SEYMOUR, *Graph minors. XI. Circuits on a surface*, Journal of Combinatorial Theory, Series B, 60 (1994), pp. 72–106. Cited on page 92

[162] —, *Graph minors. XIII. The disjoint paths problem*, Journal of Combinatorial Theory, Series B, 63 (1995), pp. 65–110. Cited on page 55

[163] —, *Graph minors. XX. Wagner's conjecture*, Journal of Combinatorial Theory, Series B, 92 (2004), pp. 325–357. Cited on page 55

[164] D. ROLFSEN, *Knots and links*, Publish or Perish, 1976. Cited on page 13, 19, 70

[165] M. SCHAEFER, *Crossing Numbers of Graphs*, CRC Press, 2018. Cited on page 85

[166] M. SCHAEFER AND D. ŠTEFANKOVIČ, *The degenerate crossing number and higher-genus embeddings*, in International Symposium on Graph Drawing, Springer, 2015, pp. 63–74. Cited on page 90

[167] S. SCHLEIMER, *Sphere recognition lies in NP*, Low-dimensional and symplectic topology, 82 (2011), pp. 183–213. Cited on page 61, 70

[168] J. SCHULTENS, *Introduction to 3-manifolds*, vol. 151, American Mathematical Soc., 2014. Cited on page 13

[169] P. SEYMOUR AND R. THOMAS, *Graph searching and a min-max theorem for tree-width*, Journal of Combinatorial Theory, Series B, 58 (1993), pp. 22–33. Cited on page 45

[170] P. D. SEYMOUR AND R. THOMAS, *Call routing and the ratcatcher*, Combinatorica, 14 (1994), pp. 217–241. Cited on page 21, 45, 54, 84, 91, 92

[171] A. SKOPENKOV, *Extendability of simplicial maps is undecidable*, arXiv preprint arXiv:2008.00492, (2020). Cited on page 61

[172] S. SMALE, *Generalized Poincare's conjecture in dimensions greater than four*, Annals of Mathematics, (1961), pp. 391–406. Cited on page 2, 8

[173] A. SONG, *Existence of infinitely many minimal hypersurfaces in closed manifolds*, arXiv preprint arXiv:1806.08816, (2018). Cited on page 90

[174] E. STEINITZ, *Polyeder und Raumeinteilungen*, Encyclopädie der Mathematischen Wissenschaften, Band 3 (Geometrie) Teil 3AB12 (1922), pp. 1–139. Cited on page 80

[175] K. STEPHENSON, *Introduction to circle packing, the theory of discrete analytic functions*, Cambridge University Press, Moscow, 2005. Cited on page 76
[176] J. STILLWELL, *Classical topology and combinatorial group theory*, Springer-Verlag, New York, 1980. Cited on page 13

[177] R. TAMASSIA, ed., *Handbook of graph drawing and visualization*, CRC Press, 2013. Cited on page 75

[178] A. TURING, *Solvable and unsolvable problems*, Science News, 31 (1954), pp. 7–23. Cited on page 58

[179] W. T. TUTTE, *How to draw a graph*, Proceedings of the London Mathematical Society, 3 (1963), pp. 743–767. Cited on page 75

[180] V. V. VAZIRANI, *Approximation algorithms*, Springer Science & Business Media, 2013. Cited on page 19, 83

[181] L. VISMARA, *Planar straight-line drawing algorithms*, in Handbook of Graph Drawing and Visualization, CRC Press, 2013. Cited on page 55

[182] J. VYGEN, *Faster algorithm for optimum Steiner trees*, Information Processing Letters, 111 (2011), pp. 1075–1079. Cited on page 30

[183] V. V. WILLIAMS, *On some fine-grained questions in algorithms and complexity*, in Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, World Scientific, 2018, pp. 3447–3487. Cited on page 20

[184] Z. WOOD, H. HOPPE, M. DESBRUN, AND P. SCHRÖDER, *Removing excess topology from isosurfaces*, ACM Transactions on Graphics, 23 (2004), pp. 190–208. Cited on page 24

[185] R. ZENTNER ET AL., *Integer homology 3-spheres admit irreducible representations in SL(2, C)*, Duke Mathematical Journal, 167 (2018), pp. 1643–1712. Cited on page 61