The Schlegel diagram of a convex polyhedron represents its vertices and edges as points and line segments in the Euclidean plane, forming a subdivision of an outer convex polygon into smaller convex polygons (a convex drawing of the graph of the polyhedron).
[1][2] 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.
[3] 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, but this conjecture was disproved by a counterexample of W. T. Tutte, the polyhedral but non-Hamiltonian Tutte graph.
(the shortness exponent) and an infinite family of polyhedral graphs such that the length of the longest simple path of an
The Halin graphs, graphs formed from a planar embedded tree by adding an outer cycle connecting all of the leaves of the tree, form another important subclass of the polyhedral graphs.