Academic Commons

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.

Subjects

Files

More About This Work

Academic Units
Computer Science
Publisher
Department of Computer Science, Columbia University
Series
Columbia University Computer Science Technical Reports, CUCS-483-89
Published Here
January 17, 2012
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.