How can we test inscribability (or equivalently circumscribability)? Igor Rivin and Warren Smith gave a method of transforming the problem into a linear program. To test circumscribability, one places weights between 0 and 1/2 on each edge of the polyhedron, so that the weights on any face add to exactly one and the weights on any nonfacial cycle add to more than one. If this can be done, the polyhedron can be circumscribed. The edge weights have the following interpretation: multiplying each weight by 2pi gives the angle the edge would take up if viewed from the tangent points on either adjacent face. Dually, one can inscribe a polyhedron if and only if one can assign weights so that each vertex's weights add to one and each nontrivial cut (set of edges that separates two subsets of vertices) adds to more than one. (The meaning of these weights is harder to describe for inscription, but it can be related to the dihedral angles in a related problem of finding "ideal polyhedra" in hyperbolic geometry.) The existence of such a weighting system can be tested by applying the ellipsoid method for linear programming. However, it remains an interesting question whether there exists a more direct combinatorial method to check inscribability or circumscribability.
We might have more of a chance of finding such a method if we restrict our attention to special classes of polyhedra. One interesting special class of polyhedra are the 4-regular ones, in which each vertex is adjacent to exactly four edges. Since these graphs are Eulerian (equivalently, their duals are bipartite), every cut has at least four edges. There is a natural candidate for a Rivin-Smith weighting on these graphs: just give every edge weight 1/4. This might fail to work, if there exists a four-edge cut. However, one can then modify the weights by adding +epsilon and -epsilon alternately along the edges of an even-length cycle in the graph; this preserves the correct weights at the vertices, but might improve the weight of a cut. It turns out that any one cut can be made to have weight greater than one by such a procedure, so we might hope that repeating this procedure gives a correct weighting showing that 4-regular polyhedra are always inscribable. The only problem might be that making one cut have a better weight always is balanced by making another cut have a worse weight, so that no correct weighting exists. Can this happen? Yes!
Mike Dillencourt and I formed the example above by replacing four of the vertices of a cube by gadgets derived from octahedra. To prove that this is not inscribable, we need to talk about a concept called "1-supertoughness". This has a scary name, but is actually a pretty simple concept: an n-vertex graph is 1-supertough if, whenever you remove some set of k vertices, the number of components you have left is at most k-1. The example above is not 1-supertough because, if you remove the four remaining unmodified cube vertices, you get four components. What does this have to do with inscribability? The weights on the removed vertices must be exactly one each, so the total weight of the edges between them and the rest of the graph must be exactly four. However, this means one of the four components must have weight at most one on the edges connecting it to the removed vertices, contradicting the assumption that a nontrivial cut has weight more than one. Therefore no weighting can exist and this polyhedron is not inscribable.
The following question remains open: is every 1-supertough 4-regular graph inscribable?
M. B. Dillencourt. Toughness and Delaunay triangulations. Discrete & Computational Geometry, vol. 5, no. 6, 1990, pp. 575-601.
M. B. Dillencourt and W. D. Smith. A linear-time algorithm for testing the inscribability of trivalent polyhedra. Proc. 8th ACM Symp. Computational Geometry, 1992, pp. 177-185. Int. J. Computational Geometry & Applications, vol. 5, 1995, pp. 21-36.
From the Geometry Junkyard,
computational
and recreational geometry.
David Eppstein,
Theory Group,
ICS,
UC Irvine.
Last update: .