Let us be given a topological graph $G$ on the unit sphere in $\mathbb{R}^3$ whose edges are minor arcs of great circles. We suppose that the graph is $3$-vertex-connected and that a pair of edges may only share a vertex incident to both edges.

We say that a polyhedron $P$ is a lifting of $G$ iff $G$ is obtained by radial projection of the edge-skeleton of $P$ onto the unit sphere.

My question is whether there is a simple criterion to check if a given spherical graph possesses a lifting. Moreover, I would like to compute that lifting (if it exists). (Computationally, I am interested in some spherical graphs with about $10$ to $20$ vertices)

The analogue planar question is classical and well-understood. That is, a planar graph, i.e., a graph with vertices in $\mathbb{R}^2$ and straight edges, can be lifted into a polyhedron, iff it is possible to find an equilibrium configuration of forces, see here.


This is one of the results of Lovasz' "Steinitz representations of polyhedra and the Colin de Verdière number".

The condition is similar to the equilibrium condition on the plane, only this time the sum of the forces at each vertex must not be zero but collinear with the radius-vector of the vertex: $$ \sum_j w_{ij}(p_i-p_j) = c_i p_i $$ Given a collection of weights $w_{ij}=w_{ji}$ satisfying the above condition, we can construct a dual polyhedron with faces $F_i$ orthogonal to the radius-vectors $p_i$. Namely, note that $$ \sum_j w_{ij} (p_i \times p_j) = p_i \times \sum_j w_{ij} p_j = 0 $$ Therefore for every $i$ the vectors $w_{ij} (p_i \times p_j)$ form a closed polygonal line in a plane orthogonal to $p_i$. This will be our face $F_i$. These faces can be fitted together to form a polyhedron. The polar dual of this polyhedron has the desired combinatorics, and its vertices are multiples of $p_i$.

If all weights $w_{ij}$ were positive, the resulting polyhedron is convex. Otherwise self-intersections can happen. Is this bad or good, depends on your situation.

| cite | improve this answer | |
  • $\begingroup$ Thank you for your reply. I looked through the paper, but I cannot find that result. Are you sure that it is in this paper? $\endgroup$ – gerw Oct 19 '16 at 17:20
  • $\begingroup$ Yes, it is in the paper, but it is not so easy to isolate the argument. I will add details in my answer. $\endgroup$ – Ivan Izmestiev Oct 19 '16 at 19:37
  • $\begingroup$ Thank you again for your changes! I still do not see how this is contained in the paper, but your answer is very clear. Just to be sure: do I get it correctly, that the existence of positive weights is equivalent to the existence of a convex lifting? $\endgroup$ – gerw Nov 8 '16 at 14:11
  • 1
    $\begingroup$ Yes, exactly. Positive weights correspond to dihedral angles smaller than $\pi$ (although there is no simple formula to express the angles in terms of weights). $\endgroup$ – Ivan Izmestiev Nov 11 '16 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.