In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and

edges Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed by ...

of a

convex polyhedron A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the w ...

. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-connected,

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

Characterization

The

Schlegel diagram In geometry, a Schlegel diagram is a projection of a polytope from \mathbb^d into \mathbb^ through a point just outside one of its facets. The resulting entity is a polytopal subdivision of the facet in \mathbb^ that, together with the ori ...

of a convex polyhedron represents its vertices and edges as points and line segments in the

Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions ...

, forming a subdivision of an outer

convex polygon In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is a ...

into smaller convex polygons (a convex drawing of the graph of the polyhedron). It has no crossings, so every polyhedral graph is also a

. Additionally, by Balinski's theorem, it is a 3-vertex-connected graph. According to Steinitz's theorem, these two graph-theoretic properties are enough to completely characterize the polyhedral graphs: they are exactly the 3-vertex-connected planar graphs. That is, whenever a graph is both planar and 3-vertex-connected, there exists a polyhedron whose vertices and edges form an isomorphic graph.. Given such a graph, a representation of it as a subdivision of a convex polygon into smaller convex polygons may be found using the

Tutte embedding In graph drawing and geometric graph theory, a Tutte embedding or barycentric embedding of a simple, 3-vertex-connected, planar graph is a crossing-free straight-line embedding with the properties that the outer face is a convex polygon and tha ...

Hamiltonicity and shortness

Tait conjectured that every

cubic Cubic may refer to: Science and mathematics * Cube (algebra), "cubic" measurement * Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex ** Cubic crystal system, a crystal system w ...

polyhedral graph (that is, a polyhedral graph in which each vertex is incident to exactly three edges) has a

Hamiltonian cycle In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

, but this conjecture was disproved by a

counterexample A counterexample is any exception to a generalization. In logic a counterexample disproves the generalization, and does so rigorously in the fields of mathematics and philosophy. For example, the fact that "John Smith is not a lazy student" is ...

of W. T. Tutte, the polyhedral but non- Hamiltonian Tutte graph. If one relaxes the requirement that the graph be cubic, there are much smaller non-Hamiltonian polyhedral graphs. The graph with the fewest vertices and edges is the 11-vertex and 18-edge

Herschel graph In graph theory, a branch of mathematics, the Herschel graph is a bipartite undirected graph with 11 vertices and 18 edges. It is a polyhedral graph (the graph of a convex polyhedron), and is the smallest polyhedral graph that does not have a ...

, and there also exists an 11-vertex non-Hamiltonian polyhedral graph in which all faces are triangles, the Goldner–Harary graph. More strongly, there exists a constant

\alpha<1

(the

shortness exponent In graph theory, the shortness exponent is a numerical parameter of a family of graphs that measures how far from Hamiltonian Hamiltonian may refer to: * Hamiltonian mechanics, a function that represents the total energy of a system * Hamiltonian ...

) and an infinite family of polyhedral graphs such that the length of the longest simple path of an

n

-vertex graph in the family is

O(n^)

Combinatorial enumeration

Duijvestijn provides a count of the polyhedral graphs with up to 26 edges;. The number of these graphs with 6, 7, 8, ... edges is :1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810, ... . One may also enumerate the polyhedral graphs by their numbers of vertices: for graphs with 4, 5, 6, ... vertices, the number of polyhedral graphs is :1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, ... .

Special cases

A polyhedral graph is the graph of a simple polyhedron if it is

(every vertex has three edges), and it is the graph of a simplicial polyhedron if it is a maximal planar graph. The Halin graphs, graphs formed from a planar embedded

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

by adding an outer cycle connecting all of the leaves of the tree, form another important subclass of the polyhedral graphs.

References

External links

*{{mathworld, title=Polyhedral Graph, urlname=PolyhedralGraph, mode=cs2 Geometric graphs Planar graphs