Planar graphs and Steinitz's theorem

One way of representing a 3-connected planar graph is as the 1-skeleton (i.e the vertices and edges) of a convex polytope. A neat way of visualizing this is by shining a light above one face of the polytope and looking at the shadow formed (see David Eppstein's beautiful picture). Steinitz's theorem says that in fact this is an exact characterization: convex polytopes are exactly those polytopes whose edge graphs are planar.

There are different ways this convex polytope can be constructed, and it can be made to take various forms. Oded Schramm, in a paper titled 'How to Cage an Egg' that should go on my list of cool paper titles, shows that given any convex polytope and any smooth strictly convex body in R³, there is a combinatorially equivalent convex polytope that can be embedded such that each edge touches the surface of the convex body (in particular, we could use a sphere). There are many other results of this flavor; Ziegler's book on polytopes has more, as does Jeff Erickson's page on constructing convex polytopes.

But the question that puzzles me is this. Steinitz's original proof yields a polytope with rational coordinates (and thus integer coordinates). However, the values involved are doubly exponential in the number of vertices. Subsequently, Onn and Sturmfels showed that a "mere" single exponential suffices (specifically, their bound is of the form n¹⁶⁹ⁿ³). It is open whether a polynomial (quadratic?) bound suffices.

Enter László Lovász, and the Colin de Verdière number of a graph. It would take too long to explain this number here (van der Holst, Lovász and Schrijver have a survey); basically it's the second eigenvalue of an associated matrix and has the interesting property of correlating with planarity, outer planarity and linkless embeddability for different values of the number. Lovász and Schrijver showed that a Colin de Verdière matrix (a matrix achieving the number) can be used to embed a planar graph on the sphere (using the geodesics as edges) so that each face is the intersection of the sphere with a convex polyhedral cone.

Lovász, in later work, then showed that this matrix can be used to generate a Steinitz representation of a planar graph as well. Which finally brings me to the question I wanted to ask:

Is there anything known about the size complexity of the Steinitz representation that the Lovász construction generates ? My references for the size of the Steinitz representation are quite old (the Ziegler book and the Onn/Sturmfels paper) and maybe there is a known polynomial upper bound ? If not, could the Lovász construction be a good candidate ?

It's worth noting that for higher dimensional polytopes, it is known that a doubly exponential representation is the best one can hope for. As often happens, the 3D case is special in this regard.

Update: David Eppstein points out that Chrobak, Goodrich and Tamassia showed a bound of O(n log n) bits per vertex (instead of n³) in SoCG 1996 (they apparently weren't aware of the Onn/Sturmfels result though).

Update II: Isn't the internet great ! Another commenter points out a monograph by
Jürgen Richter-Gebert on the realization of polytopes. Here's where things get interesting. The monograph (dated 1996) has two Steinitz realizations. One is a general bound that uses 18n² bits per vertex (better than Onn/Sturmfels) and the other, which applies to simplicial polytopes (specifically realizations of the 3-connected planar graphs that Chrobak et al consider), uses linear number of bits per vertex (something like n * log 43) ! So this work improves on the Chrobak et al work, while being roughly concurrent (Both author groups are unaware of each other's work).

Of course all of this predates the Lovász construction, so the possibility of further improvement still exists.

Categories:

• graphs