Planar-diagram codes and knot-table enumeration

Let $G$ be a finite nonempty connected plane multigraph drawn in ${\mathbb{R}}^2$: vertices are distinct points; each edge is a polygonal arc joining its endpoints; edge interiors are pairwise disjoint and avoid every vertex; and loops and parallel edges are allowed. A loop is an edge whose two endpoints are the same vertex, with its interior otherwise embedded. A face is a connected component of the complement of the drawing. If $V,E,F$ are the numbers of vertices, edges, and faces, respectively, then

$V-E+F=2.$

Plane embeddings of finite simple graphs, their faces, facial boundary walks and lengths (counting a bridge twice), and planar graphs — finite simple plane graphs and their face convention.

Euler's formula $\mathrm{\mid }V\mathrm{\mid }-\mathrm{\mid }E\mathrm{\mid }+\mathrm{\mid }F\mathrm{\mid }=2$ for every connected plane graph — Euler's formula for connected simple plane graphs.

Diestel, Graph Theory, Theorem 4.2.9 — connected plane graph Euler formula.

Let $P$ be the projection plane in an oriented $3$-sphere and let $n$ be the unit viewing normal pointing toward the viewer. Orient $P$ so that $(u,v)$ is a positive basis exactly when $(n,u,v)$ is a positive ambient basis. A crossing code has a finite set $C$ of crossing labels and a finite set $D$ of darts, where a dart is one directed half-edge incident to a crossing. A fixed-point-free involution $\alpha :D\to D$ pairs the two ends of each edge: ${\alpha }^2=\mathrm{i}\mathrm{d}$ and $\alpha (d)\mathrm{\ne }d$. A vertex map $v:D\to C$ records the crossing incident to each dart. A rotation system is the permutation $\sigma$ whose cycles give the clockwise order of darts at each crossing. Each crossing has four darts; the two over-strand darts and the two under-strand darts are opposite in that cyclic order. An arrow on each dart records whether its edge is directed into or out of its incident crossing. The pairing $\alpha$ must join one incoming end to one outgoing end. At a crossing, each opposite pair has one incoming and one outgoing dart, so following an edge and then the opposite dart defines the oriented link components. A code is connected when the graph with vertices $C$ and edges the $\alpha$-pairs is connected.

The sign of an oriented crossing is $+1$ or $-1$ according as $\det (v_{\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}},v_{\mathrm{u}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{r}})$ is positive or negative, where the two tangent vectors follow the oriented over- and under-strands. This item fixes the local cyclic-order convention as follows. Starting with the outgoing over-dart and reading counterclockwise, a positive crossing has order $(O_{\mathrm{o}\mathrm{u}\mathrm{t}},U_{\mathrm{o}\mathrm{u}\mathrm{t}},O_{\mathrm{i}\mathrm{n}},U_{\mathrm{i}\mathrm{n}})$; a negative crossing has order $(O_{\mathrm{o}\mathrm{u}\mathrm{t}},U_{\mathrm{i}\mathrm{n}},O_{\mathrm{i}\mathrm{n}},U_{\mathrm{o}\mathrm{u}\mathrm{t}})$. The stored crossing sign and cyclic order must agree. This is the page's explicit sign convention. It agrees with the current KT-03 supplier: reversing its positive counterclockwise order from outgoing over gives the clockwise record $(O_{\mathrm{o}\mathrm{u}\mathrm{t}},U_{\mathrm{i}\mathrm{n}},O_{\mathrm{i}\mathrm{n}},U_{\mathrm{o}\mathrm{u}\mathrm{t}})$.

For a nonempty connected crossing graph, let $V=\mathrm{\mid }C\mathrm{\mid }$, $E=\mathrm{\mid }D\mathrm{\mid }\mathrm{/}2$, and let $F$ be the number of cycles of the face permutation $\varphi =\alpha \circ \sigma$. A spherical code is a code satisfying $V-E+F=2$. A spherical code becomes a plane code by distinguishing one face as the outer face and deleting a point in that face from the sphere. The crossingless one-component code is a separate case: its Gauss data are one empty component word, its DT pairing and crossing-sign vector are empty at $c=0$, and its PD data are the single loop Loop[1]; every format also carries an orientation marker, ccw or cw, for the unit circle $S^1=\{(x,y)\in {\mathbb{R}}^2:x^2+y^2=1\}$ in the oriented plane, and the outer-face marker is outside. Thus the crossingless code records which direction orients its circle. It has no crossing graph or face-permutation test. Disconnected crossing graphs and disconnected crossingless links are outside this code class.

