×

zbMATH — the first resource for mathematics

Generating nonisomorphic maps without storing them. (English) Zbl 0521.05034

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] Aho, AlfredV.; Hopcroft, JohnE.; Ullman, JeffreyD., The design and analysis of computer algorithms, (1975) · Zbl 0326.68005
[2] Baker, H. H.; Dewdney, A. K.; Szilard, A. L., Generating the nine-point graphs, Math. Comp., 28, 833, (1974) · Zbl 0289.05121
[3] Brown, WilliamG., On the enumeration of non-planar maps, Mem. Amer. Math. Soc., 65, 42, (1966) · Zbl 0149.21201
[4] Cori, Robert, Un code pour les graphes planaires et ses applications, (1975) · Zbl 0313.05115
[5] Duijvestijn, A. J. W., Simple perfect squared square of lowest order, J. Combin. Theory Ser. B, 25, 240, (1978) · Zbl 0403.05026
[6] Masters ThesisA combinatorial representation for oriented polyhedral surfacesM.A. ThesisUniversity of Maryland, College Park1960See also Notices Amer. Math. Soc., 7 (1960), p. 646
[7] Faradzev, I. A., Generation of nonisomorphic graphs with a given distribution of the degrees of vertices, Algorithmic studies in combinatorics (Russian), (1978), “Nauka”, Moscow
[8] Heap, B. R., The production of graphs by computer, Graph theory and computing, 47, (1972), Academic Press, New York · Zbl 0247.05144
[9] Hopcroft, J. E.; Tarjan, R. E., A V\({\rm log}\ V\) algorithm for isomorphism of triconnected planar graphs, J. Comput. System Sci., 7, 323, (1973) · Zbl 0274.05103
[10] Hopcroft, J. E.; Tarjan, R. E., Dividing a graph into triconnected components, SIAM J. Comput., 2, 135, (1973) · Zbl 0281.05111
[11] Jacques, A.; Erdös, P., Constellations et graphes topologiques, Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), 657, (1970), North-Holland, Amsterdam · Zbl 0213.25901
[12] Läuchli, P., Generating all planar 0-, 1-, 2-, 3-connected graphs, 379, (1981) · Zbl 0454.68079
[13] Maps and their encoding1965unpublished manuscript
[14] Full genus maps and hypermaps1973unpublished manuscript
[15] Liskovets, V. A., A census of nonisomorphic planar maps, Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), 25, 479, (1981), North-Holland, Amsterdam · Zbl 0519.05040
[16] Counting non-isomorphic 2-connected planar maps1980Canad. J. Math., submitted. See also Graph Theory Newslett. 9, no. 6, p. 3.
[17] Read, RonaldC., Every one a winner or how to avoid isomorphism search when cataloguing combinatorial configurations, Ann. Discrete Math., 2, 107, (1978) · Zbl 0392.05001
[18] Tarjan, Robert, Depth-first search and linear graph algorithms, SIAM J. Comput., 1, 146, (1972) · Zbl 0251.05107
[19] Tarry, G., Le problème des labyrinthes, Nouvelles Annales de Mathématiques, 3, 187, (1895) · JFM 26.0645.02
[20] Tutte, W. T., A theory of 3-connected graphs, Nederl. Akad. Wetensch. Proc. Ser. A 64 = Indag. Math., 23, 441, (1961) · Zbl 0101.40903
[21] Tutte, W. T., A census of planar maps, Canad. J. Math., 15, 249, (1963) · Zbl 0115.17305
[22] Ph.D. ThesisCombinatorial enumeration of non-planar mapsUniv. of TorontoToronto, Ontario, Canada1971
[23] Walsh, T. R. S., Counting nonisomorphic three-connected planar maps, J. Combin. Theory Ser. B, 32, 33, (1982) · Zbl 0443.05050
[24] Walsh, T. R. S.; Lehman, A. B., Counting rooted maps by genus. I, J. Combinatorial Theory Ser. B, 13, 192, (1972) · Zbl 0228.05108
[25] Walsh, T. R. S.; Lehman, A. B.; Walsh, T. R. S.; Lehman, A. B., Erratum: “counting rooted maps by genus. II”, J. Combinatorial Theory Ser. B, 14, 185, (1973) · Zbl 0261.05105
[26] Walsh, T. R. S.; Lehman, A. B., Counting rooted maps by genus. III: nonseparable maps, J. Combinatorial Theory Ser. B, 18, 222, (1975) · Zbl 0299.05110
[27] Counting unrooted planar mapsResearch Report Corr.79-32Univ. of WaterlooWaterloo, Ontario, Canada1979
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.