<p>This is not an answer, just a comment.
Frank Lutz in Berlin is one of the experts on this topic, and you might ask him.
He maintains a nice web page,
<a href="http://page.math.tu-berlin.de/~lutz/stellar/" rel="nofollow">The Manifold Page</a>, which includes lots of information and references, including
descriptions of 
Barnette's non-polytopal 3-sphere and
Grünbaum-Sreedharan's non-polytopal 3-sphere.</p>

<p>Incidentally, I believe this related problem is still open (if not, I'd like to know of its resolution):</p>

<blockquote>
  <p>Does every triangulation of a genus 1 torus have a geometric realization (embedding) in $\mathbb{R^3}$?</p>
</blockquote>

<p>For sufficiently large genus (I think 5?), there are non-realizable examples.</p>

CC BY-SA 3.0
2011-09-26T05:11:37.910Z
Joseph, the link seems to be broken.
ilyaraz
CC BY-SA 3.0
2011-09-26T20:38:49.373Z
@ilyaraz: Thanks; the page moved.  I've relinked it.
Joseph O'Rourke
CC BY-SA 3.0
2011-01-20T14:59:35.623Z
2011-09-26T20:38:08.510Z
2011-09-26T20:38:08.510Z
Joseph O'Rourke
<p>This is a <a href="https://mathoverflow.net/questions/50100/whats-the-best-way-to-test-if-a-sphere-is-a-polytope-algorithms-for-the-simpli">cross-post</a> from MathOverflow.  </p>

<p>The problem of testing whether a simplicial face lattice (informally, a poset of faces) is polytopal is sometimes called the <a href="http://www.math.tu-bs.de/~pfetsch/apropo/simplicial_steinitz_problem.html" rel="nofollow noreferrer">Steinitz Problem</a>.</p>

<p>Sturmfels and Bokowski advanced a <a href="http://www.springer.com/mathematics/geometry/book/978-3-540-50478-8" rel="nofollow noreferrer">set of methods</a> in the late 80s to test whether the face lattice of a simplicial sphere was also realizable as a polytope.</p>

<p>The method uses oriented matroids. The problem is NP-hard, so their algorithm requires exponential time in the worst case, but they reported that the algorithm often converged quickly. Lars Schewe has <a href="http://arxiv.org/pdf/0801.2582v1" rel="nofollow noreferrer">recently shown</a> that the same method can be adapted to make use of optimized SAT solvers, although the underlying technique seems to be the same. </p>

<p>I'm curious if newer approaches have been developed in the intervening decades since Sturmfels and Bokowski published their result. Is their method still the state of the art?   Further, are there any software implementations available that solve this problem -- even using the older approach? </p>

<p>In the MathOverflow discussion, Joe O'Rourke pointed out that Polymake has a feature that seems to compute geometric realizations of simplicial complexes [GEOMETRIC_REALIZATION], but this doesn't guarantee polytopality as far as I know.  </p>

<cg.comp-geom>
What’s the best way to test if a sphere is a polytope? (the Simplicial Steinitz Problem)
Anand Kulkarni
# What’s the best way to test if a sphere is a polytope? (the Simplicial Steinitz Problem)

(Asked by: username_0 on 2011-01-19)

This is a [cross-post](https://mathoverflow.net/questions/50100/whats-the-best-way-to-test-if-a-sphere-is-a-polytope-algorithms-for-the-simpli) from MathOverflow.

The problem of testing whether a simplicial face lattice (informally, a poset of faces) is polytopal is sometimes called the [Steinitz Problem](http://www.math.tu-bs.de/~pfetsch/apropo/simplicial_steinitz_problem.html).

Sturmfels and Bokowski advanced a [set of methods](http://www.springer.com/mathematics/geometry/book/978-3-540-50478-8) in the late 80s to test whether the face lattice of a simplicial sphere was also realizable as a polytope.

The method uses oriented matroids. The problem is NP-hard, so their algorithm requires exponential time in the worst case, but they reported that the algorithm often converged quickly. Lars Schewe has [recently shown](http://arxiv.org/pdf/0801.2582v1) that the same method can be adapted to make use of optimized SAT solvers, although the underlying technique seems to be the same.

I'm curious if newer approaches have been developed in the intervening decades since Sturmfels and Bokowski published their result. Is their method still the state of the art? Further, are there any software implementations available that solve this problem -- even using the older approach?

In the MathOverflow discussion, Joe O'Rourke pointed out that Polymake has a feature that seems to compute geometric realizations of simplicial complexes [GEOMETRIC\_REALIZATION], but this doesn't guarantee polytopality as far as I know.

**Tags:** cg.comp-geom


---

## 1 answers

### Answer by username_1 on 2011-01-20. Score: 6

This is not an answer, just a comment.
Frank Lutz in Berlin is one of the experts on this topic, and you might ask him.
He maintains a nice web page,
[The Manifold Page](http://page.math.tu-berlin.de/~lutz/stellar/), which includes lots of information and references, including
descriptions of
Barnette's non-polytopal 3-sphere and
Grünbaum-Sreedharan's non-polytopal 3-sphere.

Incidentally, I believe this related problem is still open (if not, I'd like to know of its resolution):

> Does every triangulation of a genus 1 torus have a geometric realization (embedding) in $\mathbb{R^3}$?

For sufficiently large genus (I think 5?), there are non-realizable examples.

> **Comments:**
> **username_2**: Joseph, the link seems to be broken.  
> **username_1**: @username_2: Thanks; the page moved.  I've relinked it.  

---