A normalized planar-diagram code with $c>0$ has crossing labels $C=\{1,\dots ,c\}$ and four dart positions $0,1,2,3$ at each crossing, in clockwise order beginning with the outgoing over-dart. The opposite pair $(0,2)$ is over and $(1,3)$ is under. For sign $+1$, the clockwise record is $(O_{\mathrm{o}\mathrm{u}\mathrm{t}},U_{\mathrm{i}\mathrm{n}},O_{\mathrm{i}\mathrm{n}},U_{\mathrm{o}\mathrm{u}\mathrm{t}})$; for sign $-1$ it is $(O_{\mathrm{o}\mathrm{u}\mathrm{t}},U_{\mathrm{o}\mathrm{u}\mathrm{t}},O_{\mathrm{i}\mathrm{n}},U_{\mathrm{i}\mathrm{n}})$. Edge labels are assigned by scanning crossings in increasing order and their four dart positions in order, giving the next positive integer to the pair containing the first not-yet-labelled dart. The outer face is recorded by its least dart in its face cycle. These rules remove arbitrary edge-name and face-name choices; different crossing labelings may still represent the same diagram. At $c=0$ a normalized code is the crossingless record with one of the two orientation markers above.

A Gauss code for an oriented diagram records, in traversal order on each oriented component, a signed crossing label: $+j$ means the component passes over at crossing $j$, and $-j$ means it passes under. For a knot there is one cyclic word; for a link there is one cyclic word per component. Each crossing label must occur exactly twice in total, once positively and once negatively. When $c>0$, every listed component word is nonempty; a separate crossingless component is not part of this code class. The zero-crossing case is only the one-component code specified above. The code also carries a separate algebraic crossing-sign vector ${\epsilon }_j\in \{+1,-1\}$, one entry for each label. Choosing a basepoint turns the knot's cyclic word into a based word; changing the basepoint cyclically shifts the word, and relabeling crossings changes only their names. The visit order, over/under signs, and crossing-sign vector determine the crossing rotation system; it is realizable in the sphere only when the resulting code is spherical. A plane Gauss code also carries an identifier of one cycle of its face permutation to designate the outer face.

A signed Dowker–Thistlethwaite code, in this page's convention, encodes a based oriented knot with $c$ crossings by numbering its $2c$ visits $1,\dots ,2c$ in traversal order. For each odd visit $2j-1$, record the even visit $2k$ paired with it as $d_j=+2k$ when the odd visit is over and $d_j=-2k$ when it is under; also record the algebraic crossing sign ${\epsilon }_j\in \{+1,-1\}$ for crossing label $j$, the pair containing odd visit $2j-1$. Its parity conditions are that $\mathrm{\mid }{d}_1\mathrm{\mid },\dots ,\mathrm{\mid }{d}_c\mathrm{\mid }$ are exactly the even numbers $2,4,\dots ,2c$, each once, and each paired crossing has one over-visit and one under-visit. The separate ${\epsilon }_j$ records the crossing sign; signed DT conventions elsewhere may encode signs differently. The associated cyclic traversal and crossing signs determine a rotation system, which must pass the same spherical realizability test. A plane DT code also carries an identifier of one cycle of its face permutation to designate the outer face.

An oriented planar-diagram code labels each edge segment by an integer and lists its two incident darts at crossing records. Each crossing record lists its four directed edge ends in clockwise order, beginning with the outgoing over-dart, and records which opposite pair is over, the orientation of each strand, and the crossing sign. Every edge label occurs exactly twice, once as an incoming end and once as an outgoing end. The code must satisfy the local crossing-order rule above; its crossing graph must be connected when nonempty; and its rotation system must satisfy $V-E+F=2$. The record also carries an identifier of one cycle of its face permutation as the outer face. Thus an arbitrary word in labels, even when each label occurs twice, is not declared realizable until all incidence, orientation, crossing, connectedness, and face-count tests pass.

