Call a graph "polyhedral" if it is simple, planar, and 3-connected. For example, the 1-dimensional skeleton of every 3-dimensional convex polytope, regarded as a graph, is polyhedral. By a theoreom of Steinitz, polyhedral graphs are exactly the graphs which appear as 1-skeleta of 3-dimensional convex polytopes.
Call a graph "Steinitzian" if it has a spanning polyhedral subgraph. ("Spanning" means that it has the same vertex set.) Where do Steinitzian graphs occur naturally? Is the 1-dimensional skeleton of every 4-dimensional polytope Steinitizian? Is every 1-skeleton of a $d$-tope with $d\geq 5$ Steinitzian?
I have checked a few easy polytopes. For example, it is not too much to check that the complete graph $K_5$ (the 1-skelton of the 4-dimensional simplex) is Steinitzian. Deleting one edge from $K_5$ reveals the graph of a bipyramid, so this is a spanning polyhedral subgraph. In fact, every complete graph $K_d$ with $d\geq 5$ is Steinitizan. It seems plausible that the 1-skeleton of every 4-tope may be Steinitzian, but it's not easy for me to see why and obviously I don't know a counterexample.
Knowing that a graph is Steinitizan means that one may visualize it by first constructing a 3-dimensional polytope and then connecting various interior edges (which might be interior to 2-dimensional faces). Notice that being Steinitzian is almost a higher-dimensional version of being hamiltonian, as we call a graph hamiltonian exactly when it has a spanning subgraph which is the 1-skeleton of a 2-dimensional convex polytope.
