Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-24T18:32:11.096Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Tumber of Planar Maps

Published online by Cambridge University Press:  20 November 2018

Nicholas C. Wormald
Nicholas C. Wormald*
Affiliation:
University of Waterloo, Waterloo, Ontario
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In a survey of methods in enumerative map theory [14], W. T. Tutte pointed out that little has been done towards enumerating unrooted maps other than plane trees. A notable exception is to be found in the work of Brown, who took the initial step in this direction by enumerating non-separable maps up to sense-preserving homeomorphisms of the plane [2]. He then took a further step, allowing sense-reversing homeomorphisms, by counting triangulations and quad-rangulations of the disc [3, 4]. In all these problems, however, there is a fixed outer region of the plane. This can be considered as a certain type of rooting of a planar map, which is normally regarded as lying on the sphere or closed plane. It is our object here to find an expression for the number of unrooted planar maps in a given set, in terms of the numbers of maps in that set which have been rooted in a special way.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 33 , Issue 1 , 01 February 1981 , pp. 1 - 11
Copyright
Copyright © Canadian Mathematical Society 1981

References

1. Babai, L. and Imrich, W., On groups of polyhedral graphs, Discrete Math. 5 (1973), 101–103.Google Scholar
2. Brown, W. G., Enumeration of non-separable planar maps, Can. J. Math. 15 (1963), 526–545.Google Scholar
3. Brown, W. G., Enumeration of triangulations of the disk, Proc. London. Math. Soc. 14 (1964), 746–768.Google Scholar
4. Brown, W. G., Enumeration of quadrangular dissections of the disk, Can. J. Math. 17 (1965), 302–317.Google Scholar
5. Eilenberg, S., Sur les transformations périodiques de la surface de sphere, Fund. Math. 22 (1934), 28–41.Google Scholar
6. Federico, P. J., The number of polyhedra, Philips Research Reports 30 (1975), 220–231.Google Scholar
7. Harary, F., Unsolved problems in the enumeration of graphs, Publications Math. Inst. Hungar. Acad. Sci. 5 (1960), 63–95.Google Scholar
8. Harary, F., Graph theory (Addison-Wesley, Reading, Mass., 1969).Google Scholar
9. Harary, F. and Palmer, E. M., Graphical enumeration (Academic Press, New York, 1973).Google Scholar
10. Kerékjârto, R., Uber die periodischen Transformationen der Kreisscheibe und der Kugelfidche, Math. Ann. 80 (1921), 36–38.Google Scholar
11. Polya, G., Kombinatorische Anzahlbestimmungen filr Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937), 145–254.Google Scholar
12. Tutte, W. T., A census of planar maps, Can. J. Math. 15 (1963), 249–271.Google Scholar
13. Tutte, W. T., What is a map? in New directions in the theory of graphs (Academic Press, New York, 1973), 309–325.Google Scholar
14. Tutte, W. T., The enumerative theory of planar maps in A survey of combinatorial theory (North-Holland Publishing Company, Amsterdam, 1973), 437–448.Google Scholar
15. Tutte, W. T., On the enumeration of convex polyhedra, Can. J. Math, (to appear).Google Scholar