Return to Answer

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).

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).

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 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).

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).

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.

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 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).

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 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).