Doodles



Updated 18th September, 2023.

Contents

  1. Virtual doodles

  2. Planar doodles

1. Virtual doodles

Starting from labelled peer codes representing distinct link immersions we may label immersion crossings as flat or virtual in all possible combinations to obtain labelled peer codes for a set of initial virtual doodle diagrams. Each initial virtual doodle diagram may then be reduced to a minimal virtual doodle diagram by removing all Reidemeister I and Reidemeister II configurations. Note that the assignment of immersion crossing labels may result not only in "simple" Reidemeister II configurations, those designated FR2 and VR2 in [1], but also Reidemeister I or Reidemeister II detours. These are simple Reidemeister configurations where the edge(s) involved in the corresponding Reidemeister move are replaced by a (virtual) detour. In such cases, we either move, or completely remove, the detours in order to reduce the diagram by carrying out the resulting, simple, Reidemeister move. Note also that by removing Reidemeister configurations and detours, we may reduce both the number of flat and virtual crossings and it is possible that two initial doodle diagrams, possibly having a different number of (immersion) crossings, reduce to the same minimal virtual doodle diagram.

Minimal virtual doodles are defined up to detour moves, so to remove all duplicates we first remove all renumbering duplicates and then remove doodles with the same Gauss data. The removal of renumbering duplicates includes the removal of orientation reverses, so we end up with labelled peer codes for representatives of distinct equivalence classes of unoriented, minimal virtual doodle diagrams (Diagramminstrict+rev in [2]).

A consequence of the search algorithm is that, having distinguished a set of virtual doodles with k crossings from immersions with n crossings, one cannot discount the possibility of finding another distinct doodle with k crossings from an immersion having m > n crossings. A virtual doodle with k crossings will only be encountered by the search algorithm when considering immersions with k+v crossings, where v is the virtual crossing number of the doodle.

The lists presented below contain the the representatives of distinct unoriented, minimal virtual doodle diagrams obtained from initial virtual doodle diagrams derived from a list of all immersions (including non-prime immersions) of up to ten crossings having a single component.

The file vlist-release-29-12-17.tar contains the C++ source code for the programme vlist used to create the above lists, together with a Makefile.

The lists of distinct unoriented minimal virtual doodles were calculated by concatenating the lists of realizable link immersions with up to ten crossings into a file called realizable-non-prime-up-to-10, then executing the command line vlist -m 10 1 realizable-non-prime-up-to-10.

This produces a set of files containing the labelled peer code of each equivalence class but the lists are not indexed sequentially and the files do not show the canonical left preferred Gauss data for each class. To produce the files shown above, these initial lists were concatenated into a file doodle-input-codes and the command line vlist -ds 10 1 doodle-input-codes executed.

Virtual doodle diagrams

We present below diagrams of the distinct non-trivial virtual doodles that have been identified with three, four and five flat crossings. These diagrams were rendered by metapost using source code produced by the draw programme.

d3.1

d4.1 d4.2 d4.3 d4.4 d4.5 d4.6

d4.7 d4.8 d4.9 d4.10 d4.11 d4.12

d4.13 d4.14 d4.15 d4.16 d4.17 d4.18

d4.19

d5.1 d5.2 d5.3 d5.4 d5.5 d5.6

d5.7 d5.8 d5.9 d5.10 d5.11 d5.12

d5.13 d5.14 d5.15 d5.16 d5.17 d5.18

d5.19 d5.20 d5.21 d5.22 d5.23 d5.24

d5.25 d5.26 d5.27 d5.28 d5.29 d5.30

d5.31 d5.32 d5.33 d5.34 d5.35 d5.36

d5.37 d5.38 d5.39 d5.40 d5.41 d5.42

d5.43 d5.44 d5.45 d5.46 d5.47 d5.48

d5.49 d5.50 d5.51 d5.52 d5.53 d5.54

d5.55 d5.56 d5.57 d5.58 d5.59 d5.60

d5.61 d5.62 d5.63 d5.64 d5.65 d5.66

d5.67 d5.68 d5.69 d5.70 d5.71 d5.72

d5.73 d5.74 d5.75 d5.76 d5.77 d5.78

d5.79 d5.80 d5.81 d5.82 d5.83 d5.84

d5.85 d5.86 d5.87 d5.88 d5.89 d5.90

d5.91 d5.92 d5.93 d5.94 d5.95 d5.96

d5.97 d5.98 d5.99 d5.100 d5.101 d5.102

