photo

Vincent Delecroix


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

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)

For each isomorphism class of ribbon graph, the file provides

Related softwares


Creative Commons License
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.