Graph-theoretical conditions for inscribability and Delaunay realizability Original Research Article

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.