Enumeration of nonisomorphic planar maps

The maps that we count are the planar maps considered in [4]. Two maps are called isomorphic if there is a homeomorphism of the sphere which preserves its orientation, considered as fixed, and takes one map into the other. We develop a general enumerative scheme for nonisomorphic maps (up to orientation-preserving homeomorphisms). Under some conditions it reduces the enumeration of nonisomorphic maps of a given type to that of rooted maps (as defined in [4]) of the same and several related kinds. This partially fills a rather surprising gap between the well-developed techniques for counting rooted maps (cf. [4,5]) and the very few results so far obtained for counting nonisomorphic ones. This note contains a sketch of the method, which is somewhat similar to that developed in [3], and one of the main results. The scheme is based on Burnside’s lemma and on two well-known properties-one topological and the other combinatorial-of a nontrivial orientation-preserving map automorphism [ 1,2,6]: it may be uniquely represented as a rotation of the sphere around an axis (up to topological equivalence-see [ 11) and as a regular permutation acting on the set of halfedges, called “bits” [6 ] or “darts” [2]. If necessary we label the half-edges and consider labeled maps thus obtained. As a principal tool of reduction we use the topologicaI notion of a quotient map of a map with respect to an orientation-preserving automorphism (see [2] for the general definition and properties of quotient maps). It is worth noting that a quotient map is a usual map or a map having 1 or 2 special vertices (free points [2]) of degree 1 which are distinguished as