TOPICS
Search

Polyhedral Graph


An n-polyhedral graph (sometimes called a c-net) is a 3-connected simple planar graph on n nodes. Every convex polyhedron can be represented in the plane or on the surface of a sphere by a 3-connected planar graph. Conversely, by a theorem of Steinitz as restated by Grünbaum (2003, p. 235), every 3-connected planar graph can be realized as a convex polyhedron (Duijvestijn and Federico 1981). Polyhedral graphs are sometimes simply known as "polyhedra" (which is rather confusing since the term "polyhedron" more commonly refers to a solid with n faces, not n vertices).

PolyhedralGraphs

The number of distinct polyhedral graphs having V=1, 2, ... vertices are 0, 0, 0, 1, 2, 7, 34, 257, 2606, ... (OEIS A000944; Grünbaum 2003, p. 424; Duijvestijn and Federico 1981; Croft et al. 1991; Dillencourt 1992). Through duality, each polyhedral graph on V=n nodes corresponds to a graph (and polyhedron) with F=n faces. So the polyhedral graphs on n nodes are isomorphic to the convex polyhedra with n faces. There is therefore a single tetrahedral graph, two pentahedral graphs, etc., meaning also that there is a single tetrahedron, two pentahedra, etc.

There is no known formula for enumerating the number of nonisomorphic polyhedral graphs by numbers of edges E, vertices V, or faces F (Harary and Palmer 1973, p. 224; Duijvestijn and Federico 1981). The numbers for the first few are summarized in the table below.

Duijvestijn and Federico (1981) enumerated the polyhedral graphs on E edges, obtaining 1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, ... (OEIS A002840) for E=6, 7, 8, ....

The smallest nonnamiltonian polyhedral graph is the Herschel graph, which has 11 nodes. The numbers of non-Hamiltonian polyhedral graphs on n=11, 12, ... nodes are 1, 2, 30, 239, 2369, 22039, 205663, ... (OEIS A007030; Dillencourt 1991). Similarly, the numbers of non-Hamiltonian polyhedral graphs with f=9, 10, ... faces are 1, 8, 135, 2557, ... (OEIS A007032; Dillencourt 1991).

There are no untraceable graphs polyhedral graphs on 13 or fewer nodes.

As shown by Whitney (1932), polyhedral graphs are uniquely embeddable (Fleischner 1973).


See also

Convex Polyhedron, Cubical Graph, Dodecahedral Graph, Icosahedral Graph, k-Connected Graph, Octahedral Graph, Planar Connected Graph, Planar Graph, Platonic Graph, Polyhedral Formula, Polyhedral Group, Polytopal Graph, Schlegel Graph, Simple Graph, Skeleton, Tetrahedral Graph, Tutte's Wheel Theorem Explore this topic in the MathWorld classroom

Explore with Wolfram|Alpha

References

Bouwkamp, C. J.; Duijvestijn, A. J. W.; and Medema, P. Table of c-Nets of Orders 8 to 19, Inclusive, 2 vols. Unpublished manuscript. Eindhoven, Netherlands: Philips Research Laboratories, 1960.Croft, H. T.; Falconer, K. J.; and Guy, R. K. §B15 in Unsolved Problems in Geometry. New York: Springer-Verlag, 1991.Dillencourt, M. B. "Polyhedra of Small Orders and Their Hamiltonian Properties." Tech. Rep. 92-91, Info. and Comput. Sci. Dept. Irvine, CA: Univ. Calif. Irvine, 1992.Dillencourt, M. B. "Polyhedra of Small Orders and Their Hamiltonian Properties." J. Combin. Th., Ser. B 66, 87-122, 1996.Duijvestijn, A. J. W. "List of 3-Connected Planar Graphs with 6 to 22 Edges." Unpublished computer tape. Enschede, Netherlands: Twente Univ. Technology, 1979.Duijvestijn, A. J. W. and Federico, P. J. "The Number of Polyhedral (3-Connected Planar) Graphs." Math. Comput. 37, 523-532, 1981.Federico, P. J. "Enumeration of Polyhedra: The Number of 9-Hedra." J. Combin. Th. 7, 155-161, 1969.Federico, P. J. "The Number of Polyhedra." Philips Res. Rep. 30, 220-231, 1975.Fleischner, H. "The Uniquely Embeddable Planar Graphs." Disc. Math. 4, 347-358, 1973.Grünbaum, B. "Polytopal Graphs." In Studies in Graph Theory, Part 2 (Ed. D. R. Fulkerson). Washington, DC: Math. Assoc. Amer., pp. 201-224, 1975.Grünbaum, B. Convex Polytopes, 2nd ed. New York: Springer-Verlag, 2003.Harary, F. and Palmer, E. M. Graphical Enumeration. New York: Academic Press, 1973.Sloane, N. J. A. Sequences A007030/M2152, A007032/M4574, A000944/M1796 and A002840/M0339 in "The On-Line Encyclopedia of Integer Sequences."Tutte, W. T. "A Theory of 3-Connected Graphs." Indag. Math. 23, 451-455, 1961.Tutte, W. T. "On the Enumeration of Convex Polyhedra." J. Combin. Th. Ser. B 28, 105-126, 1980.Whitney, H. "Congruent Graphs and the Connectivity of Graphs." Amer. J. Math. 54, 150-168, 1932.

Referenced on Wolfram|Alpha

Polyhedral Graph

Cite this as:

Weisstein, Eric W. "Polyhedral Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PolyhedralGraph.html

Subject classifications