×

zbMATH — the first resource for mathematics

A reductive technique for enumerating non-isomorphic planar maps. (English) Zbl 0857.05044
In [A census of non-isomorphic planar maps, Colloq. Math. Soc. János Bolyai 25, 479-494 (1981; Zbl 0519.05040)] the author reduced the enumeration of planar maps up to orientation-preserving homeomorphisms of the embedding sphere to the enumeration of rooted planar maps done by W. T. Tutte [A census of planar maps, Can. J. Math. 15, 249-271 (1963; Zbl 0115.17305)] and found a closed-form formula for the number of such maps with \(n\) edges. N. C. Wormald [Counting unrooted planar maps, Discrete Math. 36, 205-225 (1981; Zbl 0467.05034)] and [On the number of planar maps, Can. J. Math. 33, 1-11 (1981; Zbl 0408.57006)] developed an algorithmic method for counting planar maps up to arbitrary homeomorphisms, including orientation-reversing ones. This method yielded no closed-form formula even when restricted to orientation-preserving homeomorphisms.
In the article under review, the reductive method of the author [loc. cit.] is generalized to arbitrary homeomorphims by classifying them into five types; the enumeration of planar maps up to arbitrary homeomorphisms is thus reduced to counting rooted planar maps, rooted projective maps and rooted circular maps. A recursive formula for counting rooted projective maps was given in [E. A. Bender, E. R. Canfield and R. W. Robinson, The enumeration of maps on the torus and the projective plane, Can. Math. Bull. 31, No. 3, 251-271 (1988; Zbl 0617.05036)]. In the present paper, rooted circular maps are reduced to certain generalized rooted quadrangular dissections of the disc, and in a final remark a method of enumerating these objects is suggested.

MSC:
05C30 Enumeration in graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bender, E.A.; Canfield, E.R.; Robinson, R.W., The enumeration of maps on torus and projective plane, Canad. math. bull., 31, 257-271, (1988) · Zbl 0617.05036
[2] Brown, W.G., Enumeration of quadrangular dissections of the disk, Canad. J. math., 17, 302-317, (1965) · Zbl 0138.19104
[3] Brown, W.G., On the enumeration of non-planar maps, Mem. amer. math. soc., 65, 1-42, (1966) · Zbl 0149.21201
[4] Bryant, R.P.; Singerman, D., Foundations of the theory of maps on surfaces with boundary, Quart. J. math. Oxford, 36, 141, 17-41, (1985) · Zbl 0565.05026
[5] Cooper, E.D., Combinatorial map theory, J. combin. theory B, 18, 73-83, (1975) · Zbl 0278.05030
[6] Coxeter, H.S.M., Introduction to geometry, (1961), Wiley New York · Zbl 0095.34502
[7] Eilenberg, S., Sur LES transformations périodiques de la surfaces de la sphère, Fundam. math., 22, 1, 28-42, (1934) · JFM 60.1228.02
[8] Goulden, I.P.; Jackson, D.M., Combinatorial enumeration, (1983), Wiley New York · Zbl 0519.05001
[9] Jones, G.A.; Thornton, J.S., Operations on maps and outer automorphisms, J. combin. theory B, 35, 2, 93-103, (1983) · Zbl 0509.57001
[10] Liskovets, V.A.; Liskovets, V.A., A census of non-isomorphic planar maps, (), 479-494 · Zbl 0519.05040
[11] Liskovets, V.A., Enumeration of nonisomorphic planar maps, Selecta math. sov., 4, 304-323, (1985) · Zbl 0578.05033
[12] Liskovets, V.A.; Walsh, T.R.S., Ten steps to counting planar graphs, (), 269-277 · Zbl 0519.05041
[13] Mani, P., Automorphismen von polyedrischen graphen, Math. ann., 192, 279-303, (1971) · Zbl 0206.51402
[14] Massey, W.S., Algebraic topology, () · Zbl 0055.16601
[15] Scott, P., The geometries of 3-manifolds, Bull. London math. soc., 15, 401-487, (1983) · Zbl 0561.57001
[16] Singerman, D., Maps on surfaces with boundary, Ars combin., 16 A, 227-238, (1983) · Zbl 0555.05033
[17] Tutte, W.T., A census of planar maps, Canad. J. math., 15, 249-271, (1963) · Zbl 0115.17305
[18] Walsh, T.R.S., Hypermaps versus bipartite maps, J. combin. theory B, 18, 155-163, (1975) · Zbl 0302.05101
[19] Wormald, N.C., Counting unrooted planar maps, Discrete math., 36, 205-225, (1981) · Zbl 0467.05034
[20] Wormald, N.C., On the number of planar maps, Canad. J. math., 33, 1-11, (1981) · Zbl 0408.57006
[21] Zieschang, H.; Vogt, E.; Coldeway, H.-D., Surfaces and planar discontinuous groups, ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.