Efficient enumeration of sensed planar maps
type: Item
instance of: scholarly article
title: Efficient enumeration of sensed planar maps
zbMATH Open document ID: 1063.05070
published in: Discrete Mathematics
publication date: 2005-06-01T00:00:00Z
review text: 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.''
reviewed by: William G. Brown
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 2173248
zbMATH Keywords: unrooted planar maps
zbMATH Keywords: exact enumeration
zbMATH Keywords: efficient algorithms
zbMATH Keywords: quotient maps
author: Timothy R. S. Walsh
MaRDI profile type: Publication
full work available at URL: j.disc.2004.08.036
OpenAlex ID: W1984327345
cites work: Relations fonctionnelles et dénombrement des cartes pointées sur le tore. (Functional relations and the enumeration of rooted genus one maps)
cites work: Counting rooted maps on an orientable surface of any genus by a function of the numbers of vertices and faces
cites work: Q4061717
cites work: On the Enumeration of Rooted Non-Separable Planar Maps
cites work: Q5682013
cites work: Theory of Maps on Orientable Surfaces
cites work: D-finite power series
cites work: Q3669450
cites work: Q3699715
cites work: A reductive technique for enumerating non-isomorphic planar maps
cites work: The Enumeration of Non-Isomorphic 2-Connected Planar Maps
cites work: Q3791172
cites work: Enumeration of Eulerian and unicursal planar maps
cites work: Counting unrooted loopless planar maps
cites work: Enumeration of unrooted maps of a given genus
cites work: The enumeration of c-nets via quadrangulations
cites work: Enumeration of non-separable graphs
cites work: Inversion of cycle index sum relations for 2- and 3-connected graphs
cites work: A Census of Planar Maps
cites work: On the enumeration of planar maps
cites work: Hypermaps versus bipartite maps
cites work: Counting unlabelled three-connected and homeomorphically irreducible two- connected graphs
cites work: Counting non-isomorphic three-connected planar maps
cites work: Q3346352
cites work: Counting rooted maps by genus. II
cites work: On the Tumber of Planar Maps
cites work: Counting unrooted planar maps
DOI: 10.1016/J.DISC.2004.08.036
description: scientific article; zbMATH DE number 2173248