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?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityHow 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?
A few comments:
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.
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).
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.)