Last modified 10th May, 2020

The draw programme generates metapost code to draw diagrams from labelled peer codes. It is currently able to draw a variety of knots and links: classical, virtual, welded and flat, and (multi-)knotoids, which was the original motivation.

The programme can also draw a set of smoothed states for a given diagram, as used by various invariants based on state sums, or the convex triangulation of a disc determined by a peer code.

This page contains the following sections:

The default drawing algorithm is one based on circle packing taken from the drawing routine in Knotscape, by Jim Hoste and Morwen Thistlethwaite, and in particular Ken Stephenson's implementation of Thurston's circle packing algrithm.

My code provides the environment to read peer codes from an input stream, then applies the algorithms of Knotscape to produce a sequence of coordinates at key points as we traverse the underlying immersion. Armed with these coordinates it is a simple matter to produce metapost output that can draw the immersion with the appropriate over, under and virtual crossings, knotoid shortcuts, and so on.

Specifically, the following key aspects have been taken from Knotscape. I am very grateful to the authors of Knotscape for making this code available in the public domain and fully acknowledge all rights they may have in that code and it's methods.

- triangulate.c - I have written code to produce the same triangulation as described in this Knotscape module starting from a labelled peer code. The output of my code is a file with the same file format as that produced by the Knotscape version. Starting with a labelled peer code allows my code to support links and non-prime diagrams, unlike Knotscape.
- ken.c - Initially, I simply integrated this Knotscape module into my code, having renamed it KS_circle_pack.c and added some comments and optional debug output. Later, I ported KS_circle_pack.c to C++, taking some ideas from another circle packing algorithm implemented in circle_pack.cpp but retaining Stephenson's algorithm. See the comments at the top of KS_circle_pack.cpp for more details.
- nodeseq.c - this module has been re-written to take into account the fact that the sequence of vertices I am interested in is determined by a labelled peer code; also, the use of metapost means I do not need all of the coordinates used by Knotscape. Thus, my nodeseq is a form of the corresponding Knotscape model optimized for peer codes, however, as with the other modules above, the algorithms (in particular the coordinate scaling algorithm) are all taken from Knotscape.
- badness - I have incorporated the same assessment of a set of coordinates as used by Knotscape via the badness function but have provided the option to control the location of the point at infinity explicitly.

Various other drawing algorithms are available as options to the draw programme, these are largely experimental in nature and were produced in an effort to explore alternatives to circle packing in an attempt to draw aesthetic diagrams for those cases where circle packing creates a tightly knotted part of the diagram. There are options included for investigating the behaviour of the drawing algorithms, such as drawing the triangulation, tracing the progress of force directed placement algorithms etc. that may be ignored by most users.

There are a number of command line options available to adjust things like the overall scale of the diagram (the `u` or `unit` option), the size of the discs added to create over and under crossings, or to designate virtual crossings (the `d` or `disc-size` option), or to designate the use of TeX's mathematics "script size" or "scriptscript size" font for semi-arc labels (the `script-labels` and `scriptscript-labels` options).

If the diagram results in metapost coordinates that are too large, the metapost_coordinate_scale_factor used by the programme may be adjusted using the `M` option. Simple help information is available by starting the programme with the command "`draw -h`", a full list of options may be seen by starting the programme with the command "`draw -H!`"

See the section Draw programme command syntax for more details.

The file draw-release-10-5-20.tar contains the C++ source for the draw programme, together with a Makefile and a test input file.

The draw programme takes as input a labelled peer code description of a knot, link or knotoid, either from the command line or from an input file. Full details of labelled peer codes are provided in the paper labelled-peer-code.pdf. Here we provide only a brief description.

A labelled peer code for a virtual (or classical) link (knot) diagram is obtained from the underlying immersion by choosing an arbitary starting component and semi-arc and numbering each semi-arc of that component consecutively from zero as we trace around the component. When we return to the starting semi-arc we move onto another component and continue the numbering.
We require that each time we start a new component we choose one that has a crossing involving a strand belonging to a component that has already been numbered. We also require that we start the numbering of the new component on a semi-arc that ensures that the first crossing we encounter involving a previously numbered strand has both an odd and an even numbered incoming semi-arc, with respect to the orientation induced by the numbering. It is always possible to construct such a numbering, as described in the document referenced above.
We view the immersion as a 4-regular plane graph. The numbering results in every vertex having an even and odd numbered terminating edge and an even and odd numbered originating edge with respect to the induced orientation.
The two edges terminating at a common vertex are called *peer edges*.

