Space-efficient generation of nonisomorphic maps and hypermaps. (English) Zbl 1327.05158

Walsh, Timothy R.

J. Integer Seq. 18, No. 4, Article 15.4.3, 35 p. (2015).

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

MSC:

05C30	Enumeration in graph theory
05C10	Planar graphs; geometric and topological aspects of graph theory
05C65	Hypergraphs
05C85	Graph algorithms (graph-theoretic aspects)

Keywords:

map; hypermap; exhaustive generation

Software:

OEIS