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?
$\begingroup$
$\endgroup$
2
asked Dec 18, 2009 at 9:57
-
$\begingroup$ Polyhedron or polytope? $\endgroup$– ThornyDec 18, 2009 at 12:04
-
$\begingroup$ Polytope of arbitrary dimension $\endgroup$– Hans-Peter StrickerDec 18, 2009 at 14:20
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
9
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.
answered Dec 18, 2009 at 12:51
-
$\begingroup$ 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? $\endgroup$ Dec 18, 2009 at 13:01
-
$\begingroup$ 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. $\endgroup$ Dec 18, 2009 at 13:55
-
-
1$\begingroup$ 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. $\endgroup$ Dec 18, 2009 at 22:45
-
1$\begingroup$ I believe that the convex hull of the points $(e^{2 \pi i k/n}, e^{4 \pi i k /n})$ in $\mathbb{C}^2$, for $0 \leq k < n$, has edge graph $K_n$ and is clearly vertex transitive. I wouldn't be surprised if could make a harder example with all edges the same length. $\endgroup$ Jul 26, 2018 at 15:45
$\begingroup$
$\endgroup$
6
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 (Neighborly cubical polytopes) 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 the paper On locally constructible spheres and balls of Benedetti and Ziegler (published in Acta in 2011). 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).
answered Apr 30, 2010 at 12:38
-
$\begingroup$ 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? $\endgroup$ Jul 24, 2010 at 17:52
-
-
1$\begingroup$ 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. $\endgroup$ Jul 25, 2010 at 1:18
-
$\begingroup$ 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? $\endgroup$ Jul 25, 2010 at 2:57
-
$\begingroup$ I see, i suppose you still insist on a realization with line intervals for edges and plane triangles for 2-faces. It is true that Tarski's algorithm applies but this algoithm is highly inpracticle. $\endgroup$ Jul 25, 2010 at 16:27
5
-
$\begingroup$ OK, but in arbitrary dimension? $\endgroup$ Dec 18, 2009 at 11:40
-
3$\begingroup$ 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." $\endgroup$ Dec 18, 2009 at 20:27
-
$\begingroup$ 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? $\endgroup$ Jul 24, 2010 at 4:18
-
-
$\begingroup$ Then, do we know of a theorem that characterizes the 1-skeleton of some other kind of polytopes (i.e., not necessarily convex)? $\endgroup$ Jul 24, 2010 at 14:46
$\begingroup$
$\endgroup$
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.)
