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.
No comments:
Post a Comment