Knots and graphs

Knots and graph theory are related in some simple ways.

The triangle is associated with the trefoil knot.

Knot diagram

A table of all prime knots with up to seven crossings represented as knot diagrams with their medial graph.

Once the medial graph is straightened, the knots are easier to draw harmoniously.

A knot in R³ (respectively in the 3-sphere, S³), can be projected onto a plane R² (resp. a sphere S²).

This projection is generically regular, meaning that it is injective everywhere, except at a finite number of crossing points, which are the projections of only two points of the knot. Moreover, we require that the two directions at these points are not collinear, that is to say the two threads project to two different directions of the plane (resp. the sphere) at the crossing point. In this condition, choosing a projection side, one can completely encode the isotopy class of the knot by its regular projection by recording a simple over/under information at these crossings.

In graph theory terms, a regular projection of a knot, or knot diagram is thus a 4-valent planar graph with over/under decorated vertices.

The Reidemeister moves are local modifications of this decorated planar graph which allow to go from one diagram to any other diagram of the same knot (up to ambient isotopy of the plane).

Medial graph

Another interpretation of a knot diagram as a decorated planar graph is more easy to deal with: The projection decomposes the plane in connected components, the graph itself of dimension 1, and an infinite zone and components which are homeomorphic to disks, of dimension 2.

There is a way to attach a color, black or white, to all of these zones of dimension 2 in the following way: Choose the black color for the infinite zone, and at each crossing in turn, color the opposite zone in black. Proceed until every crossings have been taken into account. The Jordan curve theorem implies that this procedure is well defined. It is called the medial graph of the 4-valent original graph.

The planar graph with signed edges associated to a knot diagram and a choice of signs.

Left guide

Right guide

Then you define a planar graph whose vertices are the white zones and whose edges are associated with every crossing. The over/under patterns associated to the crossings are now decorating the edges with a simple sign +/- or left/right according to the local configuration: viewing an edge from any of its two incident vertices, one of the two threads, whether left or right, goes above and the other one goes below. A left edge can be encoded as a plain edge, a right edge as a dashed edge. Changing the chirality of all edges amounts to reflecting the knot in a mirror.

We have thus constructed, for each knot diagram, a planar graph with "signed" edges associated to every crossing; the type of crossing that takes place at the middle of each edge is determined by the left/right sign of that edge.

Reidemeister moves

The Reidemeister moves can be translated in this language: two edge-signed planar graphs are associated with the same knot if and only if you can go from one to the next by a series of Reidemeister moves.

• 

  The 1st Reidemeister move

• 

  The 2nd Reidemeister move

• 

  The 3rd Reidemeister move

Linkless and knotless embedding

Main article: linkless embedding

The seven graphs in the Petersen family. No matter how these graphs are embedded into three-dimensional space, some two cycles will have nonzero linking number.

In two dimensions, only the planar graphs may be embedded into the Euclidean plane without crossings, but in three dimensions, any undirected graph may be embedded into space without crossings. However, a spatial analogue of the planar graphs is provided by the graphs with linkless embeddings and knotless embeddings. A linkless embedding is an embedding of the graph with the property that any two cycles are unlinked; a knotless embedding is an embedding of the graph with the property that any single cycle is unknotted. The graphs that have linkless embeddings have a forbidden graph characterization involving the Petersen family, a set of seven graphs that are intrinsically linked: no matter how they are embedded, some two cycles will be linked with each other.^[1] A full characterization of the graphs with knotless embeddings is not known, but the complete graph K₇ is one of the minimal forbidden graphs for knotless embedding: no matter how K₇ is embedded, it will contain a cycle that forms a trefoil knot.^[2]

References

1. ^ Robertson, Neil; Seymour, Paul; Thomas, Robin (1993), "A survey of linkless embeddings", in Robertson, Neil; Seymour, Paul, Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors, Contemporary Mathematics, 147, American Mathematical Society, pp. 125–136, http://people.math.gatech.edu/~thomas/PAP/linklsurvey.pdf .
2. ^ Ramirez Alfonsin, J. L. (1999), "Spatial graphs and oriented matroids: the trefoil", Discrete and Computational Geometry 22 (1): 149–158, doi:10.1007/PL00009446 .