Genus Distributions of Graphs Constructed Through Amalgamations
 Title:

Genus Distributions of Graphs Constructed Through Amalgamations
 Author(s):

Poshni, Mehvish Irfan
 Thesis Advisor(s):

Gross, Jonathan L.
 Date:

2012
 Type:

Dissertations
 Department(s):

Computer Science
Statistics
 Persistent URL:

http://hdl.handle.net/10022/AC:P:12989
 Notes:

Ph.D., Columbia University.
 Abstract:

Graphs are commonly represented as points in space connected by lines. The points in space are the vertices of the graph, and the lines joining them are the edges of the graph. A general definition of a graph is considered here, where multiple edges are allowed between two vertices and an edge is permitted to connect a vertex to itself. It is assumed that graphs are connected, i.e., any vertex in the graph is reachable from another distinct vertex either directly through an edge connecting them or by a path consisting of intermediate vertices and connecting edges. Under this visual representation, graphs can be drawn on various surfaces. The focus of my research is restricted to a class of surfaces that are characterized as compact connected orientable 2manifolds. The drawings of graphs on surfaces that are of primary interest follow certain prescribed rules. These are called 2cellular graph embeddings, or simply embeddings. A wellknown closed formula makes it easy to enumerate the total number of 2cellular embeddings for a given graph over all surfaces. A much harder task is to give a surfacewise breakdown of this number as a sequence of numbers that count the number of 2cellular embeddings of a graph for each orientable surface. This sequence of numbers for a graph is known as the genus distribution of a graph. Prior research on genus distributions of graphs has primarily focused on making calculations of genus distributions for specific families of graphs. These families of graphs have often been contrived, and the methods used for finding their genus distributions have not been general enough to extend to other graph families. The research I have undertaken aims at developing and using a general method that frames the problem of calculating genus distributions of large graphs in terms of a partitioning of the genus distributions of smaller graphs. To this end, I use various operations such as edgeamalgamation, selfedgeamalgamation, and vertexamalgamation to construct large graphs out of smaller graphs, by coupling their vertices and edges together in certain consistent ways. This method assumes that the partitioned genus distribution of the smaller graphs is known or is easily calculable by computer, for instance, by using the famous HeffterEdmonds algorithm. As an outcome of the techniques used, I obtain general recurrences and closedformulas that give genus distributions for infinitely many recursively specifiable graph families. I also give an easily understood method for finding nontrivial examples of distinct graphs having the same genus distribution. In addition to this, I describe an algorithm that computes the genus distributions for a family of graphs known as the 4regular outerplanar graphs.
 Subject(s):

Computer science
 Item views
 216
 Metadata:

text  xml
 Suggested Citation:
 Mehvish Irfan Poshni, 2012, Genus Distributions of Graphs Constructed Through Amalgamations, Columbia University Academic Commons, http://hdl.handle.net/10022/AC:P:12989.