Oriented crossing signs, diagram writhe, and blackboard framing — determinant convention in the oriented projection plane, calibrated so a positive Artin half twist has sign $+1$.

Regular oriented link diagrams — regular diagrams have finite transverse double points, four-valent crossing vertices, oriented strands, and over/under data.

Hass–Lagarias–Pippenger, §§1, 3 — finite diagram representation and four-valent crossing data.

Erickson, “Planar Graphs” — dart, rotation-system, face-cycle, and outer-face conventions.

Knot Atlas, Gauss Codes — signed-visit convention and trefoil code.

Knot Atlas, Planar Diagrams — PD edge and crossing records.

Knot Atlas, DT Codes — odd/even DT pairing and signed-code examples.

For a code with a nonempty connected crossing graph, let $C$ be its finite crossing set, $D$ its darts, $\alpha$ its fixed-point-free edge-pairing involution, $\sigma$ its clockwise crossing rotation, and $\varphi =\alpha \circ \sigma$ its face permutation. A spherical realization means a polygonal embedding on the oriented sphere whose vertex rotations and edge pairings are exactly $\sigma$ and $\alpha$; its faces are the cycles of $\varphi$. If every crossing has four darts with the prescribed opposite over/under pairs, arrows, and sign-consistent cyclic order, then such a realization exists if and only if $V-E+F=2$, where $V=\mathrm{\mid }C\mathrm{\mid }$, $E=\mathrm{\mid }D\mathrm{\mid }\mathrm{/}2$, and $F$ is the number of cycles of $\varphi$. Choosing one face as the outer face and deleting a point in it gives the corresponding plane realization. The crossingless one-component code is the single circle and is handled separately.

Planar-diagram, Gauss, and signed Dowker–Thistlethwaite codes — dart, edge-pairing, crossing-rotation, face-cycle, and outer-face conventions.

Euler formula for connected plane multigraphs — Euler counting for the loops and parallel edges allowed here.

Finite polygonal disk parametrizations and boundary surgery — polygonal regular neighborhoods, face disks, and PL disk parametrizations used in the edge insertion.

Regular oriented link diagrams — regular projection and decorated crossing requirements.

Hass–Lagarias–Pippenger, §3 — finite link-diagram graph data and crossing conditions.

Erickson, “Planar Graphs” — rotation-system face cycles and outer-face convention.

Input: A finite tagged Gauss code, signed Dowker–Thistlethwaite code, or oriented planar-diagram code in the conventions of this page. The crossing count $c$ is a nonnegative integer. When $c>0$, the code includes the finite crossing labels, edge-end incidences, strand arrows, over/under data, crossing signs, and a distinguished outer face. When $c=0$, the only admissible input for this procedure is the one-component crossingless code specified in the code definition.

Output: Either Invalid(reason, witness), where reason is the first failed check below and witness identifies the offending field, label, or crossing, or Valid(diagram, components, faces, outerFace). Here diagram is a finite gluing record consisting of one crossing disk per vertex, one rectangular edge band for each pair of darts under $\alpha$, and one cap disk per cycle of the face permutation. Each band is attached at its recorded dart ports, and each crossing disk records its clockwise order, strand orientations, over/under pair, and sign. components lists the oriented link cycles, faces lists the face-permutation cycles, and outerFace is the selected cycle. The gluing record represents a polygonal spherical diagram; deleting a point in its selected face gives the plane model. The procedure tests realizability of this code only; it does not compare the represented link with another code.

Instructions:

1. Read the tag and crossing count. If the tag is unknown or $c$ is not a nonnegative integer, return invalid-header with that field.

2. If $c=0$, accept only one empty Gauss component word, the empty signed-DT code, or the single Loop[1] PD record, each with exactly one orientation marker, ccw or cw. Return invalid-crossingless-code otherwise. If the outer-face marker is not exactly outside, return invalid-outer-face with that marker. For an accepted input return the standard circle with the marked orientation, one component, its two sphere faces, and the outside face selector. Do not run crossing-graph tests.

