The number of polyhedral (connected planar) graphs
Authors:
A. J. W. Duijvestijn and P. J. Federico
Journal:
Math. Comp. 37 (1981), 523532
MSC:
Primary 05C30; Secondary 05C10, 52A25
MathSciNet review:
628713
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Data is presented on the number of 3connected 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 10hedra to be presented for the first time, as well as estimates of the number of 11hedra and dodecahedra.
 [1]
L. Euler, "Elementa doctrinae solidorum," Novi Comm. Acad. Petrop. 17523, v. 4, 1758, pp. 109140; Opera (I), v. 26, pp. 7193. Read November 25, 1750.
 [2]
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.
 [3]
T. P. Kirkman, "Application of the theory of the polyhedra to the enumeration and registration of resulte," Proc. Roy. Soc. London, v. 12, 18623, pp. 341380. Numbers: all classes with up to 8 faces or 8 vertices and class with 9 faces and 9 vertices.
 [4]
O. Hermes, "Die Formen der Vielflache," J. Reine Angew. Math., [I], v. 120, 1899, pp. 2759; [II], v. 120, 1899, pp. 305353, plate 1; [III], v. 122, 1900, pp. 124154, plates 1, 2; [IV], v. 123, 1901, pp. 312342, 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].
 [5]
M. Brückner, Vielecke und Vielflache, Teubner, Leipzig, 1900. Drawings: all trilinear (cubic) with up to 10 faces, folding plates 25. Figure 6 on plate 2 belongs with the 10faced ones on plates 35.
 [6]
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
0019311 (8,398f)
 [7]
C. J. Bouwkamp, A. J. W. Duijvestijn & P. Medema, Table of cNets 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 3connected planar graphs were called cnete in the papers on squared rectangles, see [6], [9].
 [8]
