1989 Reports

Stratified Graphs

Gross, Jonathan L.; Tucker, Thomas W.

Two imbeddings of a graph G are considered to be adjacent if the second can be obtained from the first by moving one or both ends of a single edge within its or their respective rotations. Thus, the collection of imbeddings of G may be regarded as a "stratified graph", denoted SG. The induced subgraph of SG on the set of imbeddings into the surface of genus k is called the "kth stratum", and one may observe that the sequence of stratum sizes is precisely the genus distribution for the graph G. It is proved that the stratified graph is a complete isomorphism invariant for the category of graphs whose minimum valence is at least three and that the spanning subgraph of SG corresponding to moving only one edge-end is a cartesian product of graphs whose underlying isomorphism types depend only on the valence sequence for G.