Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.3

Space-Efficient Generation of Nonisomorphic Maps and Hypermaps


Timothy R. Walsh
Department of Computer Science
UQAM
Box 8888, Station A
Montréal, Quebec, H3C 3P8
Canada

Abstract:

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).


Full version:  pdf,    dvi,    ps,    latex    


(Concerned with sequences A000257 A003319 A006385 A006387 A057005 A090371 A118093 A118094 A214814 A214815 A214816 A214817 A214818 A214819 A214820 A214821 A214822 A214823 A215017 A215018.)


Received October 3 2014; revised versions received October 6 2014; October 29 2014; February 19 2015; February 23 2015. Published in Journal of Integer Sequences, May 12 2015.


Return to Journal of Integer Sequences home page