(Logo)   IMADA
University of Southern Denmark IMADA - Department of Mathematics and Computer Science
   

COMPUTER SCIENCE COLLOQUIUM

Determining the Minimum Genus of a Graph.

Michal Kotrbcik
Department of Mathematics and Computer Science
University of Southern Denmark, Denmark

Tuesday, 01 December, 2015 at 14:15
IMADA's Seminar Room

ABSTRACT

For a long time, extensive computations had been part of topological graph theory, in particular in attempts to determine the genus of various graphs and graph families. In recent years, the area is experiencing a renewed interest, motivated partly by vast increase in the available computational resources, as well as by advances in theoretical computer science. This talk will be concerned with combinatorial and algorithmic aspects of embeddings of graphs into surfaces, focusing on the genus of a graph. (The (minimum) genus of a graph G is the smallest integer g such that G has an embedding into the orientable surface of genus g; the well-known example are planar graphs that are precisely the graphs with genus 0.) Despite their seemingly topological nature, graph embeddings can be described in purely combinatorial terms, making the problem in principle finite. However, the size of the solution space grows drastically with the number of vertices and their degree, for example, in one case we are interested in finding a small-genus embedding of a graph which has almost $10^{300}$ embeddings in total. In the first part of the talk I will survey basic properties of the problem and present (negative) results about the structure of the problem space and theoretical algorithms, none of which is, unfortunately, usable in practice. In the second part of the talk I will briefly present a novel metaheuristic and a SAT-ILP framework, indicate their usability what they reveal about the problem space of the relevant instances, and discuss other graph parameters living in the same problem space. Partly joint work with T. Pisanski, P. Schmidt, respectively S. Beyer, I. Hedtke, and M. Chimani.


SDU HOME | IMADA HOME | Previous Page
Daniel Merkle