Research Topics

The field of graph drawing studies the question how to draw a given graph in the best possible way. There are various design criteria as to what is meant by “good” in this context. Among other things, one wants to allow as few edge crossings as possible. Also small angles and (after normalization) small edge lengths should be avoided. In general, it is very difficult to solve these problems optimally. However, there are a number of graph classes for which good drawings can be efficiently computed. The large number of relevant graph classes, different drawing styles and the possible combinations of design criteria create a variety of interesting questions.

In the field of countable combinatorics, we investigate how many structures can be contained in a graph (or can be realized on a set of points). Upper and lower bounds for the maximum number are usually of interest here. Typical structures that are considered are (crossing-free) cycles, spanning trees, matchings, or forests. Knowing the bounds is often from interest when, due to the lack of an efficient algorithm, it is necessary to search through the entire solution space of a problem (for example Hamilton cycled in the TSP-problem). In this case, one can use the bounds for the maximum number to obtain statements about the worst-case running time.