3. For a Gauss code with $c>0$, if a component word is empty, return invalid-empty-component-word with the first such component index. Check that every label lies in $\{1,\dots ,c\}$, occurs exactly twice in total, and occurs once with each over/under sign. Check that its separate crossing-sign vector has length $c$ and entries in $\{+1,-1\}$. Return invalid-crossing-label for the first out-of-range label, invalid-crossing-visit-count with the label and its over/under counts for any visit failure, or invalid-crossing-sign-vector with the first bad position. Turn successive visits on each component word into directed edge labels, including each cyclic last-to-first edge, numbering these segments in the listed component order and then in traversal order, and form the crossing records from the over/under visits and the stored crossing signs.

4. For a signed DT code, check that its pairing list and sign vector each have length $c$, each pairing value has absolute value in $\{2,4,\dots ,2c\}$, every such absolute value occurs once, and every sign is $+1$ or $-1$. Return invalid-dt-pairing with the first bad index for a pairing failure, or invalid-crossing-sign-vector with the first bad position for a sign failure. The odd visit $2j-1$ is crossing $j$; if $d_j>0$ it is the over-visit and if $d_j<0$ it is the under-visit. At the even visit paired with $2j-1$, use crossing label $j$ and the opposite over/under sign. Decode visits in order $1,\dots ,2c$ into the corresponding signed Gauss word and continue with step 3.

5. For a PD code, check that there are exactly $c$ crossing records and four dart occurrences at each record. Return invalid-crossing-record with the first bad record otherwise. Use the edge labels and arrows in the records to form the paired-dart involution, crossing rotations, over/under pairs, and crossing signs.

6. In every nonempty encoding, check that each edge label has exactly two occurrences, one incoming and one outgoing; each crossing has exactly four incident darts; the opposite pairs are exactly one over-strand and one under-strand; each strand has one incoming and one outgoing end; and the cyclic order matches the stored crossing sign. Return, in that order, invalid-edge-incidence, invalid-crossing-valence, invalid-over-under-pair, invalid-strand-orientation, or invalid-crossing-sign-order, with the first offending label or crossing.

7. Starting at each as-yet unvisited outgoing dart, cross its edge by $\alpha$ to the incoming dart at the other endpoint and continue through the opposite dart of that same strand. Stop only when the starting outgoing dart is reached. If an end is missing, a dart repeats before that return, or any dart remains uncovered after all cycles are traced, return invalid-component-closure with the first such dart. Then test the crossing graph for connectedness; if it is disconnected, return disconnected-crossing-graph.

8. Compute $\varphi =\alpha \circ \sigma$ on all darts by finite table lookup and list its cycles. Put $V=c$, $E=\mathrm{\mid }D\mathrm{\mid }\mathrm{/}2$, and $F=$ the number of cycles. If $V-E+F\mathrm{\ne }2$, return non-spherical-face-count with $(V,E,F)$. If the supplied outer-face identifier is not one of these cycles, return invalid-outer-face with that identifier.

9. For a passing code, choose the lexicographically first spanning tree in the finite edge ordering. Root it at the least crossing label and attach its tree bands in increasing distance from that root, using the recorded cyclic gaps. Then attach the remaining edge bands in increasing edge-label order. Use the distinguished face for the plane projection, replace each crossing disk by its prescribed transverse crossing, attach one cap disk along each face cycle, and lift the over-strand above the under-strand. Return this finite gluing record, the directed components, the face cycles, and the outer-face identifier.

Planar-diagram, Gauss, and signed Dowker–Thistlethwaite codes — exact accepted input formats, signs, and face permutation.

Realizability and face validation for planar-diagram codes — the spherical realization criterion used at steps 8–9.

Hass–Lagarias–Pippenger, §§1, 3 — finite link-diagram graph input and crossing data.

Erickson, “Planar Graphs” — permutation-based face computation and outer-face convention.

Input: A nonnegative integer crossing bound $N$.

Output: A finite ordered list of reconstructed knot-diagram candidates. A candidate is a Valid output of the planar-code validation procedure whose code is a normalized planar-diagram code with one oriented component and at most $N$ crossings. Repeated candidates up to crossing relabeling or planar isotopy are allowed; the list is not a list of knot types.

Instructions:

