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

, a branch of

mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, a polyhedral graph is the

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

formed from the vertices and edges 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 wo ...

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

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

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

, 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 In graph drawing, a convex drawing of a planar graph is a drawing that represents the vertices of the graph as points in the Euclidean plane and the edges as straight line segments, in such a way that all of the faces of the drawing (including the ...

of the graph of the polyhedron). It has no crossings, so every polyhedral graph is also a

. Additionally, by

Balinski's theorem In polyhedral combinatorics, a branch of mathematics, Balinski's theorem is a statement about the graph-theoretic structure of three-dimensional convex polyhedra and higher-dimensional convex polytopes. It states that, if one forms an undirected ...

, 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 In mathematics, an isomorphism is a structure-preserving mapping 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 them. The word is ...

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.

Hamiltonicity and shortness

Tait conjectured that every cubic 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 a ...

W. T. Tutte William Thomas Tutte OC FRS FRSC (; 14 May 1917 – 2 May 2002) was an English and Canadian codebreaker and mathematician. During the Second World War, he made a brilliant and fundamental advance in cryptanalysis of the Lorenz cipher, a majo ...

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

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

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

Goldner–Harary graph In the mathematical field of graph theory, the Goldner–Harary graph is a simple undirected graph with 11 vertices and 27 edges. It is named after A. Goldner and Frank Harary, who proved in 1975 that it was the smallest non-Hamiltonian maximal ...

. 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 the graphs in the family can be. Intuitively, if e is the shortness exponent of a graph family , then every n-vertex graph ...

) 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 In geometry, a -dimensional simple polytope is a -dimensional polytope each of whose vertices are adjacent to exactly edges (also facets). The vertex figure of a simple -polytope is a -simplex. Simple polytopes are topologically dual to si ...

if it is cubic (every vertex has three edges), and it is the graph of a

simplicial polyhedron In geometry, a simplicial polytope is a polytope whose facets are all simplices. For example, a ''simplicial polyhedron'' in three dimensions contains only triangular facesPolyhedra, Peter R. Cromwell, 1997. (p.341) and corresponds via Steinitz's ...

if it is a

maximal 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 cros ...

. The

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

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