8
$\begingroup$

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}]

enter image description here

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] &)]

enter image description here

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

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:

Éric COLIN de VERDIÈRE's course notes PDF download.

          Fig.1
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)$."

Improve this answer
$\endgroup$
5
  • $\begingroup$ Slightly off-topic, but can you verify whether this sentence of the Wikipedia article is incorrect? "For a Tutte embedding, assigning attractive forces of equal magnitudes to all edges makes the forces cancel at all interior vertices..." But for the vertex to be the barycenter of its neighbours, the forces have to have magnitude proportional to the length of each edge instead. $\endgroup$ Commented Jul 13, 2014 at 17:03
  • $\begingroup$ @RahulNarain: Here's a quote from the paper I cited: "This [Tutte's] theorem maintains that a planar graph may be easily drawn in the plane by embedding the graph boundary on a strictly convex polygon and solving a linear system for each of the two coordinates of the interior vertices. The linear system forces each interior vertex to lie at the centroid of its neighbors. Tutte proved that the result is indeed a straight line plane drawing, and, furthermore, the faces are non-degenerate, bounding convex regions in the plane." $\endgroup$ Commented Jul 13, 2014 at 17:31
  • $\begingroup$ This sounds interesting, but it also sounds more like mathematics than Mathematica. The task of implementing this theorem as a functioning algorithm seems daunting indeed. Is there any concrete work that has been done on turning this idea into a computer program? $\endgroup$ Commented Jul 13, 2014 at 23:30
  • $\begingroup$ @limulus: I don't think it is that difficult to express the linear equations that each vertex should sit at the average of its neighbors. So the challenge is to take a graph as input, convert it to these linear equations, and then solve them. I did this once in C++ long ago when I had far fewer tools than are available in Mathematica today. $\endgroup$ Commented Jul 14, 2014 at 22:27
  • 1
    $\begingroup$ 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 $\endgroup$ Commented May 8, 2019 at 16:19