We present new graph-theoretical conditions for polyhedra of inscribable type 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 of inscribable type. These results have several consequences: β’ All 4-connected polyhedra are of inscribable type. β’ All simplicial polyhedra in which all vertex degrees are between 4 and 6, inclusive, are of inscribable type. β’ All triangulations without chords or nonfacial triangles are realizable as combinatorially equivalent Delaunay triangulations.
We also strengthen some earlier results about matchings in polyhedra of inscribable type. Specifically, we show that any nonbipartite polyhedron of inscribable type has a perfect matching containing any specified edge, and that any bipartite polyhedron of inscribable type has a perfect matching containing any two specified disjoint edges. We give examples showing that these results are best possible. * Corresponding author. The support of a UCI Faculty Research Grant is gratefully acknowledged. A polyhedron is of inscribable type if it has a combinatorially equivalent realization as the convex hull of a set of points on a sphere. This and other terms used in the introduction are defined in Section 2.