1. If $N$ is not a nonnegative integer, return invalid-bound.
2. Initialize the output list empty. Pass the two normalized crossingless one-component codes, with ccw and cw orientation markers in that order, through the validator and append both outputs first.
3. For each $c=1,\dots ,N$ in increasing order, use crossing labels $\{1,\dots ,c\}$ and the four normalized dart positions at each crossing. Enumerate every crossing-sign vector in lexicographic order, with $-1<+1$. The sign determines the incoming and outgoing positions at each crossing by the normalized-code convention.
4. For each sign vector, enumerate every bijection from the set of its $2c$ outgoing darts to its $2c$ incoming darts in lexicographic order. Pair each outgoing dart with its image to obtain the edge involution, and assign edge labels by the normalized-code rule.
5. Compute the cycles of $\varphi =\alpha \circ \sigma$ for each pairing. For each cycle, in increasing order of its least dart, select that cycle in turn as the outer face and form the corresponding normalized PD code.
6. Pass each code through the planar-code validation procedure. Append its reconstructed output if and only if the validator returns Valid and the directed component tracing has exactly one cycle. Return the list after the finite loops end.

This procedure enumerates normalized finite codes and reconstructed diagrams; it neither identifies equivalent codes nor decides whether two candidates represent isotopic knots.

Planar-diagram, Gauss, and signed Dowker–Thistlethwaite codes — normalized PD codes, local sign arrows, edge labels, and face selectors.

Planar-code validation and diagram reconstruction — validation and reconstruction of each candidate code.

Hass–Lagarias–Pippenger, §§1, 7 — finite diagram inputs and reconstruction context.

Erickson, “Planar Graphs” — rotation systems and face selection.

For every finite input in the three code formats, the validation and reconstruction procedure terminates. It returns an invalid-code reason exactly when the first failed syntax, incidence, orientation, component, connectedness, face-count, or outer-face condition in its stated order occurs; otherwise it returns the crossing-disk/edge-band model of the represented oriented diagram, its oriented components, its face cycles, and its selected outer face.

Planar-code validation and diagram reconstruction — the ordered finite procedure and its output record.

Realizability and face validation for planar-diagram codes — Euler face-count criterion for spherical realization.

Hass–Lagarias–Pippenger, §3 — finite graph encoding of regular link diagrams.

Erickson, “Planar Graphs” — finite dart, rotation, face, and outer-face data.

For every nonnegative integer $N$, the bounded enumeration procedure terminates and returns exactly the reconstructed candidates represented by normalized connected one-component planar-diagram codes with at most $N$ crossings. Each returned candidate has a valid spherical face structure and a selected outer face. The procedure does not identify candidates that represent the same knot type.

Enumerate diagrams up to a crossing bound — finite sign, pairing, and face-selection loops.

Planar-code validation and reconstruction procedure properties — exact validation and reconstruction of each candidate.

Hass–Lagarias–Pippenger, §§1, 7 — finite code input and reconstructed diagram candidates.

Erickson, “Planar Graphs” — rotation systems and outer-face choices.

Assume the Axiom of Countable Choice. For every valid connected one-component oriented code with a selected outer face, the reconstruction procedure produces a regular oriented diagram representing that code. Any two such diagrams with the same code differ only by crossing and edge relabeling and are planar isotopic. The normalized planar-diagram code of a diagram with $c$ crossings appears among the candidates enumerated at bound $c$. This statement concerns diagrams and their finite codes; it does not identify distinct codes that may represent the same knot type. The finite realization and enumeration claims are choice-free; ${\mathrm{A}\mathrm{C}}_{\omega }$ is assumed only for the smooth ambient-isotopy uniqueness clause.

Planar-diagram, Gauss, and signed Dowker–Thistlethwaite codes — code formats, normalization, and crossing data.

Realizability and face validation for planar-diagram codes — finite spherical realization from the face count.

Planar-code validation and reconstruction procedure properties — correctness of the reconstruction procedure.

Enumerate diagrams up to a crossing bound — bounded normalized-code enumeration.

Enumeration up to a crossing bound procedure properties — exact enumeration of accepted one-component codes.

Smooth Jordan disks and extension of prescribed boundary collars — smooth disk extension with prescribed boundary collars and an interior diffeomorphism germ.

Planar isotopy of link diagrams — smooth orientation-preserving ambient isotopy of the plane.

Erickson, “Planar Graphs” — rotation systems encode plane embeddings up to orientation-preserving homeomorphism; lines 49–61 also identify equivalence with a continuous family of embeddings.

Hass–Lagarias–Pippenger, §3 — finite crossing-graph data for regular link diagrams.