Graph-Theoretical Conditions for Inscribability and Delaunay Realizability

M.B. Dillencourt, University of California;W.D. Smith, NECI

12/23/92

  ABSTRACT:
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: 
\begin{itemize} 
\item All 4-connected polyhedra are inscribable. 
\item All simplicial polyhedra in which all vertex degrees are
between 4 and 6, inclusive, are inscribable. 
\item All triangulations without
chords or nonfacial triangles are realizable as Delaunay triangulations.
\end{itemize} 
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.

  KEYWORDS:
INSCRIBABLE GRAPHS OF POLYHEDRA, DELAUNAY
TRIANGULATION, HAMILTONIAN TOUR, PERFECT MATCHING,
TOUGHNESS