Guide to using plantri (version 5.4) ==================================== Gunnar Brinkmann University of Gent Gunnar.Brinkmann@ugent.be Brendan McKay Australian National University brendan.mckay@anu.edu.au Heidi Van den Camp INTRODUCTION. plantri is a program that generates certain types of graphs that are imbedded on the sphere. Exactly one member of each isomorphism class is output, using an amount of memory almost independent of the number of graphs produced. This, together with the exceptionally fast operation and careful validation, makes the program suitable for processing very large numbers of graphs. Isomorphisms are defined with respect to the imbeddings, so in some cases outputs may be isomorphic as abstract graphs. DEFINITIONS. When a graph is drawn on the sphere without edges crossing, the sphere is thereby divided into regions called FACES. If the graph is connected, each face is homeomorphic to a disk (which in this case just means that it has no holes). We can cut a hole in the sphere in the middle of a face and open the sphere into a plane, but we must remember that the outside region is as much a face as the other regions even though it is no longer a disk. The combinatorial structure of a graph drawn on the sphere is represented by the cyclic order of the edges at each vertex, where (according to the arbitrary choice we will adopt) the order is clockwise if we look at the sphere from the outside. a 3------------4 / \ /| / \ b c / | d / \ / | e FIGURE 1. / \ / | / \ / | 0 --------- 2 ---- 1 f g In the above example, the abstract graph is given by the edges a={3,4}, b={2,3}, c={2,4}, d={0,3}, e={1,4}, f={0,2}, g={1,2}. The imbedding is given by listing the edges in clockwise order for each vertex: 0: d,f 1: e,g 2: b,c,g,f 3: a,b,d 4: a,e,c Note that the cyclic order b,c,g,f is the same as c,g,f,b - the starting point doesn't matter. To fully represent the imbedded graph we need both the abstract graph and the cyclic edge orders. In the case of a graph with no parallel edges (more than one edge with the same endpoints), it is conventional to give both at once by listing neighbours in clockwise order: 0: 2,3 1: 2,4 2: 0,3,4,1 3: 0,4,2 4: 1,2,3 Later we will describe a convention for representing even imbeddings of some graphs with parallel edges by cyclic neighbour lists. The MIRROR IMAGE of an imbedded graph is obtained by reversing all the cyclic orders. That corresponds to turning the sphere inside out. The mirror image of the above graph is a 4------------3 |\ / \ | \ c b / \ e | \ / \ d FIGURE 2. | \ / \ | \ / \ 1---- 2 ---------- 0 g f In defining "isomorphism" for two imbedded graphs, we have the choice of whether or not to automatically regard a graph and its mirror image as isomorphic. plantri knows both definitions: Let G and H be two connected imbedded graphs with the same numbers of vertices and the same number of edges. An ORIENTATION-PRESERVING (O-P) ISOMORPHISM from G to H is a bijection fv from V(G) to V(H), and a bijection fe from E(G) to E(H), such that (1) If e = {v1,v2} is in E(G), then fe(e) = {fv(v1),fv(v2)} and fe(e) is in E(H). (2) If (e1,e2,...,ek) is the set of edges incident with a vertex v of G, in clockwise order, then (fe(e1),fe(e2),...,f(ek)) is the set of edges incident with the vertex fv(v) of G, in clockwise order. An ORIENTATION-REVERSING (O-R) ISOMORPHISM from G to H is a bijection fv from V(G) to V(H), and a bijection fe from E(G) to E(H), such that (1) If e = {v1,v2} is in E(G), then fe(e) = {fv(v1),fv(v2)} and fe(e) is in E(H). (2) If (e1,e2,...,ek) is the set of edges incident with a vertex v of G, in clockwise order, then (fe(e1),fe(e2),...,f(ek)) is the set of edges incident with the vertex fv(v) of G, in anti-clockwise order. Note that the two definitions differ only in the penultimate word. An ISOMORPHISM from G to H is either an O-P isomorphism or an O-R isomorphism. Isomorphism and O-P isomorphism (but not O-R isomorphism) are equivalence relations, so we can speak of ISOMORPHISM CLASSES and O-P ISOMORPHISM CLASSES. Similarly, the set of all isomorphisms and the set all O-P isomorphisms (but not the set of all O-R isomorphisms) from an imbedded graph to itself form groups under composition: the AUTOMORPHISM GROUP and the O-P AUTOMORPHISM GROUP. Given an imbedded graph G, we can form another imbedded graph called its PLANAR DUAL (or just DUAL) D. The vertices of D are the faces of G. The edges of D are in 1-1 correspondence with the edges of G: the two endpoints of an edge in D are the faces that are on either side of the corresponding edge in G. Finally, the cyclic order of edges around a vertex in D (which is a face in G) is the clockwise order of the corresponding edges bounding the face in G. The graph in Figure 2 has the following dual: ---------------------- | d | | ---------- | | / a | | | / C------ D | / c / b | |/ e / | FIGURE 3. A --------- B | |\ g | | | ---------- | | f | ---------------------- The vertex A corresponds to the outside face of Figure 2. Note that the faces of the dual correspond to the vertices of the original graph. In fact, it is not hard to see that the dual of the dual of an imbedded graph is the original graph. Also note how the existence of vertices of degree 2 in the original graph led to parallel edges in the dual. If all the faces of an imbedded graph are triangles (i.e. bounded by 3 edges) the imbedded graph is called a TRIANGULATION. The literature is divided over whether the outside face must be a triangle, but we will take it that ALL faces are triangles. The dual of a triangulation is an imbedded cubic (trivalent) graph. A triangulation with n vertices has exactly 3n-6 edges and 2n-4 faces. A graph (imbedded or not) is k-CONNECTED if it cannot be disconnected by removing fewer than k vertices. It is convenient to revise the definition slightly for the complete graph K4: it is 3-connected but not 4-connected. A standard theorem says that a triangulation is 3-connected if and only if it has no loops or parallel edges. It is impossible for a planar graph to be k-connected for k greater than 5. A graph (imbedded or not) is CYCLICALLY K-CONNECTED if it is impossible to remove k or fewer vertices so that the graph breaks into components of which at least two have cycles. As before, K4 is defined to be cyclically 3-connected but not cyclically 4-connected. Planar graphs can have arbitrarily high cyclic connectivity. In many circumstances there are relationships between the connectivity of an imbedded graph and the cyclic connectivity of its dual. For example, a triangulation is k-connected if and only if its dual is cyclically k-connected. A SIMPLE graph is one with no parallel edges or loops. INSTALLING plantri. The latest edition of plantri can be obtained from http://cs.anu.edu.au/~bdm/plantri plantri.c is a C program written as a single file plantri.c. It should compile immediately with most modern C compilers, as it only contains code that is very standard (unless your compiler is VERY old). To compile plantri.c under Unix, you can use cc -o plantri -O4 plantri.c where "4" is the highest number your compiler accepts, or just make plantri (but check makefile first). RUNNING plantri. To run plantri, you need to be able to enter command-line parameters. All our examples will use standard Unix syntax. An example of a plantri run is: plantri -d 16 which makes the duals (because -d is present) of the 3-connected triangulations with 16 vertices. In other words, it makes the 3-connected cubic planar graphs with 28 vertices. The only compulsory parameter is the number of vertices ("16" in the example). This can also be given as "28d" (the suffix 'd' means 'dual') in which case it is converted by adding 4 then dividing by 2: (28+4)/2 = 16. In the case of triangulations, this calculation yields the number of faces, which is the number of vertices in the dual cubic graph. Apart from the one compulsory parameter, there are three types of optional parameters: * SWITCHES are introduced by a '-' character. If there are more than one they can be arbitrarily concatenated or separated. They can also appear anywhere. For example, these command lines are all equivalent: plantri -m4u 10 plantri -u -m4 10 plantri 10 -um4 plantri -u 10 -m4 The meanings of the switches are explained in the next sections. In the case of a switch taking a numerical value, such as -m, giving it without a value is the same as giving value 0. That is, -m is the same as -m0 . * An OUTPUT FILE can be given, if you want the graphs to be sent somewhere other than standard output. Information other than graphs (such as statistics) is written to the standard error stream. It is permitted to use a lonely '-' to explicitly request graph output to standard output. Example: plantri 20 tri.20 --Send 20-vertex triangulations to file tri.20 * A RES/MOD pair can be given to select only a portion of the graphs that would otherwise be produced. This pair comprises two integers with '/' between, such as 13/100. The first integer can be from 0 to one less than the second number. This example selects portion 13 from portions 0, 1, ..., 99. In total, these 100 portions will be a partition of all the graphs into 100 roughly equal parts. This is provided to enable you to divide your computing task into pieces of manageable size. More information on RES/MOD pairs is given later. Parameters and switches may appear in any order with one exception: the compulsory parameter (number of vertices) must precede any output file or res/mod parameters. OUTPUT FORMATS. plantri can write graphs in a variety of different formats. PLANAR CODE is the default format. It is the preferred format if you plan to feed the graph into a program that needs the imbedding, and also convenient if you don't need the imbedding. However, it uses characters which are not printable so it is not suitable for looking at by eye. ASCII CODE is a human-readable version of planar code. The vertices of the graph are named by ASCII characters starting with 'a'. Example: 7 bcdefg,agfdc,abd,acbfe,adf,aedbg,afb This is a graph with 7 vertices a,b,c,d,e,f,g. The neighbours of 'a' in clockwise order are b,c,d,e,f,g; and so on. Each graph occupies one line of output. Ascii code is convenient if you just want to draw a few graphs by hand. To select ascii code use -a. EDGE CODE is an alternative for planar code that enables all plane graphs to be encoded unambiguously even if there are multiple loops. See Appendix B for the full definition. To select edge code use -E. DOUBLE CODE is a human-readable version of edge code, with both the primal and dual graphs appearing on the same line. It begins with the number of vertices, and then for each vertex a list of the incident edges is given in clockwise order. Then there is the number of faces and a list of the edges of each face in clockwise order. The names of the edges are A, B, C, and so on in ascii order. An example is 8 AHB BLC CJD DIE EFA FIG GKH JLK 6 ABCDE AFGH EIF DJKGI KLBH LJC which is an 8-vertex cubic graph with edges A..L, and its 6 faces. To select double code use -T. GRAPH6 is a compact code for the abstract structure of a graph. The imbedding is not represented, so this is not a suitable code to use if you want the imbedding. It is also restricted to simple graphs. graph6 is one of the formats supported by Brendan McKay's 'nauty' package. Each graph occupies one line. To select graph6 code use -g. SPARSE6 is a compact code for the abstract structure of a graph which is optimized for sparse graphs. If you don't want the imbedding and are dealing with cubic graphs of 20 or more vertices, sparse6 is a good choice. sparse6 is one of the formats supported by Brendan McKay's 'nauty' package. Each graph occupies one line. To select sparse6 code use -s. Each of those formats except for ascii code also has a standard header, which may be written to the output at the beginning: format header written by default? planar code >>planar_code<< yes edge code >>edge_code<< yes graph6 >>graph6<< no sparse6 >>sparse6<< no In each case the header is written with no end-of-line characters after it (for portability reasons). To write a header when the default is not to, or vice-versa, use -h. If you only want to count the graphs and not write them, use -u to select no output. Details of these formats is given in Appendices A-C. MISCELLANEOUS SWITCHES. -d causes the dual graph to be written instead of the original graph. Note that it is applied only at the output stage. All other switches refer to the original graph before the dual is taken. For example, -m4 (minimum degree at least 4) refers to the original graph and not to the dual. -o Normally, one member of each isomorphism class is written. If this switch is given, one member of each O-P isomorphism class is written. Since graph6 and sparse6 formats don't encode the imbedding anyway, this switch is ignored for output purposes if you use -g or -s. -o also implies -G. -G This switch is only of interest if you are using a plug-in (see Appendix D). It ensures that the full automorphism group is computed for each output graph. If you are not using a plug-in, -G will just slow things down. -V Only output graphs with non-trivial group. If -o is given, the O-P group is used. Otherwise, the full group. Implies -G. -v plantri will always tell you (by a message to standard error) the number of graphs that were produced. If you specify -v, it might tell you some additional statistical information. For example, if you use -o, -v will cause it to also inform you of the number of isomorphism classes as well as the number of isomorphism classes which are O-P isomorphic to their mirror images. SELECTING THE GRAPH CLASS. In these instructions, the word 'primal' refers to the graph you will get if you don't use -d, and 'dual' refers to the dual of that graph (which you get instead by using -d). The character # refers to a non-negative integer. We begin with a few switches available in multiple circumstances. -m# Specify a lower bound on the minimum degree. In the dual graph this means a lower bound on the minimum face size. The default is -m3. -c# Specify a lower bound on the connectivity. The meaning in the dual graph will be explained in each case. The default is -c3. (-c4 has a slightly weaker meaning with -q, see below.) -x When used in combination with -c#, the connectivity must be exactly #, rather than at least #. (Some exceptions are noted below.) Now we can explain the graph classes which can be produced by plantri. -b but not -p Select eulerian triangulations, where "eulerian" means that every vertex has even degree. -m is not available except for the default -m4 (the minimum degree is always 4 anyway). -c3 (default) 3-connected eulerian planar triangulation. The dual is a 3-connected bipartite cubic graph. -c4 4-connected eulerian planar triangulation. The dual is a cyclically 4-connected bipartite cubic graph. -c3x The difference between -c3 and -c4, namely those 3-connected eulerian planar triangulations which have a triangle that is not a face. -p but not -b Select general planar simple graphs. In the 3-connected case, these are also called convex polytopes. Note that isomorphism is defined with reference to the imbedding on a sphere, which means that outputs may be isomorphic as abstract graphs if the connectivity is less than 3. -m1 The minimum degree is at least 1. -m2 The minimum degree is at least 2. -m3 (default) The minimum degree is a least 3. -m4 The minimum degree is at least 4. -m5 The minimum degree is at least 5 (and so exactly 5). -c4 The connectivity is at least 4. -c3 (default) The connectivity is at least 3. -c2 The connectivity is at least 2. -c1 The connectivity is at least 1. -c2x The difference between -c2 and -c3, namely connectivity exactly 2. -c1x The difference between -c1 and -c2, namely connectivity exactly 1. If the -c switch is used but not the -m switch, the minimum degree is set to the same value. For example, -c2 is the same as -c2m2. If the -m switch is used but not the -c switch, 3-connectivity is assumed. This means that -m1 and -m2 are ineffective without using -c1 or -c2 as well. In addition, two limits can be imposed: -e Specify bounds on the number of edges (which is equal to the number of edges in the dual). The default is no bounds. For n vertices, the number of edges can be from ceil(3n/2) (2n for -m4, ceil(5n/2) for -m5) to 3n-6. There are four possible forms: -e# number of edges exactly # -e:# number of edges at most # -e#: number of edges at least # -e#:# number of edges from # to # Only the lower bound is efficiently implemented. Generally speaking, it is more efficient to do a range of edge counts at once rather than one edge count at a time. -f# Specify an upper bound on the size of a face (in the dual: an upper bound on the maximum degree). The default is no bound. For n vertices, the largest face size can be from 3 to n-1. -bp or -pb Select general planar simple bipartite graphs. These are a subset of the class generated by -p alone, namely those which are bipartite. The minimum degree is always at most 3, so all the parameters available with -p are available except -c4, -m4, -m5 and -f3. The duals are a subclass of planar eulerian graphs. For -c3, the duals are the 3-connected planar eulerian graphs. -P# Select triangulations of a disk. These are imbedded simple graphs with a distinguished "outer" face. The outer face can be any size (here called the disk size) but the other faces must be triangles. The argument to -P is the disk size. If no argument (or 0) is given, all disk sizes are permitted. If all disk sizes are needed, it is a lot more efficient to do them all at once rather than one at a time. Except for the outer face, all vertices must have degree at least 3. On the outer face, vertices of degree 2 may be permitted, according to the -m parameter. Also, the only 2-cuts which may exist are chords of the outer face: they are permitted for -c2 but not for -c3. Since a vertex of degree 2 on the outer face implies a chord, the combination -m2c3 is the same as -m3c3. The useful combinations of -c, -m and -x are listed: -c3m3 (default) no chords, no vertices degree 2 -c2 chords allowed, no vertices degree 2 -c2x chords required, no vertices degree 2 -c2m2 chords allowed, degree 2 allowed -c2xm2 chords required, degree 2 allowed We have c2P = c3m3P + c2xP and c2m2P = c3m3P + c2xm2P. The output graphs are labelled in such a way that v-w is an edge and the outer face is on the left when looking from v-w, where v is the first vertex and w is the second vertex. For dual output, the first vertex corresponds to the outer face. The dual graph is a graph which has every vertex of degree 3 except possibly the first vertex. When interpretting the output, remember that the outer face is distinguished and that this is taken into account in determining isomorphisms. It means, for example, that some of the outputs with outer face of size 3 will be isomorphic as abstract graphs even in the 3-connected case. -q Select simple quadrangulations. These are simple planar graphs for which every face has length 4. The dual graphs are planar quartic graphs. -x is not implemented. The useful combinations of -c and -m are listed: -c3m3 (default) 3-connected dual: 3-connected simple quartic graphs -c2m2 arbitrary dual: 4-edge-connected (maybe not simple) quartic multigraphs -c2 minimum degree 3 dual: 4-edge-connected simple quartic graphs -c4 3-connected, no non-facial 4-cycles dual: 3-connected, 6-cyclically-edge-connected (simple) quartic graphs -Q Select general quadrangulations, allowing multiple edges. No connectivity or degree restrictions are currently available. The dual graphs are general planar quartic graphs, allowing multiple edges and loops. -A Select Appolonian networks. These are simple planar triangulations that can be formed starting with K4 then repeatedly dividing a face into three by addition of a new vertex. They all have minimum degree and connectivity equal to 3. The dual graphs are cubic planar graphs which can be made from K4 by repeatedly replacing a vertex by a triangle. If -b, -q, -Q, -p, -P and -A are absent, the graphs found are triangulations only restricted by connectivity and minimum degree. In this case, there is the possibility of connectivity lower than 3. The useful combinations of -c, -m, -x and -t are: -c3m3 (default) 3-connected planar triangulation. The dual is a 3-connected planar cubic graph. Both primal and dual graphs are simple. -m5 3-connected planar triangulation with minimum degree 5. The dual is a 3-connected planar cubic graph with no faces smaller than pentagons. Both primal and dual graphs are simple. -c5 5-connected planar triangulation (implies minimum degree 5). The dual is a cyclically 5-connected planar cubic graph. Both primal and dual graphs are simple. -m5c4 4-connected planar triangulation with minimum degree 5. The The dual is a cyclically 4-connected planar cubic graph with no faces smaller than pentagons. Both primal and dual graphs are simple. -m5c3x 3-connected planar triangulation with minimum degree 5 and at least one non-facial triangle. The dual is a 3-connected planar cubic graph with no faces smaller than pentagons but at least one cyclic 3-cut. Both primal and dual graphs are simple. -m5c4x 4-connected planar triangulation with minimum degree 5 and at least one separating 4-cycle. The dual is a 4-connected planar cubic graph with no faces smaller than pentagons but at least one cyclic 4-cut. Both primal and dual graphs are simple. -m4 3-connected planar triangulation with minimum degree at least 4. The dual is a 3-connected planar cubic graph with no triangles. Both primal and dual graphs are simple. -c4 4-connected planar triangulation (implies minimum degree >= 4). The dual is a cyclically 4-connected planar cubic graph. Both primal and dual graphs are simple. -c4x, -c5x are not allowed (but see -m5c4x). -m4c3x 3-connected planar triangulation with minimum degree at least 4 and at least one non-facial triangle. The dual is a 3-connected planar cubic graph with no triangles but at least one cyclic 3-cut. Both primal and dual graphs are simple. -c2 2-connected planar triangulation with minimum degree at least 3. There may be parallel edges (but remember it is a triangulation so there must be things between each pair of them). There are no loops. The dual is a 2-connected simple planar cubic graph. -c2x Same as -c2 except that there must be at least one pair of parallel edges. In the dual, at least one cutset of size 2. -m2c2 2-connected planar triangulation with minimum degree at least 2. There can be parallel edges but no loops. The dual is a 2-connected planar cubic graph which may have multiple edges but has no loops. In the case of -c1, there is an extra switch -t which changes the class. For a triangulation a "special configuration" consists of two faces that consist of a double edge with a loop inside at one end and a loop outside at the other end. In the dual cubic graph, this corresponds to a double edge which does not bound a face (so it has an edge pointing inside at one end and an edge pointing outside at the other end). In all cases, special configurations are allowed if -t is used and forbidden otherwise. In these descriptions loops and double edges are permitted except as indicated. -c1 (same as -m3c1) Planar triangulation with minimum degree at least 3 and no special configurations. The dual is a planar cubic graph no non-facial 2-cycles. -c1t (same as -m3c1t) Arbitrary planar triangulation with minimum degree at least 3. The dual is an arbitrary planar cubic graph. -m2c1 Planar triangulation with minimum degree at least 2 but no special configurations. The dual is a planar cubic graph with no loops or non-facial 2-cycles. -m2c1t Planar triangulation with minimum degree at least 2. The dual is a planar cubic graph with no loops. -m1c1 Planar triangulation with no special configurations. The dual is a planar cubic graph with no non-facial 2-cycles. -m1c1t Arbitrary planar triangulation. The dual is an arbitrary planar cubic graph. We have c2 = c2x + c3, c1 = c1x + c2, and c1t = c1tx + c2. Also m2c1 = m2c1x + m2c2 and m1c1 = m1c1x + m1c2. Also m2c1t = m2c1tx + m2c2 and m1c1t = m1c1tx + m1c2. Also m4 = m4c3x + c4, m5c4 = m5c4x + c5, and m5 = m5c4x + m5c3x + c5. MORE ON RES/MOD SPLITTING. The feature selected by the optional res/mod parameter to plantri is one of its greatest strengths. The set of objects is divided into mod disjoint classes and only the res-th class is generated. It is necessary that 0 <= res <= mod-1. The splitting is designed so that the overhead is at most 5 seconds per run for a 500MHz machine. Also, for problems where there are very many objects altogether, the value of mod can be at least as large as 10,000 and still have reasonable uniformity of class size. The definition of the classes obeys the normal laws of modulo arithmetic. For example, class 1/5 is the union of 1/10 and 6/10 (since the numbers equal to 1 modulo 5 are the numbers equal to 1 or 6 modulo 10). This enables classes to be further split into smaller pieces if the need arises. To determine the actual cost of splitting, and the maximum number of classes available, run the program plantri_s (known to the makefile). For example: % plantri_s -b 30 9030731 splitting cases at level=24; cpu=7.63 sec This says that splitting into up to 9030731 cases is feasible (though the splitting won't be very uniform if you use that many) and the cost of the splitting is about 7.6 seconds for each run. (In this case, it means that using 400 classes incurs a splitting penalty of only one percent.) Plugins can change the splitting level by defining splithint in the expansion of PLUGIN_INIT. The switch -X increases the splitting level by 1 if possible, making the splitting more uniform at the cost of more overhead. You can repeat it, as in -XX. APPENDIX A. Definition of PLANAR CODE. PLANAR CODE is the default output format for plantri. The vertices of the graph are numbered starting at 1. PLANAR CODE represents the graph by a series of bytes, whose unsigned numerical values (0..255) are significant. The first byte gives the number of vertices n. Then there are n sections, where section v contains the neighbours of vertex v in clockwise order followed by a zero byte. There is no end-of-line character appended. For example, the graph of Figure 1 is represented by the following byte values: 5 3 4 0 3 5 0 1 4 5 2 0 1 5 3 0 2 3 4 0 In case there are parallel edges, there might be more than one graph whose PLANAR CODE is the same up to rotation of the neighbour lists. To resolve this ambiguity, plantri makes the following convention: for each vertex v except for the first vertex, if the least numbered vertex that has v as a neighbour is w, then the first w in the section for v represents the same edge as the first v in the section for w. In case of all the graph classes generated by plantri that have no multiple loops, and also for all classes of triangulations, it can be proved that for every v > 1 we have w < v and the embedded graph is uniquely reconstructible from the code. In addition to the encodings of graphs, a PLANAR CODE file by default begins with the 15 characters >>planar_code<< without end-of-line characters. APPENDIX B. Definition of EDGE CODE. EDGE CODE is an alternative to PLANAR CODE that has the advantage of being uniquely decodable for all plane graphs (even with multiple loops). The undirected edges are numbered 0,1,... consecutively but in no particular order, and for each vertex a list of the incident edge numbers in clockwise order is given. Note that a loop appears twice in such a list, and in general each edge number appears exactly twice altogether. The code consists of a header and a body. The header has one of two forms: 1. A single byte of value 1-255. In this case, the value of the byte is the size of the body in bytes. All edge numbers in the body will be encoded using L=1 bytes. 2. The byte 0, a byte (K<<4)+L (where 1<=K,L<=15), and a bigendian unsigned number S stored in K bytes. In this case, S is the size of the body in bytes and L is the number of bytes used for edge numbers in the body. The size of the header is 1+1+K bytes. The body has a section for each vertex. In each section, the edge numbers for the incident edges are given in clockwise order, using an L-byte bigendian integer for each. Each vertex section except the last is followed by a single byte of value 255. (Note that this implies L is large enough that the largest edge number has first byte value at most 254.) In plantri, the only possibility for the second header type is K=2, L=1. In addition to the encodings of graphs, an EDGE CODE file by default begins with the 13 characters >>edge_code<< without end-of-line characters. APPENDIX C. Definition of GRAPH6 and SPARSE6. All numbers in this description are in decimal unless obviously in binary. GRAPH6 and SPARSE6 are text formats, and a file containing them is a text file. Apart from the header, there is one object per line. Apart from the header and the end-of-line characters, all bytes have a value in the range 63-126 (which are all printable ASCII characters). BIT VECTORS: A bit vector x of length k can be represented as follows. Example: 1000101100011100 (1) Pad on the right with 0 to make the length a multiple of 6. Example: 100010110001110000 (2) Split into groups of 6 bits each. Example: 100010 110001 110000 (3) Add 63 to each group, considering them as bigendian binary numbers. Example: 97 112 111 These values are then stored one per byte. So, the number of bytes required is ceiling(k/6). Let R(x) denote this representation of x as a string of bytes. SMALL NONNEGATIVE INTEGERS: Let n be an integer in the range 0-262143 (262143 = 2^18-1). If 0 <= n <= 62, define N(n) to be the single byte n+63. If n >= 63, define N(n) to be the four bytes 126 R(x), where x is the bigendian 18-bit binary form of n. Examples: N(30) = 93 N(12345) = N(000011 000000 111001) = 126 69 63 120 GRAPH6 format: Suppose G has n vertices. Write the upper triangle of the adjacency matrix of G as a bit vector x of length n(n-1)/2, using the ordering (0,1),(0,2),(1,2),(0,3),(1,3),(2,3),...,(n-1,n). Then the graph is represented as N(n) R(x). Example: Suppose n=5 and G has edges 0-2, 0-4, 1-3 and 3-4. x = 0 10 010 1001 Then N(n) = 68 and R(x) = R(010010 100100) = 81 99. So, the graph is 68 81 99. Note that GRAPH6 format cannot represent loops or parallel edges. SPARSE6 format: The encoded graph consists of: (1) The character ':'. (This is present to distinguish the code from GRAPH6 format.) (2) The number of vertices. (3) A list of edges. (4) end-of-line Loops and multiple edges are supported, but not directed edges. Number of vertices n: Represented as N(n) like in GRAPH6 format. List of edges: Let k be the number of bits needed to represent n-1 in binary. The remaining bytes encode a sequence R(z) where z = b[0] x[0] b[1] x[1] b[2] x[2] ... b[m] x[m] ... Each b[i] occupies 1 bit, and each x[i] occupies k bits. Padding at the end is chosen so that the decoding algorithm below does not imply any spurious edges. The vertices of the graph are 0..n-1. The edges encoded by this sequence are determined thus: v = 0 for i from 0 to m do if b[i] = 1 then v = v+1 endif; if x[i] > v then v = x[i] else output {x[i],v} endif endfor Example: :Fa@x^ ':' indicates sparse6 format. Subtract 63 from the other bytes and write them in binary, six bits each. 000111 100010 000001 111001 011111 The first byte is not 63, so it is n. n=7 n-1 needs 3 bits (k=3). Write the other bits in groups of 1 and k: 1 000 1 000 0 001 1 110 0 101 1 111 This is the b/x sequence 1,0 1,0 0,1 1,6 0,5 1,7. The 1,7 at the end is just padding. The remaining pairs give the edges 0-1 1-2 5-6. APPENDIX D. Writing Plug-ins for plantri. plantri has a facility for making certain compile-time changes to its behaviour. This requires some amount of knowledge of how the program works, and here we will give a little of that. A typical use for a plug-in is to filter the output graphs before they are written. This is a good idea if you are only wanting some subset of the graphs, because plantri is so fast that writing graphs out and reading them into another program takes about as long as generating them. Vertices in plantri are numbered starting at 0. There are global variables nv and ne which contain the number of vertices and the number of DIRECTED edges (which is twice the number of edges). In the case of disk triangulations, there are some occasions when one vertex number is unused. In this case, the global int variable missing_vertex indicates what is missing. If nothing is missing, missing_vertex < 0. For example, if nv=7 and missing_vertex=2, the vertices are actually numbered 0,1,3,4,5,6,7. The graph is held as a collection of directed edges (type EDGE). These edges are structures referenced by pointers. They have these fields, amongst others: int start; the vertex at the start of the edge int end; the vertex at the end of the edge EDGE *invers; the directed edge which is the reverse of this one EDGE *next; the next edge in clockwise order around vertex start EDGE *prev; the previous edge in clockwise order around vertex start To find the edges, there is an array firstedge[0..], type EDGE*. The value of firstedge[i] is a pointer to one of the edges starting at vertex v. For example, to "look at" all the neighbours of vertex v we can do: EDGE *e,*elast; e = elast = firstedge[v]; do { look at e->end; e = e->next; } while (e != elast); Another example is the tracing of a face. Suppose we have an edge e and we want to "look at" all the edges bounding the face on the right of e. elast = e; do { look at e; e = e->invers->prev; } while (e != elast); Use e = e->invers->next instead if you are interested in the face on the left of e. Another useful global array is degree[0..], which contains the degrees of the vertices. Another way to "look at" all the neighbours of vertex v is this: for (count = degree[v], e = firstedge[v]; --count >= 0; e = e->next) { look at e->end } To write a plug-in, you need to define some things in a separate source file (let's call it plugin.c), and make the name of that source file available when compiling plantri.c. For example, on most Unix systems: cc -o plantri_plugin -O4 '-DPLUGIN="plugin.c"' plantri.c All the quotes of both types are required. This process causes the text of plugin.c to be read into the text of plantri.c, so everything defined in each file is available in both. The work of the plug-in is achieved by defining macros. Here we list the macros that might be defined, and their meanings. If you don't want these functions, just don't define the macros. FILTER This is the name of a procedure that is called for each isomorphism type of graph that would normally be output (except that in the case of -d it is the original graph before taking the dual). The calling sequence is like this: int FILTER(int nbtot, int nbop, int doflip) The procedure must return an int value. If the value 0 is returned, the graph is not written. Otherwise it is written. The meanings of the parameters: nbtot = total number of automorphisms nbop = number of canonical labellings which are O-P. If there are O-R automorphisms, nbop=nbtot/2, while if there are none nbop=0 or nbop=nbtot. doflip = 0 if there is an orientation-reversing automorphism, otherwise 1 nbtot, nbop, doflip are only guaranteed correct if -G or -o is given. In that case the full automorphism group is available; contact the authors for details. Without -G and -o, doflip=0 and the other parameters are undefined. These rules mean that doflip+1 is the number of graphs which are to be written (except for the imbedding-insensitive formats graph6 and sparse6, for which only one will be written). If you are using FILTER to count outputs with a particular property, count each graph with a weight of doflip+1. This procedure can be used to write the graph in another format. The normal output file (an open text file) is outfile, except if -u is given, in which case you will have to open a file yourself or use stdout. SUMMARY This is called at the end of the computation before the final summary statistics are produced by plantri. Type: void SUMMARY(void) Its main use is to write information gathered by FILTER and other plug-in components. If you don't want the normal summary as well, set the global variable dosummary to 0 before returning. Look in plantri.c to see how statistics are collected and written. All statistics should be written to the file msgfile. PLUGIN_INIT This is called at the start of execution, after the command-line switches have been decoded but before any graphs are generated. You can use it to perform tasks such as: (a) Test if the switches are valid for this plug-in. (b) Set switch values to appropriate default values. (c) Initialize data-structures used by this plug-in. PLUGIN_SWITCHES This can be defined to add extra switches. The mechanism for detecting switches, and their values, can be best seen by examining plantri.c. Here are two simple cases: (a) Add a boolean switch -z: #define PLUGIN_SWITCHES else if (arg[j] == 'z') zswitch = TRUE; (b) Add a switch -z that takes an integer value: #define PLUGIN_SWITCHES else if (arg[j] == 'z') \ zvalue = getswitchvalue(arg,&j); In each case you have to define and initialize the new variables. You can do that at the top level in plugin.c: (a) static int zswitch = FALSE; (b) static int zvalue = -1; Checking that zvalue is valid, or giving it a default value if it is not specified (i.e. is still -1), can be done using PLUGIN_INIT. If you change the switches, you should also redefine the macro SWITCHES that appears in the first line of plantri.c. It is only used in error messages. PRE_FILTER_* These are the most difficult macros to use, as considerable knowledge of the internals of the program is required. plantri operates by starting with the smallest graphs in the required class, then expanding them by a few vertices at a time until the output size is reached. The exact method for expanding a graph depends on the graph class. The value of PRE_FILTER_* is an expression that is evaluated for each intermediate graph computed during the generation process that is smaller (or less constructed in some other sense) than the output size. If the value of the expression is 0, that intermediate graph is not expanded (so none of its descendants appear in the output). If the value is not 0, expansion proceeds as normal. The actual macros available are PRE_FILTER_SIMPLE, PRE_FILTER_MIN4, PRE_FILTER_BIP, PRE_FILTER_POLY, PRE_FILTER_DOUBLE, PRE_FILTER_ORDLOOP, PRE_FILTER_SPECIALLOOP, PRE_FILTER_QUAD, PRE_FILTER_MIN5. A few more complex macros are available, but describing them would require too much detail about plantri internals. Some examples of plug-ins are distributed with plantri: mdcount.c (makes plantri_mdcount) - count graphs by minimum degree degseq.c (makes plantri_deg) - counts graphs by degree sequence nft.c (makes plantri_nft) - counts graphs by non-facial triangles maxdeg.c (makes plantri_md) - imposes a bound on the maximum degree allowed_deg.c (makes plantri_ad) - specify which degrees are permitted faceorbits.c (makes plantri_fo) - count plane imbeddings with distinguished outer face APPENDIX E. Graph Counts. In this section we list some counts of the graph classes that can be generated using plantri. If you compute any additional numbers in any of these classes, please send them to us for inclusion. The column headings in these tables are: nv = number of vertices (or faces in the dual) ne = number of edges (same in the dual) nf = number of faces (or vertices in the dual) all = count of isomorphism classes O-P = count of orientation-preserving isomorphism classes. ---------------------------------------------------------------- 3-connected planar triangulations. nv ne nf all O-P 4 6 4 | 1 1 5 9 6 | 1 1 6 12 8 | 2 2 7 15 10 | 5 6 8 18 12 | 14 17 9 21 14 | 50 73 10 24 16 | 233 389 11 27 18 | 1249 2274 12 30 20 | 7595 14502 13 33 22 | 49566 97033 14 36 24 | 339722 672781 15 39 26 | 2406841 4792530 16 42 28 | 17490241 34911786 17 45 30 | 129664753 259106122 18 48 32 | 977526957 1954315346 19 51 34 | 7475907149 14949368524 20 54 36 | 57896349553 115784496932 21 57 38 | 453382272049 906736988527 22 60 40 | 3585853662949 7171613842488 23 63 42 | 28615703421545 57231089062625 ---------------------------------------------------------------- 3-connected planar triangulations with minimum degree at least 4, (plantri -m4), and 4-connected planar triangulations (plantri -c4). m4 c4 nv ne nf all O-P all O-P 6 12 8 | 1 1 | 1 1 7 15 10 | 1 1 | 1 1 8 18 12 | 2 2 | 2 2 9 21 14 | 5 5 | 4 4 10 24 16 | 12 14 | 10 12 11 27 18 | 34 45 | 25 32 12 30 20 | 130 194 | 87 128 13 33 22 | 525 891 | 313 519 14 36 24 | 2472 4499 | 1357 2430 15 39 26 | 12400 23603 | 6244 11765 16 42 28 | 65619 127887 | 30926 59915 17 45 30 | 357504 705770 | 158428 311744 18 48 32 | 1992985 3959653 | 836749 1659633 19 51 34 | 11284042 22494163 | 4504607 8971845 20 54 36 | 64719885 129227103 | 24649284 49195863 21 57 38 | 375126827 749646288 | 136610879 272940855 22 60 40 | 2194439398 4387116659 | 765598927 1530417953 23 63 42 | 12941995397 25878895923 | 4332047595 8661936137 24 66 44 | 76890024027 153765144588 | 24724362117 49442678322 25 69 46 | 459873914230 919704309272 | 142205424580 284393946501 26 72 48 | 2767364341936 5534600480206 | 823687567019 1647327455726 27 75 50 | 16747182732792 | 4801749063379 Note: An earlier version of this table gave a different value for the first count on the nv=23 row. That was due to a clerical error and not to a program bug. ---------------------------------------------------------------- planar triangulations without 3-connectivity requirement. A "special configuration" is two faces formed by a pair of parallel edges with a loop inside one end and a loop outside the other end. conn = a lower bound on the connectivity delta = a lower bound on the minimum degree conn=2 delta=3 (plantri -c2) conn=1 delta=3 and no special configuration (plantri -c1) conn=1 delta=3 (plantri -c1t). conn=2 delta=2 (plantri -m2c2) conn=1 delta=2 and no special configuration (plantri -m2c1) conn=1 delta=2 (plantri -m2c1t). conn=1 delta=1 and no special configuration (plantri -m1c1) conn=1 delta=1 (plantri -m1c1t). c2 nv all O-P 4 | 1 1 5 | 1 1 6 | 3 3 7 | 8 9 8 | 32 37 9 | 131 183 10 | 723 1156 11 | 4360 7713 12 | 29632 55436 13 | 213168 412193 14 | 1606633 3158392 15 | 12473723 24736138 16 | 99141919 197448348 17 | 802392930 1601481238 18 | 6593377305 13173471151 19 | 54883010885 109712447949 20 | 462038444588 923858502128 21 | 3928893849911 7856893675780 c1 c1t nv all O-P all O-P 4 | 1 1 | 1 1 5 | 1 1 | 1 1 6 | 3 3 | 3 3 7 | 9 10 | 9 10 8 | 37 42 | 38 43 9 | 172 230 | 178 236 10 | 993 1523 | 1041 1577 11 | 6308 10737 | 6652 11188 12 | 44145 80319 | 46738 84194 13 | 327051 620134 | 347050 653271 14 | 2530761 4913112 | 2691419 5198809 15 | 20179785 39705720 | 21509955 42184083 16 | 164672106 326420796 | 175969274 348088277 17 | 1368137926 2723097802 | 1465921468 2913967487 18 | 11536196188 23012381739 | 12395111621 24706425434 19 | 98494508358 196713776094 | 106126249031 211856940558 20 | 850073936750 1698875856077 | 918520748281 1835160731391 21 | 7406965136219 14808015829668 | 8025676381104 16042357404748 m2c2 nv all O-P 3 | 1 1 4 | 2 2 5 | 4 4 6 | 14 14 7 | 54 66 8 | 291 409 9 | 1873 3078 10 | 14468 26044 11 | 123730 235054 12 | 1139820 2223598 13 | 11012340 21770878 14 | 110159674 219136678 15 | 1131227001 2256904588 16 | 11864336461 23702178103 17 | 126639415621 253151362072 18 | 1372246820875 2743873167600 19 | 15065904311738 30128766834832 m2c1 m2c1t nv all O-P all O-P 3 | 1 1 1 1 4 | 2 2 2 2 5 | 5 5 5 5 6 | 19 19 20 20 7 | 94 112 100 118 8 | 581 802 634 862 9 | 4297 6864 4738 7451 10 | 36388 63985 40412 70132 11 | 337952 630270 376812 696162 12 | 3349489 6455215 3749104 7180627 13 | 34738800 68154023 39044043 76306202 14 | 372459154 737599845 420546653 830919184 15 | 4096051566 8151111206 4647701181 9236590422 16 | 45968549270 91704568206 52427373251 104510610443 17 | 524625804817 1047919071939 601467756683 1200901913663 18 | 6073627332266 12139545642813 6999845695102 13987563528656 m1c1 m1c1t nv all O-P all O-P 3 | 2 2 2 2 4 | 5 5 6 6 5 | 21 22 25 26 6 | 125 154 156 191 7 | 997 1502 1272 1904 8 | 9906 17017 12924 22078 9 | 115036 213553 152706 282388 10 | 1478952 2855841 1997650 3848001 11 | 20342243 40036445 27960796 54953996 12 | 293294847 582364274 410416310 814302292 13 | 4378778380 8729474470 6239790783 12434664412 14 | 67181358581 134172729792 97510238990 194705958478 15 | 1053929763051 2106555903824 1558296770458 3114359909400 16 | 16846298319763 25375343842763 50734620915690 ---------------------------------------------------------------- 3-connected planar Eulerian triangulations (plantri -b), and 4-connected planar Eulerian triangulations (plantri -bc4). b bc4 nv ne nf all O-P all O-P 6 12 8 | 1 1 | 1 1 7 15 10 | 0 0 | 0 0 8 18 12 | 1 1 | 1 1 9 21 14 | 1 1 | 0 0 10 24 16 | 2 2 | 2 2 11 27 18 | 2 2 | 1 1 12 30 20 | 8 9 | 5 6 13 33 22 | 8 11 | 3 3 14 36 24 | 32 41 | 18 22 15 39 26 | 57 89 | 19 25 16 42 28 | 185 296 | 79 112 17 45 30 | 466 829 | 134 214 18 48 32 | 1543 2772 | 501 817 19 51 34 | 4583 8746 | 1147 2058 20 54 36 | 15374 29461 | 3976 7188 21 57 38 | 50116 98342 | 11055 21036 22 60 40 | 171168 336881 | 37231 71185 23 63 42 | 582603 1156559 | 114560 224103 24 66 44 | 2024119 4024297 | 384053 753561 25 69 46 | 7057472 14075250 | 1244056 2464355 26 72 48 | 24873248 49638364 | 4193857 8321649 27 75 50 | 88111772 176037177 | 13977946 27841706 28 78 52 | 314301078 628107157 | 47522279 94737950 29 81 54 | 1126716000 2252541666 | 161222224 321889797 30 84 56 | 4060375677 8118442511 | 553033544 1104620101 31 87 58 | 14697571234 29390845869 | 1899744032 3796766424 32 90 60 | 53432834170 106854715443 | 6571595339 13136256710 33 93 62 | 195015189626 390009407529 | 22793047258 45572625554 34 96 64 | 714404259151 1428755867040 | 79449718217 158865787212 35 99 66 | 2626130395699 5252157292165 | 277760027418 555452882736 36 102 68 | 9685071313079 | 974836112457 ---------------------------------------------------------------- Convex polytopes (3-connected planar simple graphs, plantri -p), and convex polytopes with minimum degree at least 4 (plantri -pm4). p pm4 nv all O-P all O-P 4 1 1 | 5 2 2 | 6 7 8 | 1 1 7 34 45 | 1 1 8 257 419 | 4 4 9 2606 4798 | 14 16 10 32300 62754 | 67 99 11 440564 872411 | 428 720 12 6384634 12728018 | 3515 6531 13 96262938 192324654 | 31763 61677 14 1496225352 2991463239 | 307543 607787 15 23833988129 47663036427 | 3064701 6101800 16 387591510244 775158142233 | 31199068 62288750 17 6415851530241 12831576165782 | 322264655 644101914 18 107854282197058 | 3369911732 6738127018 19 | 35611596455 71216447022 20 | 379881408164 759735751770 21 | 4086847012014 8173585336482 ---------------------------------------------------------------- Triangulations of a disk: 3-connected (plantri -P), or exactly 2-connected but without vertices of degree 2 (plantri -Pc2x), or exactly 2-connected with vertices of degree 2 on the outer face permitted (plantri -Pc2m2). P nv all O-P 4 1 1 5 2 2 6 7 8 7 27 37 8 132 213 9 773 1386 10 5017 9524 11 34861 68057 12 253676 501858 13 1903584 3788747 14 14616442 29170667 15 114254053 228295618 16 906266345 1811802818 17 7277665889 14552804492 18 59066524810 118124257451 19 483864411124 967698049455 20 3996427278475 7992746427963 21 33250623548406 66500865364037 Pc2x Pc2xm2 nv all O-P all O-P 3 | 1 1 4 | 1 1 5 | 2 2 6 1 1 | 9 12 7 4 5 | 36 56 8 27 42 | 196 341 9 163 289 | 1160 2168 10 1131 2130 | 7616 14732 11 8030 15631 | 52605 103619 12 59412 117319 | 379339 753336 13 448361 891666 | 2814161 5610649 14 3447550 6877352 | 21363658 42666989 15 26887369 53713758 | 165164873 330125084 16 212338376 424461698 | 1296637273 2592566706 17 1695218973 3389687444 | 10312933521 20623423424 18 13666153626 27329645755 | 82959235392 165909929181 19 111136594337 222263795690 | 674004472100 1347979078869 20 910959545329 1821885598755 | 5524400982592 11048696658907 21 7520705838434 15041292477945 | 45637448298918 91274524809807 ---------------------------------------------------------------- 3-connected planar triangulations with minimum degree 5 (plantri -m5), and 3-connected planar graphs (convex polytopes) with minimum degree 5 (plantri -pm5). triangulations polytopes nv ne nf all O-P all O-P 12 30 20 | 1 1 | 1 1 13 33 22 | 0 0 | 0 0 14 36 24 | 1 1 | 1 1 15 39 26 | 1 1 | 1 1 16 42 28 | 3 4 | 5 6 17 45 30 | 4 4 | 8 8 18 48 32 | 12 17 | 30 46 19 51 34 | 23 33 | 85 135 20 54 36 | 73 117 | 392 686 21 57 38 | 192 331 | 1587 2961 22 60 40 | 651 1180 | 7657 14744 23 63 42 | 2070 3899 | 36291 71207 24 66 44 | 7290 14052 | 180444 357308 25 69 46 | 25381 49667 | 898310 1787611 26 72 48 | 91441 180502 | 4532719 9042238 27 75 50 | 329824 654674 | 22949165 45839601 28 78 52 | 1204737 2398527 | 116805726 233457359 29 81 54 | 4412031 8800984 | 596228948 1192066180 30 84 56 | 16248772 32447008 | 3052696452 6104366484 31 87 58 | 59995535 119883207 | 15667197926 31331752928 32 90 60 | 222231424 444226539 | 80591725752 161176530535 33 93 62 | 825028656 1649550311 | 415411427833 830804928594 34 96 64 | 3069993552 6138874486 | 2145396827091 4290746578254 35 99 66 | 11446245342 22890091062 | 11100060860777 22199999305869 36 102 68 | 42758608761 85511947468 | 37 105 70 | 160012226334 320013030067 | 38 108 72 | 599822851579 1199620598580 | 39 111 74 | 2252137171764 4504219709753 | 40 114 76 | 8469193859271 16938267502048 | A previous version of this table had the nv=29 value 8800984 incorrect for unknown reasons. It does seem that the program always got the right answer. ---------------------------------------------------------------- 3-connected planar quadrangulations (plantri -q). quadrangulations nv ne nf all O-P 8 12 6 | 1 1 9 14 7 | 0 0 10 16 8 | 1 1 11 18 9 | 1 1 12 20 10 | 3 4 13 22 11 | 3 3 14 24 12 | 11 15 15 26 13 | 18 25 16 28 14 | 58 92 17 30 15 | 139 234 18 32 16 | 451 803 19 34 17 | 1326 2469 20 36 18 | 4461 8512 21 38 19 | 14554 28290 22 40 20 | 49957 98148 23 42 21 | 171159 338673 24 44 22 | 598102 1188338 25 46 23 | 2098675 4180854 26 48 24 | 7437910 14840031 27 50 25 | 26490072 52904562 28 52 26 | 94944685 189724510 29 54 27 | 341867921 683384218 30 56 28 | 1236864842 2472961423 31 58 29 | 4493270976 8984888982 32 60 30 | 16387852863 32772085447 33 62 31 | 59985464681 119963084542 34 64 32 | 220320405895 440623586740 35 66 33 | 811796327750 1623555117611 36 68 34 | 3000183106119 6000283550482 (In a previous version of this table, the two values for nv=31 were interchanged. Thanks to Hugo Pfoertner for noticing.) ---------------------------------------------------------------- General quadrangulations (plantri -Q) nv ne nf all O-P 3 2 1 | 1 1 4 4 2 | 3 3 5 6 3 | 7 7 6 8 4 | 30 33 7 10 5 | 124 156 8 12 6 | 733 1070 9 14 7 | 4586 7515 10 16 8 | 33373 59151 11 18 9 | 259434 483925 12 20 10 | 2152298 4136964 13 22 11 | 18615182 36416865 14 24 12 | 166544071 329048627 15 26 13 | 1528659536 3037029030 16 28 14 | 14328433429 28553451498 17 30 15 | 136649176084 272766018806 18 32 16 | 1322594487342 2642420298576 19 34 17 | 12965736092988 25916954091582 20 36 18 | 128543259338048 257009789443925 ---------------------------------------------------------------- Appolonian networks. nv ne nf all O-P 4 6 4 | 1 1 5 9 6 | 1 1 6 12 8 | 1 1 7 15 10 | 3 4 8 18 12 | 7 10 9 21 14 | 24 40 10 24 16 | 93 171 11 27 18 | 434 831 12 30 20 | 2110 4147 13 33 22 | 11002 21822 14 36 24 | 56713 116062 15 39 26 | 321776 642600 16 42 28 | 1792133 3582322 17 45 30 | 10131027 20256885 18 48 32 | 57949430 115888201 19 51 34 | 334970205 669911568 20 54 36 | 1953890318 3907720521 21 57 38 | 11489753730 22979343010 22 60 40 | 68054102361 136107859377 23 63 42 | 405715557048 811430160282 ---------------------------------------------------------------- APPENDIX F. Version History The original edition of plantri, which performed only a few of the functions of the current edition, was released in June 1996. Here we will list the changes made in the functionality of recent editions only. Internal changes are listed in plantri.c. Version 3.0: Released on April 25, 2000. Version 3.1: Released on July 3, 2000. It was discovered by Thom Sulanke that the code for simple triangulations stopped working correctly at 26 or more vertices. The bug does not affect any of the calculation sizes listed in Appendix E. We believe that the only possible way of encountering the bug with the distributed software was to use the maxdeg or allowed_deg programs for 26 or more vertices. Correct operation with -m4, -c4, -b and the min5 plugin was not affected. Version 3.1 corrects the bug without otherwise changing program behaviour. Many thanks to Thom for his assistance. Version 4.0: Released on April 20, 2001. Added -q for 3-connected quadrangulations. Added -pc1 and -pc2 for general planar graphs. Added -m5 and variants. The plug-in min5.c is no longer required. sparse6 output now represents loops only once. Version 4.1: Released on November 30, 2001. Added -qc2, -qc4, -qm2c2 for types of quadrangulation. Version 4.3: Released on August 5, 2007. Added -V : write only those with non-trivial groups Added -E : write output in edge code Added -bp : general bipartite graphs -p can now make graphs of 2 or 3 vertices Version 4.4: Released on May 2, 2009. Fixed -pc1x and -pc2x Fixed incorrect connectivity computation in -p and -pb, only known problems were with -c1x, -c2x and statistics reported by -v Version 4.5: Released on September 5, 2011. Also apply FAST_FILTER_* to starting graphs (all uses need checking against the code as more than one filter might need defining) Version 4.6: Minor internal changes only. Version 4.7: Released on March 8, 2014. Added Appolonian graphs. Version 5.0: Released on October 2, 2016. Added 4-connected polytopes (-pc4). Version 5.2: Released on February 28, 2018. Added -E for text edgecode output. Fixed case -m4c3x which didn't work as advertised. Fixed the group of the gyro (triangulation with 3 vertices and one loop). Readjusted all splitting levels. Version 5.3: Released on May 17, 2022. An error in splitting for cases -q and -pb could cause some graphs to be output multiple times in version 5.2 (but not earlier). Also removed erroneous interpretation of CLOCKS_PER_SEC. Version 5.4: Released on March 10, 2023. -Q was added for general quadrangulations. ---------------------------------------------------------------- APPENDIX G. Copyright and license This is the copyright statement for plantri and associated utilities. Copyright is jointly held by the authors Gunnar Brinkmann, University of Gent, gunnar.brinkmann@ugent.be Brendan McKay, Australian National University, brendan.mcKay@anu.edu.au Licensed under the Apache License, Version 2.0 (the "License"); you may not use this software except in compliance with the License. A copy of the License is included in the package and you can also view it at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.