Generating maps on oriented surfaces using the homomorphism principle
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913485520109568 |
|---|---|
| author | Brinkmann, Gunnar |
| author_facet | Brinkmann, Gunnar |
| contents | In this article we describe an algorithm that can be applied for the generation of various classes of maps on orientable surfaces. It uses existing generators for abstract graphs and combines them with an efficient embedding and isomorphism rejection routine. The generation rate of the program implementing the algorithm depends a lot on the class of maps to be generated, but is quite high -- more than a million non-isomorphic structures per second -- for some relevant classes of maps. The same program can also be used to embed specific graphs on a given orientable surface in all non-isomorphic ways. It can serve as a tool in many applications where classes of maps on orientable surfaces are studied and provides a very general independent test for specialized generation programs. We also give enumeration results for 3-regular, 4-regular, and 5-regular maps as well as all maps and some maps with just one face. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_16512 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Generating maps on oriented surfaces using the homomorphism principle Brinkmann, Gunnar Combinatorics 05C10, 05-04, 05C85 In this article we describe an algorithm that can be applied for the generation of various classes of maps on orientable surfaces. It uses existing generators for abstract graphs and combines them with an efficient embedding and isomorphism rejection routine. The generation rate of the program implementing the algorithm depends a lot on the class of maps to be generated, but is quite high -- more than a million non-isomorphic structures per second -- for some relevant classes of maps. The same program can also be used to embed specific graphs on a given orientable surface in all non-isomorphic ways. It can serve as a tool in many applications where classes of maps on orientable surfaces are studied and provides a very general independent test for specialized generation programs. We also give enumeration results for 3-regular, 4-regular, and 5-regular maps as well as all maps and some maps with just one face. |
| title | Generating maps on oriented surfaces using the homomorphism principle |
| topic | Combinatorics 05C10, 05-04, 05C85 |
| url | https://arxiv.org/abs/2408.16512 |