Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

The number of polyhedral ($3$-connected planar) graphs
HTML articles powered by AMS MathViewer

by A. J. W. Duijvestijn and P. J. Federico PDF
Math. Comp. 37 (1981), 523-532 Request permission

Abstract:

Data is presented on the number of 3-connected planar graphs, isomorphic to the graphs of convex polyhedra, with up to 22 edges. The numbers of such graphs having the same number of edges, and the same number of vertices and faces, are tabulated. Conjectured asymptotic formulas by W. T. Tutte and by R. C. Mullin and P. J. Schellenberg are discussed. Additional data beyond 22 edges are given enabling the number of 10-hedra to be presented for the first time, as well as estimates of the number of 11-hedra and dodecahedra.
References
    L. Euler, "Elementa doctrinae solidorum," Novi Comm. Acad. Petrop. 1752-3, v. 4, 1758, pp. 109-140; Opera (I), v. 26, pp. 71-93. Read November 25, 1750. J. Steiner, "Problème de situation," Ann. de Math., v. 19, 1828, p. 36; Gesammelte Werke, vol. 1, p. 227. Descriptions: 4, 5 and 6 faces. T. P. Kirkman, "Application of the theory of the polyhedra to the enumeration and registration of resulte," Proc. Roy. Soc. London, v. 12, 1862-3, pp. 341-380. Numbers: all classes with up to 8 faces or 8 vertices and class with 9 faces and 9 vertices. O. Hermes, "Die Formen der Vielflache," J. Reine Angew. Math., [I], v. 120, 1899, pp. 27-59; [II], v. 120, 1899, pp. 305-353, plate 1; [III], v. 122, 1900, pp. 124-154, plates 1, 2; [IV], v. 123, 1901, pp. 312-342, plate 1. Descriptions: all with up to 8 faces, Part II; all trilinear (cubic) with up to 10 faces, Part I. Contains erroneous tables for 9 faces and 9 vertices and erroneous numbers for trilinear (cubic) with 11 and 12 faces [16]. M. Brückner, Vielecke und Vielflache, Teubner, Leipzig, 1900. Drawings: all trilinear (cubic) with up to 10 faces, folding plates 2-5. Figure 6 on plate 2 belongs with the 10-faced ones on plates 3-5.
  • C. J. Bouwkamp, On the dissection of rectangles into squares. II, III, Nederl. Akad. Wetensch., Proc. 50 (1947), 58–71, 72–78 = Indagationes Math. 9, 43–56, 57–63 (1947). MR 19311
    • C. J. Bouwkamp, A. J. W. Duijvestijn & P. Medema, Table of c-Nets of Orders 8 to 19, Inclusive, Philips Research Laboratories, Eindhoven, Netherlands, 2 vols., 1960. Unpublished available in UMT file. Descriptions: all with 8 to 19 edges except that only one of a dual pair is listed. See [17] for description. The 3-connected planar graphs were called c-nete in the papers on squared rectangles, see [6], [9].
  • W. T. Tutte, A theory of $3$-connected graphs, Nederl. Akad. Wetensch. Proc. Ser. A 64 = Indag. Math. 23 (1961), 441–455. MR 0140094
  • Adrianus Johannes Wilhelmus Duijvestijn, Electronic computation of squared rectangles, Technische Hogeschool Eindhoven, Eindhoven, 1962. Thesis; Technische Wetenschap aan de Technische Hogeschool te Eindhoven. MR 0144492
  • W. T. Tutte, A census of planar maps, Canadian J. Math. 15 (1963), 249–271. MR 146823, DOI 10.4153/CJM-1963-029-x
    • D. W. Grace, Computer Search for Non-Isomorphic Convex Polyhedra, Report CS15, Computer Sci. Dept., Stanford Univ., 1965 (copy obtainable from National Technical Information Service, Dept. of Commerce, Springfield, Va. 22151 as Document AD611, 366). Descriptions: trilinear (cubic) with up to 11 faces.
  • Frank Harary and William T. Tutte, On the order of the group of a planar map, J. Combinatorial Theory 1 (1966), 394–395. MR 200191
  • Rufus Bowen and Stephen Fisk, Generations of triangulations of the sphere, Math. Comp. 21 (1967), 250–252. MR 223277, DOI 10.1090/S0025-5718-1967-0223277-3
  • R. C. Mullin and P. J. Schellenberg, The enumeration of $c$-nets via quadrangulations, J. Combinatorial Theory 4 (1968), 259–276. MR 218275
    • W. T. Tutte, "Counting planar maps," J. Recreational Math., v. 1, 1968, pp. 19-27.
  • P. J. Federico, Enumeration of polyhedra: The number of $9$-hedra, J. Combinatorial Theory 7 (1969), 155–161. MR 243424
    • C. J. Bouwkamp, Review of [7], Math. Comp., v. 24, 1970, pp. 995-997.
  • Frank Harary and Edgar M. Palmer, Graphical enumeration, Academic Press, New York-London, 1973. MR 0357214
    • Doyle Britton & J. D. Dunitz, "A complete catalogue of polyhedra with eight or fewer vertices," Acta Cryst. Sect. A, v. A29, 1973, pp. 362-371. Drawings: all classes with up to 8 vertices.
  • Branko Grünbaum, Polytopal graphs, Studies in graph theory, Part II, Studies in Math., Vol. 12, Math. Assoc. Amer., Washington, D. C., 1975, pp. 201–224. MR 0406868
    • P. J. Federico, "The number of polyhedra," Philips Res. Rep., v. 30, 1975, pp. 220$^{\ast }$-231$^{\ast }$.
  • P. J. Federico, Polyhedra with $4$ to $8$ faces, Geometriae Dedicata 3 (1974/75), 469–481. MR 370358, DOI 10.1007/BF00181378
    • A. J. W. Duijvestijn, Algorithmic Calculation of the Order of the Automorphism Group of a Graph, Memorandum No. 221, Twente Univ. of Technology, Enschede, Netherlands, 1978. A. J. W. Duijvestijn, List of 3-Connected Planar Graphs with 6 to 22 Edges, Twente Univ. of Technology, Enschede, Netherlands, 1979. (Computer tape.) Descriptions: These are arranged in files, each file containing graphs of the same number of edges ordered by identification number. Only one of a dual pair is listed the one with fewer vertices than faces; if the number of these is the same for a dual pair, the one with the larger identification number is listed. The graphs are coded by lettering the vertices A, B, C, D, ... and giving the circuit of vertices for each face, with a separation mark. Each entry gives first the code of the graph and then follows in order, an indication whether the graph is self-dual or not, the order of the automorphism group, and the identification number. Arrangements for obtaining a copy of the tape can be made by communicating with the author.
  • W. T. Tutte, On the enumeration of convex polyhedra, J. Combin. Theory Ser. B 28 (1980), no. 2, 105–126. MR 572468, DOI 10.1016/0095-8956(80)90059-3
Similar Articles
Additional Information
  • © Copyright 1981 American Mathematical Society
  • Journal: Math. Comp. 37 (1981), 523-532
  • MSC: Primary 05C30; Secondary 05C10, 52A25
  • DOI: https://doi.org/10.1090/S0025-5718-1981-0628713-3
  • MathSciNet review: 628713