Finding the Canonical Polyhedron associated with a 3-connected simple graphs.

Question

I am not a professional mathematician but I am a reasonably competent programmer and I am also no stranger mathematics, though I must say that my usual domain is closer to calculus and functions rather than graph theory and discrete mathematics. Nevertheless, for reasons of an unusual application on the intersection of computer sciences and the inorganic chemistry of coordination compounds of lanthanoid metals, I have acquired an interest in convex polyhedra.

I was led to believe that according to Steinitz's Theorem every 3D convex polyhedron corresponds to a 3-connected simple planar graph and vice-versa. So one way to obtain every 3D convex polyhedron with $N$ vertices is to systematically generate the associated 3-connected graphs.

Fortunately, someone else already did that for as far as $N=12$, which just so happens to be good enough for me. This leaves only the last part: How to turn the graphs into their associated polyhedra?

I understand that there must be a million ways of doing that since the graph carries no information about neither the lengths of the edges or the positions of the vertices, but I have given it some thought and I have realized that for my particular application in the domain of chemistry, It would be interesting to know about any method that could give me the canonical form of each polyhedron. Since they are convex, I was told, each of them must have a single canonical realization in 3D.

So my question is this: Is there a systematic way to generate a canonical polyhedron, given its associated 3-connected simple planar graph?

Answer 1

The key is the circle packing theorem of Koebe-Andreev-Thurston, which states that a graph such as you describe can be realized in such a way that you can draw a circle centered on every vertex in such a way that the circles are tangent if and only if the vertices are adjacent in the graph. It is easy to see that this is equivalent to the "tangent edges" conditions of the canonical polyhedron. The center of gravity condition is the way to make the embedding unique up to rotation.