Efficient enumeration of sensed planar maps
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.
- A Census of Planar Maps
- A reductive technique for enumerating non-isomorphic planar maps
- Counting non-isomorphic three-connected planar maps
- Counting rooted maps by genus. II
- Counting rooted maps on an orientable surface of any genus by a function of the numbers of vertices and faces
- Counting unlabelled three-connected and homeomorphically irreducible two- connected graphs
- Counting unrooted loopless planar maps
- Counting unrooted planar maps
- D-finite power series
- Enumeration of Eulerian and unicursal planar maps
- Enumeration of non-separable graphs
- Enumeration of unrooted maps of a given genus
- scientific article; zbMATH DE number 3880743 (Why is no real title available?)
- scientific article; zbMATH DE number 3821780 (Why is no real title available?)
- scientific article; zbMATH DE number 3924814 (Why is no real title available?)
- scientific article; zbMATH DE number 4055646 (Why is no real title available?)
- scientific article; zbMATH DE number 3478130 (Why is no real title available?)
- scientific article; zbMATH DE number 3419161 (Why is no real title available?)
- Hypermaps versus bipartite maps
- Inversion of cycle index sum relations for 2- and 3-connected graphs
- On the enumeration of planar maps
- On the Enumeration of Rooted Non-Separable Planar Maps
- On the Tumber of Planar Maps
- Relations fonctionnelles et dénombrement des cartes pointées sur le tore. (Functional relations and the enumeration of rooted genus one maps)
- The enumeration of c-nets via quadrangulations
- The Enumeration of Non-Isomorphic 2-Connected Planar Maps
- Theory of Maps on Orientable Surfaces
- A reductive technique for enumerating non-isomorphic planar maps
- Counting unrooted maps using tree-decomposition
- Counting edge-transitive, one-ended, three-connected planar maps with a given growth rate.
- scientific article; zbMATH DE number 4055646 (Why is no real title available?)
- Counting maps on doughnuts
- Enumeration of unrooted orientable maps of arbitrary genus by number of edges and vertices
- Counting unrooted maps on the plane
- Enumeration of maps regardless of genus: geometric approach
This page was built for publication: Efficient enumeration of sensed planar maps
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1779505)
