Draw programme

Last modified 28th February, 2012

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 is also capable of drawing knotoids, which was the original motivation.

The algorithm is 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.

  1. 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.
  2. ken.c - I have simply integrated this Knotscape module into my code, having renamed it circle_pack.c, added some comments and optional debug output.
  3. 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.
  4. 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.
In addition to the above, wherever the Knotscape original modules call auxiliary functions I have written corresponding functions in support of my versions. These are also acknowledged effctively to have been taken directly from Knotscape.

The file draw-release-28-2-12.tar contains the C++ source for the draw programme, together with a Makefile.

Drawing knots and knotoids

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] / + - - + - + -

Labelled peer codes for knotoids

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.

Draw programme command syntax

The command syntax for the programme draw is as follows:

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

<metapost-control> =
      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 20
      knotoid: draw knotoids with the leg in the unbounded component of the immersion's complement
      labels: add edge labels to the diagram
      oriented: draw orientation for knots (orientation always shown for knotoids)
      pen-size: set the pen multiplier n to determine the pencircle scale n*0.5pt
      rotate=<degrees>: rotate the diagram anti-clockwise by the specified number of degrees
      shortcut: draw the shortcut if the immersion code is a knotoid
      unit: set the unit dimension N to determine u=N/100 points, default 20
      vertices: label the vertices and draw coordinate axes

<option> =
      c=<centre>: same as centre
      C=<cycle>: same as cycle
      D: same as dots
      d: same as disc-size
      h: this help screen
      i: draw immersion only
      k: same as knotoid
      l: same as labels
      o: same as orientated
      p: same as pen-size
      r=<degrees>: same as rotate
      s: same as shortcut
      u: same as unit
      v: same as vertices

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

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 {}

The input file may contain comments by inserting the ; character anywhere on a line. Titles may be included by starting a line with -- to allow names to be given to peer codes. An example input file is:

; 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 ]/+ + * + + +

A more complex example is the link l11n455, which has peer code

[-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:

When deciding how to arrange the vertices in a diagram the draw programme must make a choice of where to place the unbounded component of the underlying immersions complement. Put another way, if we imagine the diagram drawn on a 2-spehere, the programme has to choose in which region to place the point at infinity. By default, the choice is made by selecting the region whose boundary contains the largest number of edges. As described above, for knotoids the knotoid or k option overrides this choice by chosing the region whose boundary includes the edge labelled zero (which contains the leg of the knotoid. For knots and links it is also possible to influence this choice using the cycle or C option. In the metapost file produced by the draw programme, each figure is prefixed by the title (if one has been provided), the peer code, and a list of left and right turning cycles. These list the semi-arcs in the boundary of the regions making up the diagram's complement. An example of this information is:

% -- 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}

produces the following immersion diagram

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.

References:

Knotoids, Vladimir Turaev, arXiv:1002.4133v4.

back to maths homepage