A reductive technique for enumerating non-isomorphic planar maps
type: Item
instance of: scholarly article
title: A reductive technique for enumerating non-isomorphic planar maps
zbMATH Open document ID: 0857.05044
DOI: 10.1016/0012-365X(94)00347-L
author: Valery A. Liskovets
published in: Discrete Mathematics
publication date: 1997-02-26T00:00:00Z
review text: 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 \textit{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. \textit{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 [\textit{E. A. Bender}, \textit{E. R. Canfield} and \textit{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.
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 932556
zbMATH Keywords: rotation
zbMATH Keywords: reflection
zbMATH Keywords: enumeration
zbMATH Keywords: planar maps
zbMATH Keywords: homeomorphisms
zbMATH Keywords: quadrangular dissections
reviewed by: Timothy R. S. Walsh
MaRDI profile type: Publication
cites work: The Enumeration of Maps on the Torus and the Projective Plane
cites work: Enumeration of Quadrangular Dissections of the Disk
cites work: On the enumeration of non-planar maps
cites work: FOUNDATIONS OF THE THEORY OF MAPS ON SURFACES WITH BOUNDARY
cites work: Combinatorial map theory
cites work: Q3273607
cites work: Q3669422
cites work: Operations on maps, and outer automorphisms
cites work: Q3669450
cites work: Q3699715
cites work: The Enumeration of Non-Isomorphic 2-Connected Planar Maps
cites work: Automorphismen von polyedrischen Graphen
cites work: Some new algebraic methods in topology
cites work: The Geometries of 3-Manifolds
cites work: Q3218150
cites work: A Census of Planar Maps
cites work: Hypermaps versus bipartite maps
cites work: Counting unrooted planar maps
cites work: On the Tumber of Planar Maps
cites work: Surfaces and planar discontinuous groups. Revised and expanded transl. from the German by J. Stillwell
description: scientific article; zbMATH DE number 932556