Hierarchy for imbedding-distribution invariants of a graph

Most existing papers about graph imbeddings ale concerned with the determination of minimum genus, and various others have been devoted to maximum genus or to highly symmetric imbeddings of special graphs. An entirely dirrerent viewpoint is now presented, in which one seeks distributional information about the huge family of all cellular imbeddings of a graph into all closed surfaces, instea ~ of focusing on just one imbedding or on the existence of imbeddings into just one surface. The distribution of imbeddings admits a hierarchically ordered class of computable invariants, each of which partitions the set of all graphs into much finer subcategories than the subcategories corresponding to minimum genus or to any other single imbedding surface. Quite low in this hierarchy are invariants such as the average genus, taken over all cellular imbeddings, and the average region size, where ·region size · means the number of edge traversals required to complete Po tour of a region boundary. Further up in the hierarchy is the multiset of duals of a graph. At an intermediate level are the ·imbedding polynomials·. The hierarchy is explored, and several specific calculations of the values of some of the invariants are provided. The main results are concerned with the amount of work needed to derive one invariant from another, when possible, and with principles for computing the algebraic erreet of adding an edge or of forming a composition of two graphs. lDeparlmen & or Comput.er Science. Columbia Univenhy. New York. New York 10027. The resulh herein were obtained while the rm & au&hor wu a viaiUne: r"",,,.l~y member in t!.le Depanmen & or Comput.er Science d Carne~e--Mellon Univel'llity. Support.ed by ONR con&rae & NOO~~~'!~.()':OS