Donald Bren School of Information and Computer Sciences

We present new graph-theoretical conditions for inscribable polyhedra and Delaunay triangulations. We establish several sufficient conditions of the following general form: if a polyhedron has a sufficiently rich collection of Hamiltonian subgraphs, then it is inscribable. These results have several consequences:

All 4-connected polyhedra are inscribable.

All simplical polyhedra in which all vertex degrees are between 4 and 6, inclusive, are inscribable.

All triangulations without chords or nonfacial triangles are realizable as Delaunay triangulations.

We also strengthen some earlier results about matchings in inscribable polyhedra. Specifically, we show that any nonbipartite inscribable polyhedron has a perfect matching containing any specified edge, and that any bipartite inscribable polyhedron has a perfect matching containing any two specified disjoint edges. We give examples showing that these results are best possible.