On the Enumeration of Inscribable Graphs

Warren D. Smith, NECI

Abstract

We explore the question of counting, and estimating the number and the
fraction of, inscribable graphs.  In particular we will concern
ourselves with the number of inscribable and circumscribable {\it
maximal planar graphs} (synonym: simplicial polyhedra) on $V$
vertices, or, dually, the number of circumscribable and inscribable
{\it trivalent} (synonyms: 3-regular, simple) polyhedra. For small $V$
we provide computer-generated tables.  Asymptotically for large $V$ we
will prove bounds showing that these graphs are exponentially
numerous, but, viewed as a fraction of all maximal planar graphs, they
are exponentially rare.

Many of our results are based on a lemma, the
``strong 0-1 law for maximal planar graphs,'' of independent interest.

This is part of a series of TMs exploring graph-theoretic consequences
of the recent Rivin-Smith characterization of ``inscribable graphs.''
(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, ``circumscribable'' if it is
the 1-skeleton of a convex polyhedron each face of which is tangent to
a common sphere.)  \end{Abstract}

   Keywords

Inscribable,
Circumscribable,
Enumeration,
Census,
Tutte,
Maximal planar graphs,
Strong 0-1 law,
Triangle-free simple polyhedra.