geometric graph theory Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geomet ...

, a branch of

mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, a polyhedral graph is the

undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

formed from the vertices and edges of a

convex polyhedron In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional figure with flat polygonal faces, straight edges and sharp corners or vertices. The term "polyhedron" may refer either to a solid figure or to its boundary su ...

. 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 (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

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, a Euclidean plane is a Euclidean space of Two-dimensional space, dimension two, denoted \textbf^2 or \mathbb^2. It is a geometric space in which two real numbers are required to determine the position (geometry), position of eac ...

, 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 ...

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 In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedron, convex polyhedra: they are exactly the vertex connect ...

, 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 In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...

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 that ...

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 mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...

, 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 "student John Smith is not lazy" is a c ...

of W. T. Tutte, the polyhedral but non-

Hamiltonian Hamiltonian may refer to: * Hamiltonian mechanics, a function that represents the total energy of a system * Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system ** Dyall Hamiltonian, a modified Hamiltonian ...

Tutte graph In the mathematical field of graph theory, the Tutte graph is a 3-regular graph with 46 vertices and 69 edges named after W. T. Tutte. It has chromatic number 3, chromatic index 3, girth 4 and diameter 8. The Tutte graph is a cubic polyhedral gr ...

. 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 graph, 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 d ...

, and there also exists an 11-vertex non-Hamiltonian polyhedral graph in which all faces are triangles, the

Goldner–Harary graph In the mathematics, mathematical field of graph theory, the Goldner–Harary graph is a simple undirected graph with 11 vertices and 27 edges. It is named after Anita M. Goldner and Frank Harary, who proved in 1975 that it was the smallest Hamilt ...

. More strongly, there exists a constant

\alpha<1

(the shortness exponent) 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^)

. A problem with one additional constraint exists,

Barnette's conjecture Barnette's conjecture is an conjecture, unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after David W. Barnette, a professor emeritus at the University of California, Davis; it state ...

, asking whether every cubic '' bipartite'' polyhedral graph is Hamiltonian, which remains unsolved.

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

The graphs of the

Platonic solid In geometry, a Platonic solid is a Convex polytope, convex, regular polyhedron in three-dimensional space, three-dimensional Euclidean space. Being a regular polyhedron means that the face (geometry), faces are congruence (geometry), congruent (id ...

s have been called ''Platonic graphs''. As well as having all the other properties of polyhedral graphs, these are

symmetric graph In the mathematical field of graph theory, a graph is symmetric or arc-transitive if, given any two ordered pairs of adjacent vertices (u_1,v_1) and (u_2,v_2) of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 a ...

s, and all of them have

s. There are five of these graphs: *

Tetrahedral graph In geometry, a tetrahedron (: tetrahedra or tetrahedrons), also known as a triangular pyramid, is a polyhedron composed of four triangular faces, six straight edges, and four vertices. The tetrahedron is the simplest of all the ordinary conve ...

– 4 vertices, 6 edges * Octahedral graph – 6 vertices, 12 edges *

Cubical graph A cube or regular hexahedron is a three-dimensional solid object in geometry, which is bounded by six congruent square faces, a type of polyhedron. It has twelve congruent edges and eight vertices. It is a type of parallelepiped, with pairs of pa ...

– 8 vertices, 12 edges * Icosahedral graph – 12 vertices, 30 edges * Dodecahedral graph – 20 vertices, 30 edges A polyhedral graph is the graph of a

simple polyhedron In geometry, a -dimensional simple polytope is a -dimensional polytope each of whose vertex (geometry), vertices are adjacent to exactly edge (geometry), edges (also Facet (geometry), facets). The vertex figure of a simple -polytope is a -simp ...

if it is

(every vertex has three edges), and it is the graph of a simplicial polyhedron if it is a maximal planar graph. For example, the tetrahedral, cubical, and dodecahedral graphs are simple; the tetrahedral, octahedral, and icosahedral graphs are simplicial. The

Halin graph In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree (graph theory), tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in ...

s, 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, e.g., including only woody plants with secondary growth, only ...

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

References

External links