d5.103 d5.104 d5.105 d5.106 d5.107 d5.108

d5.109 d5.110 d5.111 d5.112 d5.113 d5.114

d5.115 d5.116 d5.117 d5.118 d5.119 d5.120

d5.121 d5.122 d5.123 d5.124 d5.125 d5.126

d5.127 d5.128 d5.129 d5.130 d5.131 d5.132

d5.133 d5.134 d5.135 d5.136 d5.137 d5.138

d5.139 d5.140 d5.141 d5.142 d5.143 d5.144

d5.145 d5.146 d5.147 d5.148 d5.149 d5.150

d5.151 d5.152 d5.153 d5.154 d5.155 d5.156

d5.157 d5.158 d5.159 d5.160 d5.161 d5.162

d5.163 d5.164 d5.165 d5.166 d5.167 d5.168

d5.169 d5.170 d5.171 d5.172 d5.173 d5.174

d5.175 d5.176 d5.177 d5.178 d5.179 d5.180

d5.181 d5.182 d5.183 d5.184 d5.185 d5.186

d5.187 d5.188 d5.189 d5.190 d5.191 d5.192

d5.193 d5.194 d5.195 d5.196 d5.197 d5.198

d5.199 d5.200 d5.201 d5.202 d5.203 d5.204

d5.205 d5.206 d5.207 d5.208 d5.209 d5.210

d5.211 d5.212 d5.213 d5.214 d5.215 d5.216

d5.217 d5.218 d5.219 d5.220 d5.221 d5.222

d5.223 d5.224 d5.225 d5.226 d5.227 d5.228

d5.229 d5.230 d5.231 d5.232 d5.233 d5.234

d5.235 d5.236 d5.237 d5.238 d5.239 d5.240

d5.241 d5.242 d5.243 d5.244 d5.245 d5.246

d5.247 d5.248 d5.249 d5.250

2. Planar doodles

It is possible to adapt the search methodology used for virtual doodles to consider only flat crossings and search for planar doodles but such an approach is limited in its success and is also very time consuming. Consideration of the link immersions of up to three components described on the link immersions page using this approach results in just six planar doodles.

Given that every doodle is the shadow of a knot, one can also search for minimal planar doodles by considering the shadow of the prime knots listed in the Thistlethwaite-Hoste tables included in knotscape. Lists of the Gauss codes and planar diagram data for these knots may be found on the Gauss codes page. Whilst this is a fast and effective method of identifying planar doodles, it is limited to doodles with one component and it is currently unkown whether there is a non-trivial planar doodle that is not the shadow of a non-trivial knot.

An enumeration of all reduced prime minimal planar doodles is possible by searching for the dual graph of a doodle as described in [3]. In this context prime means that a planar doodle is 3-connected when regarded as a 4-valent graph, we also distinguish as super-prime those planar doodles that are 4-connected.

The software used for the search is available on the search software page, together with a Makefile. Note that this software requires the use of the Open Graph Drawing Framework (OGDF) [4] to test for planarity of dual graphs and to provide a planar embedding of planar dual graphs. I am deeply grateful to the authors of the OGDF for making their work publicly available and my work much easier! For this project the version of OGDF used was Dogwood, February 2nd, 2022. It also requires access, locally or via a symbolic link, to the braid programme in order to de-duplicate the lists it produces.

As described in [3], dual graphs for prime doodles are constructed from a disc with an even number of vertices on the boundary and the disc sub-divided by adding additional interior edges and vertices to create four-sided regions. This approach is valid since, for a prime doodle, the boundary of the dual graph is an embedded circle for any choice of infinite region (see [3]). Focussing on prime doodles also means that we do not have to consider bigons in the dual graph, since removing an endpoint from each of the doodle edges corresponding to a bigon's edges in a dual graph would disconnect the doodle. This is significant simplification since it means we need consider at most one edge between a pair of vertices in the dual graph. A additional consequence of this is that the search avoids the infinite but uninteresting family of "satellite" doodles, as described below.