W.
T. Tutte, A theory of 3connected graphs, Nederl. Akad.
Wetensch. Proc. Ser. A 64 = Indag. Math. 23 (1961),
441–455. MR 0140094
(25 #3517)
 [9]
Adrianus
Johannes Wilhelmus Duijvestijn, Electronic computation of squared
rectangles, Thesis, Technische Wetenschap aan de Technische Hogeschool
te Eindhoven, Eindhoven, 1962. MR 0144492
(26 #2036)
 [10]
W.
T. Tutte, A census of planar maps, Canad. J. Math.
15 (1963), 249–271. MR 0146823
(26 #4343)
 [11]
D. W. Grace, Computer Search for NonIsomorphic 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.
 [12]
Frank
Harary and William
T. Tutte, On the order of the group of a planar map, J.
Combinatorial Theory 1 (1966), 394–395. MR 0200191
(34 #90)
 [13]
Rufus
Bowen and Stephen
Fisk, Generations of triangulations of the
sphere, Math. Comp. 21 (1967), 250–252. MR 0223277
(36 #6325), http://dx.doi.org/10.1090/S00255718196702232773
 [14]
R.
C. Mullin and P.
J. Schellenberg, The enumeration of 𝑐nets via
quadrangulations, J. Combinatorial Theory 4 (1968),
259–276. MR 0218275
(36 #1362)
 [15]
W. T. Tutte, "Counting planar maps," J. Recreational Math., v. 1, 1968, pp. 1927.
 [16]
P.
J. Federico, Enumeration of polyhedra: The number of 9hedra,
J. Combinatorial Theory 7 (1969), 155–161. MR 0243424
(39 #4746)
 [17]
C. J. Bouwkamp, Review of [7], Math. Comp., v. 24, 1970, pp. 995997.
 [18]
Frank
Harary and Edgar
M. Palmer, Graphical enumeration, Academic Press, New York,
1973. MR
0357214 (50 #9682)
 [19]
Doyle Britton & J. D. Dunitz, "A complete catalogue of polyhedra with eight or fewer vertices," Acta Cryst. Sect. A, v. A29, 1973, pp. 362371. Drawings: all classes with up to 8 vertices.
 [20]
Branko
Grünbaum, Polytopal graphs, Studies in graph theory, Part
II, Math. Assoc. Amer., Washington, D. C., 1975, pp. 201–224.
Studies in Math., Vol. 12. MR 0406868
(53 #10654)
 [21]
P. J. Federico, "The number of polyhedra," Philips Res. Rep., v. 30, 1975, pp. 220231.
 [22]
P.
J. Federico, Polyhedra with 4 to 8 faces, Geometriae Dedicata
3 (1974/75), 469–481. MR 0370358
(51 #6585)
 [23]
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.
 [24]
A. J. W. Duijvestijn, List of 3Connected 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 selfdual 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.
 [25]
W.
T. Tutte, On the enumeration of convex polyhedra, J. Combin.
Theory Ser. B 28 (1980), no. 2, 105–126. MR 572468
(81j:05073), http://dx.doi.org/10.1016/00958956(80)900593
 [1]
 L. Euler, "Elementa doctrinae solidorum," Novi Comm. Acad. Petrop. 17523, v. 4, 1758, pp. 109140; Opera (I), v. 26, pp. 7193. Read November 25, 1750.
 [2]
 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.
 [3]
 T. P. Kirkman, "Application of the theory of the polyhedra to the enumeration and registration of resulte," Proc. Roy. Soc. London, v. 12, 18623, pp. 341380. Numbers: all classes with up to 8 faces or 8 vertices and class with 9 faces and 9 vertices.
 [4]
 O. Hermes, "Die Formen der Vielflache," J. Reine Angew. Math., [I], v. 120, 1899, pp. 2759; [II], v. 120, 1899, pp. 305353, plate 1; [III], v. 122, 1900, pp. 124154, plates 1, 2; [IV], v. 123, 1901, pp. 312342, 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].
 [5]
 M. Brückner, Vielecke und Vielflache, Teubner, Leipzig, 1900. Drawings: all trilinear (cubic) with up to 10 faces, folding plates 25. Figure 6 on plate 2 belongs with the 10faced ones on plates 35.
 [6]
 C. J. Bouwkamp, "On the dissection of rectangles into squares. I," Nederl. Akad. Wetensch. Proc., v. A49, 1946, pp. 17761188 (= Indag. Math., v. 8, 1946, pp. 724736); II and III, Nederl. Akad. Wetensch. Proc., v. A50, 1947, pp. 5871, 7278 (= Indag. Math., v. 9, 1947, pp. 4356, 5763). Drawings: all with up to 14 edges, Part II, Figures 5, 7, 8. Professor Bouwkamp has called attention to the following corrections: Figure 5, second row, delete the second double arrow, third row, change to ; Figure 8, a missing dual pair can be reconstructed from the last row of data on page 71 [17]. MR 0019311 (8:398f)
 [7]
 C. J. Bouwkamp, A. J. W. Duijvestijn & P. Medema, Table of cNets 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 3connected planar graphs were called cnete in the papers on squared rectangles, see [6], [9].
 [8]
 W. T. Tutte, "A theory of 3connected graphs," Nederl. Akad. Wetensch. Proc. Ser. A, v. 64 (= Indag. Math., v. 23, 1961, pp. 451455). MR 0140094 (25:3517)
 [9]
 A. J. W. Duijvestijn, Electronic Computation of Squared Rectangles, Thesis, Technische Hogeschool, Eindhoven, Netherlands, 1962; also in Philips Res. Rep., v. 17, 1962, pp. 523612. Descriptions: 15 and 16 edges but only one of a dual pair. MR 0144492 (26:2036)
 [10]
 W. T. Tutte, "A census of planar maps," Canad. J. Math., v. 15, 1963, pp. 249271. MR 0146823 (26:4343)
 [11]
 D. W. Grace, Computer Search for NonIsomorphic 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.
 [12]
 F. Harary & W. T. Tutte, "On the order of the group of a planar graph," J. Combin. Theory, v. 1, 1966, pp. 394395. MR 0200191 (34:90)
 [13]
 R. Bowen & S. Fiske, "Generation of triangulations of the sphere," Math. Comp., v. 21, 1967, pp. 250252. Numbers: triangulations (duals of cubic) with up to 12 vertices. MR 0223277 (36:6325)
 [14]
 R. C. Mullin & P. J. Schellenberg, "The enumeration of cnets via quadrangulations," J. Combin. Theory, v. 4, 1968, pp. 259276. In this paper, as well as in [10], "cnets" refers to rooted 3connected planar graphs, but in [7] the same term is used for the unrooted graphs. MR 0218275 (36:1362)
 [15]
 W. T. Tutte, "Counting planar maps," J. Recreational Math., v. 1, 1968, pp. 1927.
 [16]
 P. J. Federico, "Enumeration of polyhedra: the number of 9hedra," J. Combin. Theory, v. 7, 1969, pp. 155161. Numbers: to 9 faces or vertices and to 19 edges. MR 0243424 (39:4746)
 [17]
 C. J. Bouwkamp, Review of [7], Math. Comp., v. 24, 1970, pp. 995997.
 [18]
 F. Harary & E. M. Palmer, Graphical Enumeration, Academic Press, New York, 1973, p. 224. MR 0357214 (50:9682)
 [19]
 Doyle Britton & J. D. Dunitz, "A complete catalogue of polyhedra with eight or fewer vertices," Acta Cryst. Sect. A, v. A29, 1973, pp. 362371. Drawings: all classes with up to 8 vertices.
 [20]
 B. Grünbaum, "Polytopal graphs," in Studies in Graph Theory, Part II, MAA Studies in Mathematics, vol. 12, Math. Assoc. Amer., Washington, D. C., 1975, pp. 201224. MR 0406868 (53:10654)
 [21]
 P. J. Federico, "The number of polyhedra," Philips Res. Rep., v. 30, 1975, pp. 220231.
 [22]
 P. J. Federico, "Polyhedra with 4 to 8 faces," Geom. Dedicata, v. 3, 1975, pp. 469481. Drawings: all classes with up to 8 faces. The following corrections to the accompanying table are noted: line 24 change Symmetry entry to 4; line 169, change Faces entry to 242; line 219, change Faces entry to 224; line 301, change Vertices entry to 222. MR 0370358 (51:6585)
 [23]
 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.
 [24]
 A. J. W. Duijvestijn, List of 3Connected 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 selfdual 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.
 [25]
 W. T. Tutte, "On the enumeration of convex polyhedra," J. Combin. Theory Ser. B, v. 28 B, 1980, pp. 105126. MR 572468 (81j:05073)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
05C30,
05C10,
52A25
Retrieve articles in all journals
with MSC:
05C30,
05C10,
52A25
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198106287133
PII:
S 00255718(1981)06287133
Article copyright:
© Copyright 1981 American Mathematical Society
