Bachelor-/Masterarbeiten, Hiwi-Stellen
Offene Hiwi-Stellen
.
Theses
Fill out this form if you are / might be interested in writing your thesis with us. We will contact you with concrete topics then. Note, however, that we might not be able to supervise everyone who is interested.
What to expect
All our topics are of theoretical nature and are located somewhere between structural and algorithmic graph theory / combinatorics. Usually, the largest part of a thesis in our group is devoted to your own research, i.e. proving something, with varying shares of surveying the state of the art and writing. We have weekly to biweekly meetings to support you and give feedback on your progress and write-up. In addition to the final presentation, you will introduce yourself in our seminar with a 5-minute talk on your goals after a few weeks.
Topics
Here are some topics we are interested in and most of the theses we supervise are related to them. Feel free to contact us with any questions or fill in the application form above.
Linear Layouts
Linear layouts are a tool to investigate the structure of (ordered) graphs by partitioning the edge set. For instance, a stack layout (also called book embedding) asks for a vertex ordering and a partition of the edges such that no two edges of the same part cross with respect to the vertex ordering. Other variants, like queue layouts, alter the conditions that each part needs to satisfy or take a partial or linear order as part of the input. A thesis in this field might investigate some variant(s) of linear layouts, starting with small examples and then prove upper or lower bounds on larger graph classes or relate different variants to each other.
Contact: Laura Merker
Product Structure
Product Structure is a tool to decompose complex graphs into simpler ones. For instance, every planar graph can be decomposed into a path and a tree-like graph. This is often useful for investigating various graph parameters (e.g. in the context of linear layouts) but also has algorithmic consequences. We have both algorithmic and structural questions concerning product structure, e.g. investigating which graph classes admit product structure or exploit the structure to prove bounds on different graph parameters and develop efficient algorithms.
Contact: Laura Merker
Coverings of Graphs
We seek to disassemble a graph G into simpler, manageable pieces by considering covers, that is subgraphs of G whose union covers all edges of G. These subgraphs are required to belong to a given graph class, which is usually simple in structure. Examples include forests and planar graphs. The minimum number of subforests of G which cover all edges of G is called the arboricity of G. For example, every planar graph has arboricity at most 3.The thickness of G corresponds to the minimum number of subgraphs required to cover G if all these subgraphs have to be planar. We investigate such covering numbers for different classes of subgraphs.
Contact: Miriam Goetze