×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arquès, D., Relations fonctionelles et dénombrement des Cartes pointées sur le tore, J. combin. theory ser. B, 43, 253-274, (1987) · Zbl 0628.05040
[2] Arquès, D.; Giorgetti, A., Énumération des Cartes pointeés sur une surface orientable de genre quelconque en function des nombres de sommets et de faces, J. combin. theory ser. B, 77, 1-24, (1999) · Zbl 1029.05073
[3] Babai, L.; Imrich, W.; Lovasz, L., Finite homeomorphism groups of the 2-sphere, Colloq. math. soc. janos bolyai (topics in topology), 8, 61-75, (1972)
[4] Brown, W.G.; Tutte, W.T., On the enumeration of rooted non-separable planar maps, Canad. J. math., 16, 572-577, (1964) · Zbl 0119.38804
[5] Cauchy, A., Mémoire sur diverses propriétés remarquables des substitutions régulières ou irrégulières et des systèmes de substitutions conjuguées, C. R. acad. sci. Paris, 21, 835, (1845)
[6] J. Edmonds, A combinatorial representation for oriented polyhedral surfaces, M.A. Thesis, University of Maryland, College Park, 1960 (See also Notices Amer. Math. Soc. 7 (1960) 646).
[7] Harary, F.; Palmer, E.M., Graphical enumeration, (1973), Academic Press New York and London · Zbl 0266.05108
[8] Jones, G.A.; Singerman, D., Theory of maps on orientable surfaces, Proc. London math. soc. (3), 37, 2, 273-307, (1978) · Zbl 0391.05024
[9] Kuhn, H.W., On imprimitive substitution groups, Amer. J. math., 26, 45-102, (1904) · JFM 35.0172.01
[10] Lipshitz, L., D-finite power series, J. algebra, 122, 353-373, (1989) · Zbl 0695.12018
[11] Liskovets, V.A., A census of non-isomorphic planar maps, Colloq. math. soc. janos bolyai (algebraic methods in graph theory, 1978), 25, 479-494, (1981) · Zbl 0519.05040
[12] Liskovets, V.A., Enumeration of nonisomorphic planar maps, Selecta math. soviet., 4, 4, 303-323, (1985) · Zbl 0578.05033
[13] Liskovets, V.A., A reductive technique for enumerating non-isomorphic planar maps, Discrete math., 156, 197-217, (1996) · Zbl 0857.05044
[14] Liskovets, V.A.; Walsh, T.R., The enumeration of non-isomorphic 2-connected planar maps, Canad. J. math., XXXV, 3, 417-435, (1983) · Zbl 0519.05041
[15] V.A. Liskovets, T.R. Walsh, Ten steps to counting planar graphs, Proceedings of the 18th Southeastern Conference on Computing, Graph Theory and Combinatorics, vol. 60, Florida Atlantic University, Congressus Numerantium, 1987, pp. 269-278. · Zbl 0647.05030
[16] Liskovets, V.A.; Walsh, T.R., Counting unrooted Eulerian and unicursal planar maps, Discrete math., 282, 209-221, (2004) · Zbl 1051.05049
[17] Liskovets, V.A.; Walsh, T.R., Counting unrooted loopless planar maps, European J. combin., 26, 651-663, (2005) · Zbl 1070.05050
[18] A. Mednykh, R. Nedela, Enumeration of unrooted maps with given genus, submitted for publication. · Zbl 1102.05033
[19] Mullin, R.C.; Schelleberg, P.J., The enumeration of c-nets via quadrangulations, J. combin. theory, 4, 259-276, (1968) · Zbl 0183.52403
[20] Poincaré, H., Sur la généralisation d’un théorème d’euler relatif aux polyèdres, C. R. hebd. acad. sci., 117, 144-145, (1893) · JFM 25.1031.03
[21] Robinson, R.W., Enumeration of non-separable graphs, J. combin. theory, 9, 327-356, (1970) · Zbl 0217.02501
[22] Robinson, R.W.; Walsh, T.R., Inversion of cycle index sum relations for 2- and 3-connected graphs, J. combin. theory ser. B, 37, 289-308, (1993) · Zbl 0728.05026
[23] Tutte, W.T., A census of planar maps, Canad. J. math., 15, 249-271, (1963) · Zbl 0115.17305
[24] Tutte, W.T., On the enumeration of planar maps, Bull. amer. math. soc., 74, 64-74, (1968) · Zbl 0157.31101
[25] Walsh, T.R., Hypermaps versus bipartite maps, J. combin. theory ser. B, 18, 2, 155-163, (1975) · Zbl 0302.05101
[26] Walsh, T.R., Counting unlabelled three-connected and homeomorphically irreducible two-connected graphs, J. combin. theory ser. B, 32, 12-32, (1982) · Zbl 0449.05032
[27] Walsh, T.R., Counting non-isomorphic three-connected planar maps, J. combin. theory ser. B, 32, 33-44, (1982) · Zbl 0443.05050
[28] Walsh, T.R., A polynomial-time algorithm for counting rooted toroidal maps, Ars combin., 16, 49-56, (1983) · Zbl 0553.05041
[29] Walsh, T.R.; Lehman, A.B., Counting rooted maps by genus II, J. combin. theory ser. B, 13, 122-141, (1972), (See also the erratum in J. Combin. Theory Ser. B 13 (1973) 666) · Zbl 0228.05109
[30] Whitney, H., 2-isomorphic graphs, Amer. J. math., 55, 245-254, (1933) · JFM 59.1235.01
[31] Wielandt, H., Finite permutation groups, (1694), Academic Press New York
[32] Wormald, N.C., On the number of planar maps, Canad. J. math., XXXIII, 1, 1-11, (1981) · Zbl 0408.57006
[33] Wormald, N.C., Counting unrooted planar maps, Discrete math., 36, 205-225, (1981) · Zbl 0467.05034
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.