Research Topics

The field of graph drawing studies how to draw a given graph in the best possible way. There are various design criteria for what is considered “good” in this context. Among other things, one wants to allow as few edge crossings as possible. Small angles and (after normalization) small edge lengths should also 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 a graph can contain (or how many 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 of 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 cycles in the TSP). In this case, one can use the bounds for the maximum number to obtain statements about the worst-case running time.