Space-Efficient Generation of Nonisomorphic Maps and Hypermaps

摘要

In 1979, while working as a senior researcher in the Computing Centre of the USSR Academy of Sciences in Moscow, I used Lehman's code for rooted maps of any orientable genus to generate these maps. By imposing an order on the code-words and keeping only those that are maximal over all the words that code the same map with each semi-edge chosen as the root, I generated these maps up to orientation-preserving isomorphism, and by comparing each of them with the code-words for the map obtained by reversing the orientation, I generated these maps up to a generalized isomorphism that could be orientation-preserving or orientation-reversing. The limitations on the speed of the computer I was using and the time allowed for a run restricted me to generating these maps with up to only six edges. In 2011, by optimizing the algorithms and using a more powerful computer and more CPU time I was able to generate these maps with up to eleven edges. An average-case time-complexity analysis of the generation algorithms is included in this article. And now, by using a genus-preserving bijection between hypermaps and bicoloured bipartite maps that I discovered in 1975 and the condition on the word coding a rooted map for the map to be bipartite, I generated hypermaps, both rooted and unrooted, with up to twelve darts (edge-vertex incidence pairs).