Guide to using surftri. Version 0.987 - July 2015 Surftri generates certain types of graphs that are embedded in surfaces for which the irreducible triangulations are known. Surftri is based extensively on the code, data structures, and ideas taken from plantri. The latest edition of plantri is available from the plantri page http://cs.anu.edu.au/~bdm/plantri . The authors of plantri are: Gunnar Brinkmann and Brendan McKay. The author of surftri is Thom Sulanke (tsulanke@indiana.edu). ---------------- Below is a list of the main changes for running surftri rather than plantri. See the plantri guide for more details at http://cs.anu.edu.au/~bdm/plantri The syntax for running surftri is: surftri [-uaAgsh -c#xm#pe#f# -od -v -n] n g [res/mod] [outfile] There are surftri switches which are not present in plantri: -n The surface is non-orientable. The default when -n is not present is that the surface is orientable. -A Similar to the "-a" switch. The upper case version of a letter indicates that the vertices have opposite orientations. For example, K_6 embedded in the projective plane can be specified with the ASCII CODE: 6 bcdef,afDEc,abEFd,acFBe,adBCf,aeCDb The first occurance of "D" indicates that vertices b and d have opposite orientations across the edge bd. For some non-triangulations of non-orientable surfaces this additional information is required to correctly represent the embedding. The additional parameter g is required by surftri. It is the genus of the surface. If the -n switch is not present then the surface is orientable and has g handles. If the -n switch is present then the surface is non-orientable and has g crosscaps. With -p switch all generated maps are 2-cell embedding. The -c switch has a slightly different meaning in surftri. If the interior of every face of an embedded graph is isomorphic to a disk then the graph is c1 (2-cell embedding). If for every face of a c1 embedded graph every vertex occurs at most once on its boundary then the graph is c2 (closed 2-cell embedding). If for every pair of faces of a c2 embedded graph the intersection of the two faces is either empty, a vertex, an edge, or a face then the graph is c3. The plantri switches which are not present in surftri are -G, -m# for # > 4, -o when -n is present, -b, -P#. Surftri reads the irreducible triangulations from a file genus.alpha where is the genus of the surface if orientable or the negative of the genus if the surface is non-orientable. When the "-m4" switch is used then the 4-irreducible triangulations are read from genus0m4.alpha. These filenames can also be links. When general graphs are being generated (-p) a file genus.holes is also read. This file contains irreducible maps. When quadrangulations are being generated (-q) a file genus.quad is read. This file contains irreducible quadragulations. Included in the surftri source tar file are: surftri.c surftri c source extend.c more source code for surftri makefile make file to build surftri surftri-guide.txt this file genus0.alpha irreducible triangulations of the sphere genus0m4.alpha 4-irreducible triangulations of the sphere genus-1.alpha irreducible triangulations of the projective plane genus1.alpha irreducible triangulations of the torus genus-2.alpha irreducible triangulations of the Klein bottle genus0.holes irreducible maps of the sphere (empty) genus1.holes irreducible maps of the torus genus-1.holes irreducible maps of the projective plane genus-2.holes irreducible maps of the Klein bottle genus0.quad irreducible quadragulations of the sphere genus1.quad irreducible quadragulations of the torus genus-1.quad irreducible quadragulations of the projective plane genus-2.quad irreducible quadragulations of the Klein bottle Available from the URL given below are: genus2.alpha.gz irreducible triangulations, orientable, genus 2, all genus3.10-11.alpha.gz irreducible triangulations, orientable, genus 3, n=10,11 genus3.10-12.alpha.gz irreducible triangulations, orientable, genus 3, n=10-12 genus4.11-12.alpha.gz irreducible triangulations, orientable, genus 4, n=11,12 genus5.12.alpha.gz irreducible triangulations, orientable, genus 5, n=12 genus6.12.alpha.gz irreducible triangulations, orientable, genus 5, n=12 genus-3.alpha.gz irreducible triangulations, non-orientable, genus 3, all genus-4.alpha.gz irreducible triangulations, non-orientable, genus 4, all genus-5.9-11.alpha.gz irreducible triangulations, non-orientable, genus 5, n=9-11 genus-6.10-11.alpha.gz irreducible triangulations, non-orientable, genus 6, n=10-11 genus-7.10-11.alpha.gz irreducible triangulations, non-orientable, genus 7, n=10-11 genus-8.11.alpha.gz irreducible triangulations, non-orientable, genus 8, n=11 genus-9.11.alpha.gz irreducible triangulations, non-orientable, genus 9, n=11 -------------- More information about surftri and the latest version of surftri can be found at: http://hep.physics.indiana.edu/~tsulanke/graphs/surftri/ From this same URL can be obtained the irreducible triangulations for a few small surfaces and small irreducible triangulations for a few other not quite so small surfaces. ============================= A few examples are given to demonstrate some features and as simple tests for a new installation. List triangulation of sphere with 5 vertices: $ surftri -v -a 5 0 surftri -v -a 5 0 5 bcd,adec,abed,aceb,bdc 1 irreducible triangulations read and used with nv 4 1 triangulations written to stdout; cpu=0.00 sec Count triangulation of sphere with 16 vertices: $ surftri -v -u 16 0 surftri -v -u 16 0 1 irreducible triangulations read and used with nv 4 17490241 triangulations generated; cpu=12.64 sec Count splitting cases for triangulations of sphere: $ surftri_s -v -u 16 0 surftri_s -v -u 16 0 1 irreducible triangulations read and used with nv 4 49566 splitting cases at level=13; cpu=0.07 sec Count triangulation of torus with 13 vertices: $ surftri -v -u 13 1 surftri -v -u 13 1 1 irreducible triangulations read and used with nv 7 4 irreducible triangulations read and used with nv 8 15 irreducible triangulations read and used with nv 9 1 irreducible triangulations read and used with nv 10 8778329 triangulations generated; cpu=8.15 sec Count triangulations of projective plane with 14 vertices: $ surftri -v -u -n 14 1 surftri -v -u -n 14 1 1 irreducible triangulations read and used with nv 6 1 irreducible triangulations read and used with nv 7 10606795 triangulations generated; cpu=8.12 sec Count triangulations of Klein bottle with 13 vertices: $ surftri -v -u -n 13 2 surftri -v -u -n 13 2 6 irreducible triangulations read and used with nv 8 19 irreducible triangulations read and used with nv 9 2 irreducible triangulations read and used with nv 10 2 irreducible triangulations read and used with nv 11 21535942 triangulations generated; cpu=20.46 sec Count maps on projective plane with 3 vertices: $ surftri -v -u -pc1 -n 3 1 surftri -v -u -pc1 -n 3 1 With 3 edges and 1 faces: 1 By embedding type: 1 c1; 0 c2; 0 c3 1 irreducible maps read and used with nv 3 1 maps generated; cpu=0.00 sec Count maps on projective plane with 4 vertices: $ surftri -v -u -pc1 -n 4 1 surftri -v -u -pc1 -n 4 1 With 4 edges and 1 faces: 2 With 5 edges and 2 faces: 2 With 6 edges and 3 faces: 2 By embedding type: 5 c1; 1 c2; 0 c3 1 irreducible maps read and used with nv 3 1 irreducible maps read and used with nv 4 6 maps generated; cpu=0.00 sec Count maps on projective plane with 5 vertices: $ surftri -v -u -pc1 -n 5 1 surftri -v -u -pc1 -n 5 1 With 5 edges and 1 faces: 7 With 6 edges and 2 faces: 16 With 7 edges and 3 faces: 21 With 8 edges and 4 faces: 14 With 9 edges and 5 faces: 5 With 10 edges and 6 faces: 2 By embedding type: 56 c1; 9 c2; 0 c3 1 irreducible maps read and used with nv 3 1 irreducible maps read and used with nv 4 2 irreducible maps read and used with nv 5 65 maps generated; cpu=0.00 sec Count maps on projective plane with 5 vertices (closed 2-cell embedding): $ surftri -v -u -pc2 -n 5 1 surftri -v -u -pc2 -n 5 1 With 7 edges and 3 faces: 1 With 8 edges and 4 faces: 4 With 9 edges and 5 faces: 2 With 10 edges and 6 faces: 2 By embedding type: 9 c2; 0 c3 1 irreducible maps read and used with nv 3 1 irreducible maps read and used with nv 4 2 irreducible maps read and used with nv 5 9 maps generated; cpu=0.00 sec Count maps on projective plane with 5 vertices (regular embedding: the intersection of the two faces is either empty, a vertex, an edge, or a face): (there are none) $ surftri -v -u -pc3 -n 5 1 surftri -v -u -pc3 -n 5 1 0 maps generated; cpu=0.00 sec Count maps on projective plane with 6 vertices (regular embedding: the intersection of the two faces is either empty, a vertex, an edge, or a face): $ surftri -v -u -pc3 -n 6 1 surftri -v -u -pc3 -n 6 1 With 15 edges and 10 faces: 1 1 irreducible maps read and used with nv 6 1 maps generated; cpu=0.00 sec For non-orientable surface "-A" might be needed: List maps of projective plane with 6 vertices with and without signatures: $ surftri -A -pc1 -n 6 1 > tmp.with surftri -A -pc1 -n 6 1 1128 maps written to stdout; cpu=0.00 sec $ surftri -a -pc1 -n 6 1 > tmp.wout surftri -a -pc1 -n 6 1 1128 maps written to stdout; cpu=0.00 sec $ grep -i "6 bcd,ade,afd,acfb,bf,ced" tmp.wout tmp.with tmp.wout:6 bcd,ade,afd,acfb,bf,ced tmp.wout:6 bcd,ade,afd,acfb,bf,ced tmp.with:6 bcd,ade,afd,acFb,bf,ceD tmp.with:6 bcd,ade,afd,acfb,bF,cEd All maps on torus with 8 vertices: $ surftri -v -u -pc1 8 1 surftri -v -u -pc1 8 1 With 9 edges and 1 faces: 1062 With 10 edges and 2 faces: 15803 With 11 edges and 3 faces: 97039 With 12 edges and 4 faces: 336130 With 13 edges and 5 faces: 754026 With 14 edges and 6 faces: 1177789 With 15 edges and 7 faces: 1336173 With 16 edges and 8 faces: 1127884 With 17 edges and 9 faces: 717048 With 18 edges and 10 faces: 344159 With 19 edges and 11 faces: 123739 With 20 edges and 12 faces: 32833 With 21 edges and 13 faces: 6229 With 22 edges and 14 faces: 826 With 23 edges and 15 faces: 70 With 24 edges and 16 faces: 7 By embedding type: 5056799 c1; 1013985 c2; 33 c3 2 irreducible maps read and used with nv 4 7 irreducible maps read and used with nv 5 11 irreducible maps read and used with nv 6 16 irreducible maps read and used with nv 7 15 irreducible maps read and used with nv 8 6070817 maps generated; cpu=5.63 sec All maps on Klein bottle with 8 vertices: $ surftri -v -u -pc1 -n 8 2 surftri -v -u -pc1 -n 8 2 With 9 edges and 1 faces: 3289 With 10 edges and 2 faces: 50695 With 11 edges and 3 faces: 314636 With 12 edges and 4 faces: 1089843 With 13 edges and 5 faces: 2422616 With 14 edges and 6 faces: 3724740 With 15 edges and 7 faces: 4135032 With 16 edges and 8 faces: 3398628 With 17 edges and 9 faces: 2093827 With 18 edges and 10 faces: 968938 With 19 edges and 11 faces: 334141 With 20 edges and 12 faces: 84198 With 21 edges and 13 faces: 14978 With 22 edges and 14 faces: 1775 With 23 edges and 15 faces: 129 With 24 edges and 16 faces: 6 By embedding type: 16071759 c1; 2565678 c2; 34 c3 3 irreducible maps read and used with nv 4 14 irreducible maps read and used with nv 5 28 irreducible maps read and used with nv 6 43 irreducible maps read and used with nv 7 44 irreducible maps read and used with nv 8 18637471 maps generated; cpu=17.57 sec All quadragulations on the projective plane with 15 vertices: $ surftri -v -u -q -n 15 1 surftri -v -u -q -n 15 1 1 irreducible quadrangulations read and used with nv 4 1 irreducible quadrangulations read and used with nv 7 9213613 quadrangulations generated; cpu=12.59 sec All quadragulations on the projective plane with 20 vertices with minimum degree 3: $ surftri -v -u -q -m3 -n 20 1 surftri -v -u -q -m3 -n 20 1 1 irreducible quadrangulations read and used with nv 4 1 irreducible quadrangulations read and used with nv 6 1 irreducible quadrangulations read and used with nv 7 1 irreducible quadrangulations read and used with nv 8 1 irreducible quadrangulations read and used with nv 10 1 irreducible quadrangulations read and used with nv 12 1 irreducible quadrangulations read and used with nv 14 1 irreducible quadrangulations read and used with nv 16 1 irreducible quadrangulations read and used with nv 18 1 irreducible quadrangulations read and used with nv 20 3613389 quadrangulations generated; cpu=69.65 sec