A linear-time algorithm for testing the inscribability of trivalent polyhedra
Michael B. Dillencourt, Warren D. Smith · 1992
We present an algorithm for testing the inscribability of a trivalent polyhedron, or, equivalently, testing the circumscribability of a simplicial polyhedron. Our algorithm runs in linear time, using only low-precision integer arithmetic. The algorithm is based on a purely combinatorial characterization of inscribable trivalent polyhedra.