# Implementing Creative Reidemeister Type II Moves

Question. Given a Gauss Code $$C$$ of a knot $$K \subset S^3$$ with respect to a diagram $$D$$, how can one determine all possible Reidemeister type II moves that increase the number of crossings in $$D$$?

This is clear for creative (i.e., "increases the number of crossings") Reidemeister moves of type I since for a number $$a$$ not appearing in the Gauss code $$C$$, one can just insert $$\{a,-a\}$$ or $$\{-a,a\}$$ in an arbitrary place in $$C$$ to obtain a Gauss code of an equivalent knot. This is much harder in the case of Type II Reidemeister moves, since blindly inserting $$\{a,b\}$$ in one place, and $$\{-a, -b\}$$ (or $$\{-b,-a\}$$) in another might yield a Gauss code of a non-equivalent virtual knot because one might perform one of the Forbidden Moves (see Kauffman, Figure 3).

One solution that occurred to me is to try to construct an explicit embedding of $$D$$ into $$\mathbb{R}^2$$ to see which arcs of $$D$$ are adjacent. But even then the problem seems hard. Is there a more direct way?

Let's first be explicit about exactly what a Gauss code is, since it commonly causes some amount of confusion. In an oriented knot diagram, label all the crossings by unique names (for example, $$a,b,c$$ and so on). Starting from some point away from a crossing, follow the knot in the direction of the orientation, and record three things when you come to a crossing: the crossing label, the crossing orientation ($$+$$ or $$-$$), and the crossing type ($$U$$ or $$O$$ for "under" or "over"). Then continue following the knot until you reach the beginning again.

In the following figure, the black strand is the followed strand and the gray strand is the other strand, and I have recorded the four types of crossings that might occur:

The first confusion is that $$a^{+O}$$ and $$a^{-U}$$ are sometimes called "positive" or "right-handed" crossings and $$a^{-O}$$ and $$a^{+U}$$ are sometimes called "negative" or "left-handed" crossings; notice "positive" and "negative" have nothing to do with the crossing orientation! The second confusion is from not realizing that the following is a theorem that must be proved:

Theorem. Given an unoriented Gauss code (i.e., a Gauss code after deleting the $$+$$'s and $$-$$'s) of a prime knot, one can recover the knot type up to mirror image. In fact, there are exactly two ways to adorn the unoriented Gauss code with orientations.

This is why many times (unoriented) Gauss codes are written as $$-a$$ or $$a$$ for $$a^{U}$$ or $$a^{O}$$, for example in Dowker-Thistlethwaite codes. (This theorem fails for virtual knots and for non-prime knots in general.)

So, to be completely accurate, Reidemeister moves of type I correspond to inserting $$x^{\pm O}x^{\mp U}$$ or $$x^{\pm U}x^{\mp O}$$ somewhere in the Gauss code for a fresh label $$x$$.

Virtually speaking, there is no danger in accidentally doing a forbidden move when performing a Reidemeister II move. The move corresponds to inserting a $$x^{\pm O}y^{\mp O}$$ in one place and $$x^{\mp U}y^{\pm U}$$ in another (in the case both strands are going "in the same direction"), or to inserting a $$x^{\mp O}y^{\pm O}$$ in one place and $$y^{\mp U}x^{\pm U}$$ in another. The "forbidden move" is called so because diagrammatically it looks like it might be a Reidemeister-III-like move, but it does not correspond to a Reidemeister-like modification of a Gauss code. So: if you're modifying Gauss codes directly, there is no such thing as a forbidden move to avoid.

For classical knots, the Gauss code has plenty of information to recover a way to draw a knot diagram. As you follow the knot, you convert the $$x^{\pm O}$$ and $$x^{\pm U}$$ into the fragments from my figure above, and then you connect everything up according to the code, only taking care not to let any strands overlap. The constraint on a Reidemeister II move is that it occurs over a face of the diagram, where a face is one of the regions complementary to the diagram itself (the faces are polygons whose vertices are at the crossings and whose edges are crossing-free strands of the knot).

There is a straightforward algorithm to abstractly work with faces through the Gauss code itself. The edges of a face are given by positions between terms of the Gauss code. Orientations of the edges of a face are given by recording "left" or "right" for the position between the terms of the Gauss code. Given a position between terms and an orientation, we can read off a face whose edges are given counter-clockwise orientation, so as we follow the boundary of the face our left hand is always touching its interior. I'll just do two examples: if we are at the position just before $$a^{+O}$$ and the edge orientation is "right", then we advance to the position just after $$a^{-U}$$ and keep the edge orientation as "right." If we are at the position just after $$a^{-U}$$ and the edge orientation is "left", then we advance to the position just after $$a^{+O}$$ and switch to the edge orientation "right." (These rules should make sense if you spend some time working them out yourself!)

The point is, it is completely algorithmic to determine the faces. Then, since a face is a collection of orientations of positions between terms in a Gauss code, Reidemeister II corresponds to inserting the sorts of terms mentioned before at pairs of positions in a face in a way that respects the orientations given by the face. Again, a computer could do this.

• Indeed it did not occur to me that it might be useful to consider orientations. Since I do not really have access to oriented Gauss codes I need to implement (or reluctantly use) an algorithm to find such orientations. I found Kauffmans 1999 paper describing such an algorithm. Is it reasonable to go in this direction? May 1, 2019 at 19:50
• @LeviRyffel Kauffman's paper describes Max Dehn's solution to the so-called Gauss word problem. Rosenstiehl and Tarjan have an $O(n)$ algorithm for finding the signs (using a data structure called a "pile of twin stacks"). See jeffe.cs.illinois.edu/teaching/topology17/notes/… for some references. If you do not care about running time too much, you can take all $2^n$ crossing orientations and calculate for each the number of faces to get the Euler characteristic (all you want is for the Euler characteristic to be $2$). May 2, 2019 at 4:04
• @LeviRyffel The section starting at page 100 of knotplot.com/thesis/thesis_letter.pdf has an algorithm where you "puff up" each crossing into a square of trivalent vertices then do any algorithm for finding a planar embedding of a graph. May 2, 2019 at 4:05