Generating Maps on Oriented Surfaces Using the Homomorphism Principle.
Saved in:
| Title: | Generating Maps on Oriented Surfaces Using the Homomorphism Principle. |
|---|---|
| Authors: | Brinkmann, Gunnar1 (AUTHOR) Gunnar.Brinkmann@UGent.be |
| Source: | Discrete & Computational Geometry. Jun2026, Vol. 75 Issue 4, p1294-1304. 11p. |
| Subjects: | Algorithms, Geometric surfaces, Regular graphs, Mathematical mappings, Mathematics, Graph theory |
| Abstract: | 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. Enumeration results for 3-regular, 4-regular, and 5-regular maps as well as for all maps and some maps with just one face can be found as supplementary material. [ABSTRACT FROM AUTHOR] |
| Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | 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. Enumeration results for 3-regular, 4-regular, and 5-regular maps as well as for all maps and some maps with just one face can be found as supplementary material. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 01795376 |
| DOI: | 10.1007/s00454-025-00734-5 |
