Spanning polytopes

Question

Hamiltonian cycles (seen as spanning polygons) are interesting for several reasons (only a few of which I am aware of), but especially because not every connected graph has a Hamiltonian cycle (is Hamiltonian), so the characterization of Hamiltonian graphs becomes interesting (see wikipedia article on Hamiltonian paths).

Side note: Each platonic and archimedian solid is Hamiltonian.

What about spanning polytopes, as one possible generalization of Hamiltonian cycles = spanning polygons?

(By "spanning polytope" I mean a spanning subgraph that is the 1-skeleton of a polytope of arbitrary dimension.)

There are connected graphs without spanning polytopes (trees obviously), but there are non-Hamiltonian graphs that have a spanning polytope of dimension d>2, e.g. the Herschel graph.

A google search for "spanning polytope" yields only very few and unrelated results, so my question is:

Is there research on this or a related topic, only under another name?

If not so, does this have an obvious - or not so obvious - reason?

Answer 1

Unfortunately, there is no known good characterization of which graphs are the 1-skeleton of some polytope in some dimension d. There are several interesting properties of polytope graphs that may be of interest to you:

$\bullet$ In $\mathbb{R}^3$, Steinitz's theorem characterizes all polytopal graphs as the planar 3-connected graphs.

$\bullet$ In d > 3, the cyclic polytopes have $K_n$ as a 1-skeleton. A result of Perles implies that every graph $G$, $G$+$K_n$ is a d-polytopal graph for some n and some d, although it is unknown what the minimum n is for a given $G$.

$\bullet$ It is a theorem of Balinski that the graph of a polytope in $\mathbb{R}^d$ is d-connected, so graphs with polytopal spanning subgraphs must have a highly connected subgraph.

There are also results about how to determine whether a specific graph $G$ is a polytopal graph, but they do not extend into a classification of all polytopal graphs.

There have been studies into classes of abstract polytope graphs, classes which contain all the 1-skeletons of polytopes but likely contain graphs with no polytopal realization, for example in this paper of Eisenbrand, Haehnle, and Rothboss Diameter of Polyhedra: Limits of Abstraction

For more information, check out Gil Kalai's chapter 19 in the Handbook of Discrete and Computational Geometry by Jacob E. Goodman and Joseph O'Rourke (or Gil Kalai's excellent blog gilkalai.wordpress.com/ ) or Grunbaum's Convex Polyopes.