If the immersion has n vertices, the graph has 2n edges and the peer edges are of the form `2i, 2j-1` (taken mod 2n) for some integers `i` and `j` in the range `0,...n-1`. The value of `i` determines a numbering for the vertex (and corresponding crossing) at which edge `2i` terminates. We therefore refer to the even edge as the *naming edge* for the corresponding crossing.

Further, the peer edges will be oriented around the vertex so that the odd edge is located adjacent to the even edge in a clockwise or anticlockwise direction. We call crossings of the first type Type 1 crossings and of the second type Type 2 crossings.

The first part of a labelled peer code is comprised of a list of the odd-numbered peers in the order determined by the vertex numbering. The list is separated by commas into the peers of naming edges that are associated with the same component of the link.

For example, for the immersion and edge numbering shown in the figure above, the list of odd peers is

`11 9, 3 1 13 5 7`

The list of odd peers may be supplemented to record the type of each crossing by writing each odd peer associated with a Type I crossing as a negative number. Thus, for the diagram above we get

`-11 9, -3 1 -13 5 -7`

we refer to this code as a *peer code*.

The second part of a labelled peer code provides information about the original link diagram. For classical crossings we assign the label `+` if the naming edge forms part of the over-arc of the crossing and the label `-`
if it forms part of the under-arc. For virtual or welded crossings we assign the label `*` and for flat crossings we assign the label `#`.

These labels are writen after the list of odd peers separated by a `/` character. They are written in the order determined by the vertex numbering. Thus continuing the above example if the original link diagram is as
follows:

then the full labelled peer code is

`-11 9, -3 1 -13 5 -7 / + - - + - + -`

For the purposes of distinguishing labelled peer codes from other codes when using a computer the peer code will be enclosed in square brackets, as follows:.

`[-11 9, -3 1 -13 5 -7] / + - - + - + -`

To represent a knotoid we draw a shortcut from the head to the leg comprised of under-crossings, whereupon we may obtain an immersion as before. We then determine the peer code by starting with the edge containing the leg of the knotoid and proceed along the knotoid to the head and then along the shortcut. We identify the first crossing created by adding the shortcut by writing the `^` character *after* the odd peer at that crossing in the first part of the peer code. We attach labels to a knotoid's peer code in the same manner as we do with links.

The following is an example of a labelled peer code for a knotoid.

`
[-7 13 -11 -1 3 -5 9^ ]/+ + - + + - -
`

Note that the `^` character uniquely identifies the head since there is a unique edge entering each crossing as part of the under-arc.

The command syntax for the programme draw is as follows:

`Usage draw [--<programme-option>][-<metapost-control>][<infile>[<outfile>]]`

The programme reads labelled peer codes from the <infile>, or from a command prompt if no <infile> is provided, and then evaluates a triangulation of the disc determined by the immersion underlying the peer code.

By default, the programme uses Ken Stephenson's circle packing algorithm to place the vertices of the triangulation. Alternatively one of the following long programme options may be used to select a different vertex placement technique.

Once the vertices have been positioned, the programme creates a metapost script describing the diagram in <outfile>, or in the file draw.out if no <outfile> is provided.

The supported `programme-option` and `metapost-control` options are:

<programme-option> convex: draw the convex, straight line triangulation of a disc edge[=<max-iterations>] default 200: use edge distribution placement force[=<max-iterations>] default 200: use Plestenjak force directed placement gravity[=<max-iterations>] default 200: use centre of gravity placement magnify[=<percentage>] default 0: magnify small circles in circle packing by specified percentage shrink[=<max-iterations>] default 200: use region shrinking placement after circle packing small-shrink[=<max-iterations>]: use small region shrinking placement after circle packing smoothed: draw all of the smoothed states for the given diagram <metapost-control> c=<centre>: specify the centre of rotation <centre> = (<x>,<y>)|z<n> C=<cycle>: specify the turning cycle to bound the infinite region D: set the smoothed state disc size multiplier to determine the size of smoothed crossings n*d (default n=6) d: set the unit multiplier to determine the crossing disc diameter (default 30) F: do not draw the crossing features h: help screen I: do not draw the immersion (consider using F option also) k: draw knotoids with the leg in the unbounded component of the immersion's complement l: add edge labels to the diagram o: draw orientation for knots (orientation always shown for knotoids) p: set the pen multiplier n to determine the pencircle scale n*0.5pt (default n=1) P: draw the underlying circle packing that determines the diagram r=<degrees>: rotate the diagram anti-clockwise by the specified number of degrees S: draw the shortcut if the code describes a knotoid t: draw the triangulation of the unit disc u: set the unit dimension nn to determine u=0.nn points (default 20) v: label the vertices and draw coordinate axes

