# zbMATH — the first resource for mathematics

Efficient enumeration of sensed planar maps. (English) Zbl 1063.05070
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 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 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 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.”

##### MSC:
 05C30 Enumeration in graph theory 05C10 Planar graphs; geometric and topological aspects of graph theory 68R10 Graph theory (including graph drawing) in computer science
Full Text: