Enumerating ribbon graphs or combinatorial maps
I implemented in the surface_dynamics library
a canonical generation for ribbon graphs (equivalently combinatorial
maps). That is to say an algorithm to generate the list of ribbon
graphs up to isomorphism. The main class is FatGraphs_g_nf_nv()
that
can be used as follows to generate the 33 quadrangulations of the sphere
made of 4 quadrilaterals (for technical reasons we generate their dual)
>>> from surface_dynamics.topology.fat_graph_exhaustive_generation import FatGraphs_g_nf_nv
>>> F = FatGraphs_g_nf_nv(0, nv=4, nf=6, vertex_min_degree=4)
>>> F.cardinality_and_weighted_cardinality()
(33, 189/8)
>>> F.list()
[FatGraph('(0,9,8,11)(1,14,3,2)(4,15,12,5)(6,13,10,7)',
'(0,1)(2,3)(4,5)(6,7)(8,9)(10,11)(12,13)(14,15)',
'(0,2,14,4,12,6,10,8)(1,11,13,15)(3)(5)(7)(9)'),
FatGraph('(0,9,8,11)(1,10,13,2)(3,12,15,4)(5,14,7,6)',
'(0,1)(2,3)(4,5)(6,7)(8,9)(10,11)(12,13)(14,15)',
'(0,2,4,6,14,12,10,8)(1,11)(3,13)(5,15)(7)(9)'),
...
FatGraph('(0,6,13,1)(2,4,11,3)(5,14,12,8)(7,15,10,9)',
'(0,1)(2,3)(4,5)(6,7)(8,9)(10,11)(12,13)(14,15)',
'(0,13,14,7)(1)(2,11,15,5)(3)(4,8,10)(6,9,12)'),
FatGraph('(0,6,13,1)(2,4,11,3)(5,10,9,15)(7,12,8,14)',
'(0,1)(2,3)(4,5)(6,7)(8,9)(10,11)(12,13)(14,15)',
'(0,13,7)(1)(2,11,5)(3)(4,15,8,10)(6,14,9,12)')]
More generally, restrictions can be put on
- genus (fixed genus
g
, min genusg_min
, max genusg_max
) - number of faces (
nf
, or min numbernf_min
, or max numbernf_max
) - number of vertices (
nv
, or min numbernv_min
, or max numbernv_max
) - vertex degrees (lower bound
vertex_min_degree
)
In the future, I will likely implement more restrictions such as
vertex_max_degree
and restrictions on face degrees.
Trivalent ribbon graphs
The trivalent ribbon graphs were considered in the work of Kontsevich on Witten's conjecture (1992). We provide below the lists of trivalent ribbon graphs sorted by genus and number of boundary components (aka faces)
- g=0, n=3: 2 trivalent ribbon graphs
- g=0, n=4: 6 trivalent ribbon graphs
- g=0, n=5: 26 trivalent ribbon graphs
- g=0, n=6: 191 trivalent ribbon graphs
- g=1, n=1: 1 trivalent ribbon graph
- g=1, n=2: 5 trivalent ribbon graphs
- g=1, n=3: 46 trivalent ribbon graphs
- g=2, n=1: 9 trivalent ribbon graphs
- g=2, n=2: 368 trivalent ribbon graphs
- g=3, n=1: 1726 trivalent ribbon graphs
For each isomorphism class of ribbon graph, the file provides
- a representative which is a triple of permutation representing the associated 3-constellation (see for example the book of Lando and Zvonkine "Graphs on surfaces").
- the automorphism group (the names are taken from the GAP software)
- the edge-face adjacency matrix
Related softwares
- plantri by G. Brinkmann and B. McKay implements a very well optimized version for genus 0.
- surftri by T. Sulanke enumerate triangulations

Cet article est publié sous la licence Creative Commons Attribution-NonCommercial 4.0 International License.
This article is published under the Creative Commons Attribution-NonCommercial 4.0 International License.