Efficient enumeration of sensed planar maps Original Research Article

We use Liskovets’ quotient maps and Robinsonʹs cycle index sums to count 1-, 2- and 3-connected planar maps by number of vertices and edges up to sense-preserving homeomorphism of the embedding sphere. Although Wormald has already counted these maps up to all homeomorphism, sense-reversing as well as sense-preserving, our methods are computationally more efficient for counting these maps up to orientation-preserving homeomorphism and yield closed-form enumeration formulas in the case of 1- and 2-connected maps. Our formula for 1-connected planar maps uses the number of rooted planar maps with image vertices and image faces; we evaluate these numbers using a method that is more efficient than substituting into Tutteʹs parametric equations, and we also count rooted toroidal maps by number of vertices and faces more efficiently than by substituting into Arquès’ explicit formula.