Given any minimal planar doodle one can add a small circular component that surrounds an individual crossing and create another minimal doodle. This construction yields an infinite family of doodles that are not of great interest, so doodles produced by the search that contain such removable vertex circles are discarded. Similarly, given any two minimal doodles one could extend an edge from one to encircle a boundary crossing of the other and construct another minimal doodle, again not of great interest when attempting to identify distinct doodles. This latter family is, however not 3-connected and therefore implicitly avoided by the search. Finally, it is possible to construct a neighbourhood, N, of a point in the interior of an edge of a doodle that meets the doodle in an arc. Then, it's possible to add another doodle, called a satellite doodle, within N so that the resultant doodle is minimal. Satellite doodles are so named because they may be constructed on any edge of the host doodle. Clearly any number of satellites could be added, and recursively. As noted above, this family is avoided by not having to consider bigons in the dual graph.

The search has been completed for doodles having up to fourteen crossings, a search lasting approximately 14 days using a single linux processing core. The following table summarises the results of this search, together with the results of the search based on the Thistlethwaite-Hoste knot lists for fifteen and sixteen crossings. In each cell of the table the first number gives the number of distinct doodles that are prime but not super-prime (3-connected but not 4-connected), the second number is the number of super-prime doodles. The results obtained via the dual graph for single component doodles have been verified as being consistent with the distinct minimal doodles determined by the shadow of Thistlethwaite's knots up to fourteen crossings.

number of crossings reduced prime minimal planar doodles with m components
m=1 m=2 m=3 m=4
6 0,1
7
8 0,1
9 1,0
10 0,1 0,1
11 1,0 1,1
12 1,2 1,2 1,1 0,2
13 2,3 4,1 2,2 2,0
14 5,12 8,14 8,4 0,1
15 20,18
16 55,81

The following lists contain the the unoriented left-preferred gauss code for each doodle, as defined in [2].

Planar doodles with up to ten crossings

S6^3_1 S8^1_1 P9^1_1

Planar doodles with ten crossings

S10^1_1 S10^2_1

Planar doodles with eleven crossings

P11^1_1 P11^3_1 S11^3_1

Planar doodles with twelve crossings

P12^1_1 P12^2_1 P12^3_1 S12^1_1 S12^1_2 S12^2_3

S12^2_2 S12^3_1 S12^4_1 S12^4_2

Planar doodles with thirteen crossings

P13^1_1 P13^1_2 P13^2_1 P13^2_2 P13^2_3 P13^2_4

P13^3_1 P13^3_2 P13^4_1 P13^4_2

S13^1_1 S13^1_2 S13^1_3 S13^2_1 S13^3_1 S13^3_2

Planar doodles with fourteen crossings

P14^1_1 P14^1_2 P14^1_3 P14^1_4 P14^1_5 P14^2_1

P14^2_2 P14^2_3 P14^2_4 P14^2_5 P14^2_6 P14^2_7

P14^2_8 P14^3_1 P14^3_2 P14^3_3 P14^3_4 P14^3_5

P14^3_6 P14^3_7 P14^3_8 S14^1_1

S14^1_2 S14^1_3 S14^1_4 S14^1_5 S14^1_6 S14^1_7

S14^1_8 S14^1_9 S14^1_{10} S14^1_{11} S14^1_{12} S14^2_1

S14^2_2 S14^2_3 S14^2_4 S14^2_5 S14^2_6 S14^2_7

S14^2_8 S14^2_9 S14^2_{10} S14^2_{11} S14^2_{12} S14^2_{13}

S14^2_{14} S14^3_1 S14^3_2 S14^3_3 S14^3_4 S14^4_1

References:

[1] A. Bartholomew, R. Fenn, N. Kamada, S. Kamada. Doodles on Surfaces, arXiv:1612.08473v2, Journal of Knot Theory and its Ramifications Vol. 27 No 12 (2018), 1850071..

[2] A. Bartholomew, R. Fenn, N. Kamada, S. Kamada. On Gauss codes of virtual doodles, arXiv:1806.05885v1, special edition: Self-distributive system and quandle (co)homology theory in algebra and low-dimensional topology, Journal of Knot Theory and its Ramifications special edition: Self-distributive system and quandle (co)homology theory in algebra and low-dimensional topology, Journal of Knot Theory and its Ramifications Vol. 27, No. 11 (2018) 1843013.

[3] A. Bartholomew, R. Fenn. Planar Doodles: Their Properties, Codes and Classification, arXiv:2308.08834

[4] M. Chimani, C. Gutwenger, M. J√ľnger, G. W. Klau, K. Klein, P. Mutzel. The Open Graph Drawing Framework (OGDF). Chapter 17 in: R. Tamassia (ed.), Handbook of Graph Drawing and Visualization, CRC Press, 2014.

back to maths homepage