The short `<metapost-control>` options have corresponding long options, useful for including in
input files as global options or as qualifiers (see the section Input file format):

centre=<centre>: specify the centre of rotation <centre> = (<x>,<y>)|z<n> cycle=<cycle>: specify the turning cycle to bound the infinite region dots: draw knotoid shortcuts dashed with dots rather than dashed evenly disc-size: set the unit multiplier to determine the crossing disc diameter (default 30) knotoid-leg-unbounded: draw knotoids with the leg in the unbounded component of the immersion's complement labels: add edge labels to the diagram no-crossings: do not draw the crossing features no-immersion: do not draw the immersion oriented: draw orientation for knots (orientation always shown for knotoids) packing: draw the underlying circle packing that determines the diagram pen-size: set the pen multiplier n to determine the pencircle scale n*0.5pt (default n=1) rotate=<degrees>: rotate the diagram anti-clockwise by the specified number of degrees shortcut: draw the shortcut if the code describes a knotoid triangulation: draw the triangulation of the unit disc unit: set the unit dimension nn to determine u=0.nn points (default 20) vertices: label the vertices and draw coordinate axes

additional long options:

edge-factor=<float> default 0.5: amount by which vertices are moved towards the COG in edge distribution placement first-gap: always use the first gap as the active gap in edge distribution placement frame-corners: show frame corners when tracking placement iteration hyperbolic: drawing diagram in the hyperbolic plane no-vertex-axes: do not show the axes when labelling the vertices of a diagram no-show-displacement: do not show the triangulation displacement when tracking placement iteration plot=<divisions>: set the number of divisions for the histogram in edge distribution placement (default 20) script-labels: label vertices using TeX's script size font scriptscript-labels: label vertices using TeX's scriptscript size font show-shrink: draw the effect of shrinking the triangulation when using region shrinking placement show-small: highlight the small edges of the triangulation when using edge_distribution placement shrink-factor=<float> default 0.75: amount by which region shrinking placement retracts trianglulation vertices towards the barycentre shrink-area-factor=<float> default 1.618034: region shrinking placement converges if all compact regions have an area within this factor of their average area smoothed-disc-size: set the smoothed state disc size multiplier to determine the size of smoothed crossings n*disc-size (default n=6) tension: set the metapost path tension, default value 1.0, i.e. the metapost ".." default

additional short options:

#: debug a=<float> default 1.0: average triangulation edge length factor used to magnify edge vertices closer than a*average_triangulation_edge_length A: adjust the angle of diagram arcs at crossings to be right angles b: do not use badness optimization B: include boundary vertices; may be used with f, g, P, or t. Boundary vertices are alway included in force directed placement, in which case this option only has an efect if the t option is also used. E: use edge repulsion rather than Plestenjak force directed placement i[=<max-iterations>] default 1000: set maximum circle packing iterations H!: additional help screen #H!: display debug help screen K: use Fenn's circle packing algorithm rather than Ken Stephenson's L: start from one when labelling edges M=<scale_factor> : set metapost_coordinate_scale_factor: default 2500 with the circle packing option, 1000 with force or gravity placement, 600 with the convex-disc option, 25 otherwise O: create metapost with one cycled path for each component P: draw circle packing R=<float>: retract boundary vertices radially towards their centroid by a factor <float> < 1 T[=<track-step>] default 1: track placement iteration (force, gravity, shrink) V[=<vertex>] default 0: check inner hull calculation of <vertex> x=[0|1|2|3] default 0: set debug level for Stephenson circle packing

The overlap between long options and short options is designed to provide a convenient mechanism for setting programme defaults from the command line as well as an intuitive approach to creating input files (see below)

By default the draw programme produces metapost code based on the following metapost parameters

- units = 20, giving u=0.2 pt
- disc-size = 20, giving a disc diameter of 20u
- pen-size = 1, giving pencirlce scale 0.5 pt

Multiple peer codes may be included in the inputfile, written on different lines. Default options
to be applied to all the codes in the file may be specified from the command line using long or short
options. Alternatively, defaults may be included within the file by specifying one or more long
options within square brackets, separated by commas, as in `[unit=30,labels]`. It is
possible to override the defaults on a per-code basis by including *qualifiers* after a peer
code. Qualifiers are long options, separated by commas, included within braces `{}`

`
; here is an example input file
[oriented, unit=30] ; set the defaults for these codes
-- an example of a flat knot; this is a comment on a title line
[-5 -7 -1 -9 -3]/#####
-- a rotated knotoid
[-7 13 -11 -1 3 -5 9^ ]/+ + - + + - - {rotated=45, centre=z4}
`

