Can you determine whether a graph is the 1-skeleton of a polytope?

How do I test whether a given undirected graph is the 1-skeleton of a polytope?

How can I tell the dimension of a given 1-skeleton?

-
Polyhedron or polytope? –  Thorny Dec 18 '09 at 12:04
Polytope of arbitrary dimension –  Hans Stricker Dec 18 '09 at 14:20

In general, you can't tell the dimension of a polytope from its graph. For any $n \geq 6$, the complete graph $K_n$ is the edge graph of both a $4$-dimensional and a $5$-dimensional polytope. (Thanks to dan petersen for correcting my typo.) The term for such polytopes is "neighborly".

On the other hand, you can say that the dimension is bounded above by the lowest vertex degree occurring anywhere in the graph.

A beautiful paper of Gil Kalai shows that, given a $d$-regular graph, there is at most one way to realize it as the graph of a $d$-dimensional polytope, and gives an explicit algorithm for reconstructing that polytope. You could try running his algorithm on your graph. (Or a more efficient version recently found by Friedman.) This algorithm will output some face lattice; that is to say, it will tell you which collections of vertices should be $2$-faces, which should be $3$-faces and so forth.

Unfortunately, going from the face lattice to the polytope is very hard. According to the MathSciNet review, Richter-Gebert has shown that it is NP-hard to, given a lattice of subsets of a finite set, decide whether it is the face lattice of a polytope. Note that this is a lower bound for the difficulty of your problem.

Let me be more explicit about the last statement. Richter-Gebert shows that, given a collection $L$ of subsets of $[n]$, it is NP-hard to determine whether there is a polytope with vertices labeled by $[n]$ whose edges, $2$-faces and $3$-faces are the given sets. (Here $[n] = \{ 1,2, \ldots, n \}$.)

Suppose we had an algorithm to decide whether a graph could be the edge graph of a polytope. Take our collection $L$ and look at the two-element sets within it. These form a graph with vertex set $[n]$. Run the algorithm on it. If the output is NO, then the answer to Richter-Gebert's problem is also no. If the answer is YES, then we have the problem that our algorithm might have found a polytope whose $2$-faces and $3$-faces differ from those prescribed by $L$. If our graph is $4$-regular, this problem doesn't come up by Kalai's result. But, not having read Richter-Gebert myself, I don't know whether the problem is still NP-hard when we restrict to $4$-regular graphs.

However, even if Richter-Gebert's result doesn't apply directly, I find it difficult to imagine that there could be an efficient algorithm to solve the graph realization problem, since there isn't one to solve the face lattice problem.

-
Thanks a lot! You answered explicitly my question for the dimension. I have understood this. But what about the decision problem "G is the 1-skeleton of a polytope"? Is there no explicit procedure for arbitrary (other than d-regular) graphs? How could I approach the problem, naively and straight-ahead? –  Hans Stricker Dec 18 '09 at 13:01
I don't see how there can be, in light of Richter-Gebert's result. I'll edit my answer to spell this out more fully. –  David Speyer Dec 18 '09 at 13:55
Let's call it a moral lower bound. –  Greg Kuperberg Dec 18 '09 at 15:24
Obvious nitpick: Surely you mean that K_n can be the graph of both a 4-polytope and a 5-polytope? (Or even more generally, for $n \ge 5$, K_n can be the graph of a d-polytope, for any $4 \le d \le n-1$.) Of course the graph of a 3-polytope is planar. –  Dan Petersen Dec 18 '09 at 22:45
You are right, of course. –  David Speyer Dec 19 '09 at 15:29

A few more remarks, On the bright side: To determine if a given graph is the graph of a d-polytope is decidable. Tarski's algorithm for real closed fields can be used.

In dimension 3 as Sam Nead mentioned graphs of 3-polytopes are precisely 3 connected planar graphs. The algorithm by Hopcroft and Tarjan and various subsequent algorithms give a linear-time algorithm for planarity.

Regarding the second question, it is possible that the same graph can be realized as the graph of d-polytopes of various dimensions. David already mentioned K_n which is the graph of a d-polytope for every d between 4 and n-1. Another example is the graph of a d-cube which was proved by Joswig and Ziegler to be a graph of e-polytopes for e between 4 and d.

Another fact is that there are not so many graphs of polytopes. There are only exponentially many different graphs of simple d-polytopes with n vertices. See this paper of Benedetti and Ziegler. It is not known if this result extends to graphs of general d-polytopes, or to all subgraphs of graphs of simple d-polytopes, or to dual graphs of all triangulations of (d-1)-spheres. The later question is discussed by Gromov in the paper spaces and questions (p. 33).

-
Thanks for the link to "Spaces and Questions"! –  Victor Protsak May 17 '10 at 19:21
I have heard that it's still not known if the complete graph on 12 vertices can be realized as the 1-skeleton of a 3-polytope. But according to what you have said, it should have been decidable. So can't we just use Tarski's algorithm once on $K_12$ and check? Or is the input size really really big for this case? –  Vinayak Pathak Jul 24 '10 at 17:52
I meant $K_{12}$. –  Vinayak Pathak Jul 24 '10 at 17:53
Graphs of 3-polytopes are planar so even $K_5$ cannot be realized as the graph of a 3-polytope. you must mean something else. –  Gil Kalai Jul 25 '10 at 1:18
I am talking about the generalization of the Czaszar polyhedron. It's a polyhedron whose skeleton is $K_7$. For n = 6, 7, 8, 9, 10, 11, there cannot be a polyhedron whose skeleton is $K_n$, which can be shown using the Euler characteristic. So the next candidate is $K_12$, and that's still open. I had assumed that 3-polytopes are the same as polyhedra. But it seems they are the same as "convex" polyhedra? –  Vinayak Pathak Jul 25 '10 at 2:57

In dimension three there is the Steinitz theorem.

-
OK, but in arbitrary dimension? –  Hans Stricker Dec 18 '09 at 11:40
Günter Ziegler writes in his Lectures on Polytopes that "No similar theorem is known, and it seems that no similarly effective theorem is possible, in higher dimensions." –  David Eppstein Dec 18 '09 at 20:27
I wonder what he meant by "similar theorem". Did he mean that a theorem characterizing the 1-skeleton of convex polytopes is not known or that a theorem characterizing the 1-skeleton of general polytopes is not known? –  Vinayak Pathak Jul 24 '10 at 4:18
Convex, I would guess? –  Sam Nead Jul 24 '10 at 9:36
Then, do we know of a theorem that characterizes the 1-skeleton of some other kind of polytopes (i.e., not necessarily convex)? –  Vinayak Pathak Jul 24 '10 at 14:46

Not an answer, but potentially useful:

A matrix whose rows form an orthogonal basis of an eigenspace of a graph's adjacency matrix has columns that serve as coordinate vectors of an harmonious geometric realization of the graph.

("harmonious" == automorphisms of the graph induce rigid isometries the realization)

When the graph has a high degree of symmetry, these realizations --which I call "spectral"[*]-- have a great visual appeal; in general, though, these realizations are jumbles of points in one-dimensional space. In most cases, multiple vertices (and edges) are collapsed to single points, so that the realizations aren't faithful.

If a graph happens to admit a faithful spectral realization, you might be able to tease out a cell structure (which may not be unique), though I've not investigated this. I'll note that, even for polyhedra, there's no guarantee that the "faces" of a spectral realization are bounded by planar cycles of edges.

[*] More precisely, the realizations as described here are orthogonal projections of realizations I call "spectral". (See my still-drafty note, "Spectral Realizations of Graphs", the bulk of which is dedicated to a gallery of spectral realizations of the uniform polyhedra.)

-