4-connected Planar Graphs are Inscribable
M.B. Dillencourt, University of California;W.D. Smith, NEC
12/10/91
ABSTRACT:
This is part of a series of TMs exploring graph-theoretic consequences of the
recent Rivin-Smith characterization of ``inscribable graphs.'' The purpose
of the present TM is to prove that all ``4-connected planar'' graphs are
inscribable. (A graph is a set of ``vertices,'' some pairs of which are joined
by ``edges.'' A graph is ``inscribable'' if it is the 1-skeleton of a convex
polyhedron inscribed in a sphere. A graph is ``planar'' if it may be drawn in
the plane with edges being represented by Jordan curves, and with no
edge-crossings. A graph is ``4-connected'' if it cannot be disconnected by
the removal of fewer than 4 vertices.) This TM will later be incorporated
into a joint publication by Dillencourt and Smith on ``Graph-Theoretic
Properties of Inscribable Graphs.'' The other half, which was written by
Dillencourt, is mostly on {\it trivalent} inscribable graphs. An ``extended
abstract'' of it was submitted to the ACM Computational Geometry
Conference, and should also appear as another NEC TM.
KEYWORDS:
INSCRIBABLE, CIRCUMSCRIBABLE, HAMILTONIAN, PLANAR
GRAPHS, POLYHEDRA