The distribution of graph imbeddings on topological surfaces

This thesis investigates what would commonly be called the distribution of graph imbeddings into topological surfaces, by which one actually means the distribution of the finite set of combinatorial equivalence classes of cellular imbeddings. Whereas the minimum genus and the maximum genus of graphs are already the subjects of an extensive literature, the beginning of a literature on the average genus of an individual graph is presently only in the preprint stage. Derived herein is a so-called Kuratowski-type theorem for average genus, that is, a characterization of all the graphs with average genus less than one. By reconsidering Whitney's classic result on 2-connectivity from the new viewpoint of "linear synthesis" of graphs, we are able to obtain results with possible importance to isomorphism testing. First, only finitely many 3-connected or 2-connected simplical graphs can share a value of average genus. Second, the set of values of average genus for the classes of 3-connected or 2-connected simplicial graphs have no limit points. Also, explicit formulas are derived for the crosscap number distribution of several classes of graphs, the first known computations of the non-orientable case for infinite classes.