Graduate Student Seminar
Thu, 25 February, 2016
8:00pm
Title: Finding the maximum genus of a graph – Topic in Topological graph theory
Speaker: Lara El-Sherif
Abstract: For any graph G and an orientable surface Sg (a surface of genus g), whether G can be cellularly embedded in Sg creates an interesting problem for many topological graph theorists. The “genus range” of a graph G, denoted GR(G) is defined to be the set of numbers g such that the graph G can be cellularly embedded in surface Sg. We call the minimum number g in the genus range, the “minimum genus” of G and the largest number in the range, the “maximum genus” respectively. Whereas the study of minimum genus dates back into the 19th century, interest in maximum genus began in the 1970’s. The main contributors to the theory behind finding the maximum genus of a graph are Xuong and Nebesky, among others. In this talk we will introduce the methods used by both Xuong and Nebesky in solving the maximum genus problem. We will also talk about the polynomial time algorithms available for finding a maximum genus embedding of a graph and the problems that lie in those algorithms.
Note: The Graduate Student Seminar is mandatory
Note: The Graduate Student Seminar is mandatory