In the above example a diagram is rotated by 45 degrees about z4. The default centre of rotation
is determined from the minumum and maximum x-coordinates and y-coordinades, the midpoint of each
being used to determine the centre of rotation. In the above example an explicit centre of rotation is given as one of the vertices used to draw the diagram. The metapost path created for each diagram has a vertex at each crossing and a vertex at the midpoint of each semi-arc. A diagram with the vertices labelled may be drawn using the long option `vertices` or the short option
`v` (see below for an example). Alternatively, an explicit centre of roatation may be specified by giving the exact x and y coordinates.

Some examples of the diagrams that the programme can produce are shown below, these pictures are png format files that have been produced, and scaled, using Ghostscript for presentation on this page.

The following is an example of the diagram resulting from the metapost code produced by the draw programme for the virtual knot

` [-5 7 9 -11 3 1 ]/+ + * + + + `

` [-7 39 -53 27 15 35 -47, 13 -43 37 -45, 49 -33 -21 -41 5 19 11 -23 -51 -29 1, -31 25 -9 -17 -3]/- + - + - + + - + + + + + + + - - - - + - - + - - + - `

Using the `--oriented/-o` option adds the orientation determined by the immersion code:

Using the `--label/-l` option produces labels on the edges of the diagram:

Using the `--vertices/-v` option produces a diagram with coordinate axes and vertex labels, intended in case the Metapost code requires manual editing:

The following is an example of the diagram resulting from the metapost code produced by the draw programme for the knotoid

` [-7 13 -11 -1 3 -5 9^ ]/+ + - + + - - `

If the `--knotoid/-k` option is used the leg appears in the unbounded component of the knotoid complement, however, as in the following example this does not always produce an aesthetic result.

If the `--shortcut/-s` option is used the shortcut is drawn:

`
% -- Example immersion
% [4 8 0 2 6]/# # # # #
% left turning cycles:
% cycle 0: 0 6
% cycle 1: -1 -5
% cycle 2: 2 8 4
% cycle 3: -3 -7 -9
% right turning cycles:
% cycle 4: 0 -5 2 -7
% cycle 5: -1 6 -9 4
% cycle 6: -3 8
`

See labelled-peer-code.pdf for an explanation of the minus signs in this output.

From this information it is possible to select a particular turning cycle if required. For example, the peer code` [5 7 1 9 3]/##### {labels} `

and the turning cycle information shown above. If we select cycle 2 and use the qualifier:

` [5 7 1 9 3]/##### {labels,cycle=2} `

we produce the following diagram.

Note: sometimes the Metapost code produced by the draw programme results in Metapost producing postscript files with negative bounding box values. For some programmes it is therefore necessary to add the following line to these postscript files

`
<x-shift> <y-shift> translate
`

where <x-shift> and <y-shift> are chosen so the lower-left bounding box coordinates are non-negative.

There are several invariants based on state sums for which it is sometimes useful to generate pictures of the smoothed states
for an example diagram. By using the `smoothed` programme option, the draw programme will produce metapost code for all
of the smoothed states of each input code.

Only non-virtual crossings are smoothed, and in the case of knotoids, shortcut crossings are not smoothed. For the remaining crossings, the states range over all combinations of Seifert-smoothed and non-Seifert-smoothed choices for each crossing. A Seifert smoothed crossing is one for which the smoothed state corresponds to tracing the Seifert circles of the underlying diagram at that crossing.

The `smoothed` option produces a diagram of the original knot or knotoid, with semi-arcs labelled from zero as
determined by the labelled peer code. Then produces state diagrams, identifying each non-Seifert-smoothed crossing by
marking the crossing with a small black dot on each smoothed strand. Furthermore it labels each crossing with a state
label as follows:

For some diagrams, the default size of the smoothed crossing is too large and causes metapost to complain about paths not
intersecting. In this case, reducing the size of the smoothed crossing using the `smoothed-disc-size` or `D`
option, or if necessary additionally adjusting the crossing disc size with the `disc-size` or `d` should resolve the situation.

- Positive crossings: Seifert-smoothed are labelled A, non-Seifert-smoothed are labelled B
- Negative crossings: Seifert-smoothed are labelled B, non-Seifert-smoothed are labelled A

The following is an example of a smoothed state for a knotoid that closes to the Slvik knot:

The full set of smoothed states for this knotoid are as follows:

Knotoids, Vladimir Turaev, arXiv:1002.4133v4.