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