Generating SVG for the Prime Knots

Soon after I started self-study in Knot Theory, I wanted to design a 24x36 wall poster with knots. I wanted to create it programmatically, starting from nothing but a list of Gauss Codes. Last weekend I finally found the time. Here’s the result:

The above image depicts all single-component prime links with 9 or fewer crossings (omitting their mirror images), plus some 10-crossing knots thrown in at the end.

When viewing the SVG image in its own browser tab, you can click any knot to zoom in. You can also redistribute the poster, print it, hack it, whatever; I’m releasing it into the public domain under CC0. You can also download this 8192x12288 JPEG (6 MB).

SVG is a nice file format for this use case. It’s great at drawing curves, it scales beautifully to any resolution, and doesn’t take much space.

I also love 3D depictions of knots, complete with lighting and specular highlights (see my old WebGL table). However, to a mathematician, knots are more closely related to embeddings of 4-regular planar graphs than they are to real-world knots. For example, Reidemeister moves are one of the first things students learn about, and these moves are defined in the language of 2D knot projections.

How I did it

To create these diagrams, I hacked together a Python pipeline that looks like this:

Gauss Code » Combinatorial Embedding » Half-Edge Structure » Circle Packing » SVG

I obtained the Gauss Codes from knotinfo at Indiana University. I then added orientation information using a method described by Lou Kauffman in his paper Virtual Knot Theory and created this JSON file with the enhanced Gauss Codes. The result is a list of combinatorial embeddings. At this point in the pipeline, each vertex is associated with a clockwise adjacency list, but actual vertex coordinates have not yet been assigned.

To find the faces in the combinatorial embedding, I found it useful to populate a half-edge data structure. Each face is discovered by winding one step around each 4-degree vertex. This JSON file represents the half-edge data structure for each prime knot.

Choosing a planar layout

Next, I needed a way to come up with actual vertex coordinates. The classic way to do this is force-based layout. However I had a few interesting requirements:

1. The edges should be represented by continuous curves, not straight lines.
2. The shadow of the knot (i.e. the 4-regular graph drawing) must have no edge intersections.
3. Ideally, the layout generator has no random seed or sensitivity to initial conditions, as is often seen in physics-based layout systems.

The latter two requirements would be fulfilled with a Tutte Spring Embedding, but the result would not be aesthetically pleasing, nor would it have curved edges.

It turns out that there is a way to generate a nice planar diagram without force-based layout, using a special type of circle packing that preserves the clockwise adjacency list of each vertex. As a bonus, the circle packing is unique to a particular embedding of the knot, making it canonical and easy to reproduce.

Circle packing

In William Thurston’s famous Notes, it was proven that any triangulation of a sphere has a corresponding circle packing. Similar results were discovered by E. Andreev and P. Koebe, so this theorem is sometimes referred to as the K-A-T (Koebe-Andreev-Thurston) Theorem. Kenneth Stephenson wrote a nice article about it in the 2003 Notices of the AMS entitled Circle Packing: A Mathematical Tale. In a separate paper, Stephenson and Collins describe an algorithm that consumes a combinatorial embedding of a planar graph and produces a circle packing where the tangency of the circles corresponds perfectly with the graph.

I ended up using Stephenson’s algorithm, but to simplify the rendering, I applied it to the “meta-graph” rather than the original combinatorial embedding. Each face, vertex and edge in the combinatorial embedding becomes a vertex in the meta-graph.

So, applying circle packing in this way produces three types of circles: faces, crossings, and arcs. This is shown below, using the 8₁₁ knot as an example. Each type of circle is drawn with a different pastel color.

Details: choosing the outer face

The following images are all the 8₁₁ knot, but with a different face chosen as the outside face. Some of these projections are not ideal because the circles in the outermost layer are much larger than the next-smallest layer. This causes crossings to become lost.

I found that a good heuristic for choosing an outer face is to simply choose a face with a large number of edges.

Details: rendering the crossings

2D knot diagrams typically employ a trompe l’oeil effect whereby a gap is used to distinguish an undercrossing from an overcrossing.

To achieve this effect, I did not simply terminate and re-start each cubic Bézier curves at appropriate points near the intersection, because a naive bevel angle does not look great with wide lines. I found it more aesthetically pleasing to render a “whiteout” line on top of the undercrossing and below the overcrossing, as shown below.

Note that a similar effect could be achieved with SVG’s clipPath facility.

Another detail that you probably noticed is that the thickness varies according to the enclosing circle; this means that I could not merely use SVG strokes, instead I had to convert the strokes into filled areas. To do this I cribbed the offsetting functionality in the Simon Cozens beziers library.

Philip Rideout, 28 July 2020.

References

1. Bar-Natan, Dror. The Knot Atlas. Drawing Planar Diagrams: How does it work?.

2. Collins, Charles R., and Kenneth Stephenson. A circle packing algorithm. Computational Geometry 25.3 (2003): 233-256. David Eppstein wrote this implementation as part of the PADS library.

3. Kauffman, Louis H. Virtual knot theory. arXiv preprint math/9811028 (1998). Frédéric Chapoton wrote this implementation of the orientation-determination algorithm as part of the SAGE library.