Academic Commons

Theses Doctoral

Methods for Computing Genus Distribution Using Double-Rooted Graphs

Khan, Imran Farid

This thesis develops general methods for computing the genus distribution of various types of graph families, using the concept of double-rooted graphs, which are defined to be graphs with two vertices designated as roots (the methods developed in this dissertation are limited to the cases where one of the two roots is restricted to be of valence two). I define partials and productions, and I use these as follows: (i) to compute the genus distribution of a graph obtained through the vertex amalgamation of a double-rooted graph with a single-rooted graph, and to show how these can be used to obtain recurrences for the genus distribution of iteratively growing infinite graph families. (ii) to compute the genus distribution of a graph obtained (a) through the operation of self-vertex-amalgamation on a double-rooted graph, and (b) through the operation of edge-addition on a double-rooted graph, and finally (iii) to develop a method to compute the recurrences for the genus distribution of the graph family generated by the Cartesian product of P3 and Pn.

Files

  • thumnail for Khan_columbia_0054D_10610.pdf Khan_columbia_0054D_10610.pdf application/x-pdf 885 KB Download File

More About This Work

Academic Units
Computer Science
Thesis Advisors
Gross, Jonathan L.
Degree
Ph.D., Columbia University
Published Here
April 5, 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.