# How to construct a polyhedron from its vertex graph?

Consider the graph given by

graph = Graph[{2 <-> 1, 3 <-> 1, 7 <-> 1, 5 <-> 1, 6 <-> 1, 3 <-> 2, 4 <-> 3,
4 <-> 7, 4 <-> 5, 7 <-> 5, 6 <-> 5, 2 <-> 6}] Via Steinitz's theorem, this is the vertex graph of a convex polyhedron:

KVertexConnectedGraphQ[graph, 3] && PlanarGraphQ[graph]
-> True


How can one construct that polyhedron (i.e. a spatial representation of it) from the graph? Embedding the graph in 3-space using GraphPlot3D comes close, but does not actually build a polyhedron as the side view reveals:

GraphPlot3D[graph, Boxed -> False,
EdgeRenderingFunction -> (Cylinder[#1, .05] &),
VertexRenderingFunction -> (Sphere[#1, .1] &)] (Note how the quadrilateral face is "bent".)

I have experimented with various embeddings such as "SpringEmbedding", "SpringElectricalEmbedding" etc. but none of them seem to produce a true polyhedron even from this simple graph. I am aware that the polyhedron representation of a polyhedral graph is not unique (maybe not even topologically unique(?)) but any embedding that is a polyhedron would suffice. The polyhedral graphs supplied in Mathematica's graph database all come with such embeddings, so I am confident this must be possible.

One way to approach this problem is through Tutte's spring embedding theorem. Pick one face as outer, embed the remaining graph in the planar region inside using Tutte's theorem, and then lift into 3D.

Note that there is in general a continuum of polyhedra all of which realize the same polyhedral graph.

This paper offers a new and simpler proof of Tutte's theorem. Perhaps it or its references could help.

Gortler, Steven J., Craig Gotsman, and Dylan Thurston. "Discrete one-forms on meshes and applications to 3D mesh parameterization." Computer Aided Geometric Design 23.2 (2006): 83-112. Elsevier link.

Here is perhaps a more direct source: Finally, here is a quote from the Wikipedia page: "...each interior vertex is at the average (or barycenter) of its neighbor's positions...The condition that a vertex $v$ be at the average of its neighbors' positions may be expressed as two linear equations, one for the $x$ coordinate of $v$ and another for the $y$ coordinate of $v$. For a graph with $n$ vertices, $h$ of which are on the outer face, this gives a system of $2(n − h)$ equations in $2n$ unknowns; however, fixing the positions of the vertices on the outer face reduces the number of unknowns to $2(n − h)$."
• The Tutte layout is available as GraphLayout -> "TutteEmbedding", or more flexibly, as IGLayoutTutte in the IGraph/M package. See some demos here: community.wolfram.com/groups/-/m/t/1678406 Furthermore, IGraph/M can compute the faces using IGFaces. But this is not sufficient to make a three-dimensional polyhedron. We need to go to 3D in such a way that all faces stay co-planar. That does not seem trivial ... Also related: mathoverflow.net/q/331038/8776 – Szabolcs May 8 '19 at 16:19