Efficient enumeration of sensed planar maps (Q1779505)

This paper is concerned with efficient counting (here often called ``enumeration'') of various classes of planar and toroidal maps. A sensed planar map is an equivalence class of planar maps under orientation-preserving homeomorphisms. The author observes that \textit{N. C. Wormald} [Can. J. Math. 33, 1--11 (1981; Zbl 0408.57006) and Discrete Math. 36, 205--225 (1981; Zbl 0467.05034)] ``enumerated sensed and unsensed planar maps by number of edges and number of vertices,'' observing that, ``using his method it takes \(\text{O}(M^6)\) arithmetic operations to count either sensed or unsensed maps by number of vertices and edges up to \(M\) edges and all relevant numbers of vertices, and \(\text{O}(M^4)\) operations to count them by number of edges alone.'' Expanding on work of \textit{V. A. Liskovets} [Sel. Math. Sov. 4, 303--323 (1985; Zbl 0578.05033), translation of Vopr. Teor. Grupp Gomologicheskoj Algebry 1981, 103--115 (1981; Zbl 0479.05036) and Geom. Metody Zadachakh Algebry Anal. 1981, 106--117 (1981; Zbl 0495.05034)] and \textit{V. A. Liskovets} with the present author [Can. J. Math. 35, 417--435 (1983; Zbl 0519.05041)] (from the author's introduction) ``we obtain closed-form formulas to count 1- and 2-connected sensed planar maps by number of edges and vertices, and an interactive algorithm to count 3-connected sensed planar maps by number(s) of edges and vertices. Substituting into the formulas, it takes \(\text{O}(M^2)\) arithmetic operations on arbitrarily long integers to count sensed 1- and 2-connected planar maps with up to \(M\) edges and all relevant number(s) of vertices once the corresponding numbers of rooted 1- and 2-connected planar maps have been calculated, and \(\text{O}(M^5)\) operations to count sensed 3-connected maps.''