Deutsch Intern
Chair of Computer Science I - Algorithms and Complexity

Theses

We offer topics for bachlor and master theses as well as for master practica. The topics usually align with our research interests. When assigning topics, it is important for us that, on the one hand, they fit to the student and, on the other hand, that they are interesting for us from a research perspective. Therefore, we do not maintain a list of fixed topics. If you are interested in doing your thesis with us, please contact Alexander Wolff (for algorithms), Christian Glaßer (for complexity theory), or Marie Schmidt (for optimization), or any of our postdocs or PhD students. In a short meeting, we can then discuss your interests and find a suitable topic together. Before you start writing your thesis with us, you should have taken one of our seminars in oder to familiarize yourself with scientific work in our community. Alternatively, you can take one of our seminars, while you write your thesis with us.

To help you start writing your thesis, we offer a LaTeX-template together with some guides and tips. Please read them carefully. After a short familiarization phase, we will jointly register your thesis at the examination office (which has forms for bachelor theses and master theses).

Completed Theses

2024

2023

  • Johannes Zink: Algorithms for Drawing Graphs and Polylines with Straight-Line Segments (Dissertation)
    [unibib]

  • Duy-Khang Tran: Efficiently computing alternative minimum-bend orthogonal representations (Bachelor Thesis, in German)
    [pdf]

  • Cato Sacher: Complexity of arithmetic Circuits over natural numbers with addition, multiplication and division (Master Thesis, in German)
    [pdf]

  • Sebastian Körner: Compaction of Orthogonal Graph Drawings via Complex Cuts (Bachelor Thesis, in German)
    [pdf]

  • Pascal Schlereth: Complexity of arithmetic circuits over natural numbers with minimum and maximum (Master Thesis)
    [pdf]

  • David Dingel: Separation of the Relativized Conjectures SAT and TFNP (Bachelor Thesis, in German)
    [pdf]

  • Leo Puppe: Comparison of a schedule-based and an on-demand minibus line through simulation (Bachelor Thesis, in German)
    [pdf]

  • Andreas Maier: Reducing cancelled lessons by improving timetables with stochastic optimization (Bachelor Thesis)
    [pdf]

  • Nicolai Noah Krapohl: Shelf Restocking via TSP with Precedence Constraints (Master Thesis)

2022

  • Tim Gerlach: Variations of the Generalized Minimum Manhattan Network Problem (Bachelor Thesis)
    [pdf]

  • Aaron Neugebauer: Rainbow Matchings in Color-Spanned Graphs (Bachelor Thesis)
    [pdf]

  • Joshua Geis: Upward-Planar Drawings of Outerpaths with Three Slopes (Bachelor Thesis, in German)
    [pdf]

  • Arash Torabi Goodarzi: Crossing Reduction in Circular Layouts under Grouping Constraints (Bachelor Thesis)
    [pdf]

  • Tobias Schopka: Generalisierung orthogonal gezeichneter Pläne (Bachelor Thesis, in German)
    [pdf]

  • Florian Timpf: Sufficient and Necessary Conditions for the Feasibility of a Tangle (Bachelor Thesis, in German)
    [pdf]

  • Lorena Stäblein: Morphing Special Planar Graphs with Cycles on Small Grids in Three Dimensions (Bachelor Thesis)

  • Vasil Alistarov: Computing Tangles Using a SAT Solver (Project Report)
    [pdf]

  • Jonas Barth: Clear Drawing of Literary Networks Using the Sugiyama Framework (Bachelor Thesis, in German)
    [pdf]

  • Tim Herrmann: Storyline Visualizations for Scientific Collaboration Graphs (Master Thesis, in German)
    [pdf], [slides|pdf]

  • León Lang: Regular Outer Obstacle Representations of Small Planar Graphs (Bachelor Thesis, in German)
    [pdf]

  • Florian Mittelstädt: About Coloring of Generalized Interval Graphs (Master Thesis, in German)
    [pdf]

  • Marie Diana Sieper: Parameterized Complexity of Constrained and Partial Level Planarity (Master Thesis)
    [pdf]

  • Ina Goeßmann: On the Segment Number of 4-Regular Planar Graphs (Master Thesis)
    [pdf]

2021

  • David Dingel: Labeling Problem in hierarchically layered graphs (Project Report, in German)
    [pdf]

  • Martin Herold: Hierarchical Clustering (Project Report)
    [pdf]

  • Michael Leeming: The Local Edge Length Ratio - Complexity and Greedy Algorithm (Master Thesis, in German)
    [pdf]

  • Tim Janiak: Interactive Design of Metro Maps (Master Thesis)
    [pdf]

  • Alexander Erhardt: The Weak Line Cover Number in 3D for Restricted Graph Classes (Master Thesis, in German)
    [pdf]

  • Peter Markfelder: Extension of Partial Contact Representations (Master Thesis)
    [pdf]

  • Tim Hegemann: Aligning Polylines to Line Features on Bitmap Images of Historical Maps (Master Thesis)
    [pdf]

  • Annika Förster: Boundary Labeling with Polygon Obstacles (Master Thesis)
    [pdf]

  • Alexander Zaft: Map Labelling with Phylogenetic Tree Constraints (Project Report)
    [pdf]

  • Peter Markfelfer: On Block Crossing Optimal Drawings of Storylines (Project Report)
    [pdf]

  • Jan Sauer: The Complexity of Drawing Chord-Link Diagrams (Bachelor Thesis, in German)
    [pdf]

  • Samuel Wolf: Infrastructure Planning via Algorithms for the Weighted Region Problem (Bachelor Thesis)
    [pdf]

  • Paul Schwind: Strongly monotone drawings with bends of planar graphs (Bachelor Thesis, in German)

  • Markus Heigl: Segment number of 4-regular, triconnected, planar graphs (Bachelor Thesis)

  • Lukas Brückner: Orthogonal Drawing as a Coloring Problem in Perfect Graphs (Bachelor Thesis, in German)
    [pdf]

  • Dominique Bau: Algorithm Engineering for a Geometric Set Cover Problem (Master Thesis, in German)
    [pdf]

  • Christian Goldschmied: 1-Obstacle Visibility Representation of Cubic Graphs (Bachelor Thesis, in German)
    [pdf]

  • Leon Füger: A Local Search Algorithm for Coordinated Motion Planning (Project Report)
    [pdf]

  • Moritz Niederer: An Algorithm for the Joint Visualization of Species and Gene Trees (Bachelor Thesis, in German)
    [pdf]

  • Titus Dose: Balance Problems for Integer Circuits and Separations of Relativized Conjectures on Incompleteness in Promise Classes (Dissertation)
    [pdf]

2020

  • Benedikt Riegel: Approximation Algorithms for Variants of the k-Median Problem (Bachelor Thesis)
    [pdf]

  • Lukas Garbe: Segment Number of Maximal Outerplanar Graphs (Teacher's Thesis)
    [pdf]

  • Jakob Geiger: Cluster-Minimization in Geometric Graphs (Master Thesis, in German)
    [pdf], [slides]

  • Jakob Geiger: Geometric Clustering (Project Report, in German)
    [pdf]

  • Julian Walter: A Variant of Sugiyama's Algorithm for Undirected Graphs with Port Constraints (Master Thesis, in German)
    [pdf], [slides|pdf], [slides|pptx]

  • Felix Klesen: Algorithms for Automated Floor Planning (Master Thesis)
    [pdf]

  • Leon Füger: Drawing Hypergraphs in 3D via the Incidence Poset  (Bachelor Thesis, in German)
    [pdf]

  • Sebastian Müller: Comparison of Drawing Styles for Planar Graphs  (Bachelor Thesis, in German)
    [pdf]

  • Dominique Bau: Interactive Visualization of RDF Graphs (Project report, in German)
    [pdf]

  • David Fischer: Implementing Algorithms for the Minimum Convex Partition Problem (Project report, in German)
    [pdf]

  • Michael May: An Algorithm for Optimizing an Areal Partition (Bachelor Thesis, in German)
    [pdf]

  • Myroslav Kryven: Optimizing Crossings in Circular-Arc Drawings and Circular Layouts (Dissertation)
    [unibib]

  • Andre Löffler: Constrained Graph Layouts: Vertices on the Outer Face and on the Integer Grid (Dissertation)
    [unibib]

2019

  • Michael Kreuzer: Interactive Visualization and Comparison of Graphs in Virtual Reality (Bachelor Thesis)
    [pdf], [poster]

  • Chris Rettner: Flipped Bitonic st-Orderings of Upward Plane Graphs (Bachelor Thesis)
    [pdf]

  • Olga Frost: A Knowledge-based Software System for Time and Human Resource Management in Prolog (Bachelor Thesis)

  • Julian Walter: Partial Zooming in Large Network Graphs (Project report, in German)
    [pdf], [slides]

2018

  • Benedikt Budig: Extracting Spatial Information from Historical Maps: Algorithms and Interaction (Dissertation)
    [unibib]

  • Fabian Feitsch: Public Transportation in Rural Areas: The Clustered Dial-a-Ride Problem (Master Thesis)
    [pdf], [slides]

  • Krzysztof Fleszar: Network-Design-Problems in Graphs and on the Plane (Dissertation)
    [pdf], [slides]

  • Marie Diana Sieper: Approximation Algorithms for Solving the Quality-of-Service Multicast Tree Problem (Bachelor Thesis)
    [pdf]

  • Maike Rösch: Approximation Algorithms for Set-Cover Problems with Rectangles (Bachelor Thesis, in German)
    [pdf], [poster]

  • Julia Kübert: Attempto Controlled English für Amazon Alexa (Bachelor Thesis, in German)
    [pdf]

  • Sandra Lederer: Analyse und Optimierung verschiedener Algorithmen zur Synchronisation von SQL-Datenbanken (Master Thesis, in German)
    [pdf]

2017

  • Dongliang Peng: An Optimization-Based Approach For Continuous Map Generalization (PhD Thesis)
    [pdf], [slides]

  • Johannes Zink: 1-Planar RAC Drawings with Bends (Masterarbeit)
    [pdf]

  • Jonas Jung: Recognition of Rivers in Areal Photographs through Machine Learning [in German] (Bachelor Thesis)
    [pdf]

  • Jona Kalkus: An Interactive Visualisation for Definite Clause Grammars (Master Thesis)
    [pdf]

  • Stefan Bodenlos: Integration of Prolog and ClioPatria in Python (Master Thesis)
    [pdf]

  • Johannes Blum: Scalability of Route Planning Techniques and Empirical Growth of Road Network Parameters (Master Thesis)
    [pdf]

  • Felix Klesen: Recognition of Rivers in Areal Photographs [in German] (Bachelor Thesis)
    [pdf]

  • Julian Walter: Rotation and scale invariant template matching for historical maps (Bachelor Thesis)
    [pdf], [poster]

  • Joachim Spoerhase: Approximation Algorithms for Network Design and Location Planning (Habilitation Thesis)
    [pdf], [slides]

  • Ludwig Ostermayer:  Integration of Prolog and Java with the Connector Architecture CAPJa (Dissertation)
    [pdf]

  • Bernhard Häussner: Visual Comparison of Business Process Flowcharts (Master Thesis)
    [pdf], [slides]

  • Peter Markfelder: Optimale Zeichnungen von Storylines mit Blockkreuzungen (Bachelorarbeit)
    [pdf]

  • Mirco Lukas: Integration of the Connector Architecture CAPJa in a Development Environment (Master Thesis)
    [pdf]

2016

  • Eike-Christian Weiss: Multi-Paradigm Programming in Java and Prolog for Games Engineering (Bachelor Thesis)

  • Andre Löffler: Snapping Graph Drawings to the Grid (Master Thesis)
    [pdf]

  • Thomas Handwerker: Testing Source Code with the Logic Programming Language Prolog (Master Thesis)
    [pdf], [slides]

  • Martin Becker: String Matching von historischen Toponymen (Bachelor Thesis)
    [pdf]

  • Leon Sering: A Combinatorial Upper Bound on the Length of Twang Cascades (Master Thesis)
    [pdf]

  • Fabian Feitsch: From Many User-Contributed Polygons to One Polygon Consensus (Bachelor Thesis)
    [pdf], [slides]

  • Ursula Scherm: Covering Vertices and Edges of Graphs with the Minimum Number of Lines [in German] (Bachelor Thesis)
    [pdf]

  • Johannes Zink: Drawing Circuit Diagrams Using KLayLayered from KIELER [in German] (Master Project)
    [pdf]

2015

  • Wadim Reimche: Slanted Orthogonal Drawings of Graphs [in German] (Master Thesis)
    [pdf]

  • Titus Dose: Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers [in German] (Master Thesis)
    [pdf]

  • Johannes Zink: Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition [in German] (Bachelor Thesis)
    [pdf], [slides]

  • Adrian Loy: Optimization of Cutting Schedules [in German] (Bachelor Thesis)
    [pdf], [slides]

  • Philipp Kindermann: Angular Schematization in Graph Drawing (PhD Thesis)
    [pdf], [slides]

  • Nadine Schwartges: Dynamic Label Placement in Practice (PhD Thesis)
    [pdf], [slides]

  • Matthias Neumann: Drawing of Networks Considering Edge Lengths [in German] (Bachelor Thesis)
    [pdf], [slides]

  • Maximilian Witek: Multiobjective Traveling Salesman Problems and Redundancy of Complete Sets (PhD Thesis)
    [pdf]

  • Larissa Michler: Stabilität vollständiger Mengen (Bachelor Thesis)

  • Sandra Lederer : Multiparadigmen-Programmierung mit Java und Prolog (Bachelor Thesis)

  • Lukas Beckmann: Analyse von Umkehrpunkten auf GPS-Trajektorien unter Verwendung der Fréchet-Distanz (Bachelor Thesis)
    [pdf], [slides]

2014

  • Lukas Bott: Optimization and Automatization in Commissioning (Bachelor Thesis)

  • Lorenz Reinhart: Rectangle Representations of Weighted Outerplanar Graphs [in German] (Bachelor Thesis)
    [pdf], [slides]

  • Fabian Lipp: Boundary Labeling for Annotations in Texts (Master Thesis)
    [pdf], [slides]

  • Martin Fink: Crossings, Curves, and Constraints in Graph Drawing (PhD Thesis)
    [pdf], [slides]

  • Bernhard Häussner: Implementation of an Algorithm for Smooth Orthogonal Drawings of Planar Graphs [in German] (Bachelor Thesis)
    [pdf], [slides]

  • Maximilian Aulbach: Visualizing Weighted Graphs in Restricted Area [in German] (Bachelor Thesis)
    [pdf], [slides]

  • Magnus Lechner: Concentric Metro Maps [in German] (Bachelor Thesis)
    [pdf], [slides]

  • Benedikt Budig: Algorithmic Analysis of Historical Maps (Master Thesis)
    [pdf], [slides]

  • Dieter Lutz: Realtime Linear Cartograms using Least-Squares Optimisation (Master Thesis)
    [pdf]

  • Agota Lovas: On F-Automata and Equivalence Classes of Boolean Functions (Diploma Thesis)

  • Uwe Herkert: Entwicklung eines Übersetzers für While-Programme (Bachelor Thesis)

  • Geng Sun: Development of a DSL Editor for Simplifying Rule Creation in Drools (Master Thesis)

  • Mirco Lukas: Erweiterung der Dialektdatenbank BayDat um eine Kartierungsfunktion (Bachelor Thesis)

  • Xiaofen Liu: Abgleich von SQL–Tabellen und CSV–Dateien mit Hilfe von Embedded SQL (Bachelor Thesis)

2013

  • Hagen Schwaß: Symmetry detection in building outlines [in German] (Master Thesis)
    [pdf], [slides]

  • Julian Schuhmann: Drawing Calculation Graphs [in German] (Master Thesis)
    [pdf], [slides]

  • Christian Volkert: Merging Curves for Improving curvilinear Metro Maps [in German] (Bachelor Thesis)

  • Leon Sering: Grapheneinbettung mit vorgegebener Kantenlänge (Bachelor Thesis)

  • Titus Dose: Effiziente Reduktionen zwischen NP-vollständigen Problemen (Bachelor Thesis)

  • Torbjørn Cunis: Decidability of Differences of Level 3/2 Languages of the Straubing Therien Hierarchy (Bachelor Thesis)

  • Johannes Blum: Transformation of Register Machine Programs (Bachelor Thesis)

2012

  • Sergiy Pakholchak: Dynamic Labeling of Streets [in German] (Bachelor Thesis)
    [pdf], [slides]

  • Benjamin Morgan: Placing Street Labels in Interactive Navigational Maps (Bachelor Thesis)
    [pdf], [slides]

  • Krzysztof Fleszar: Generalized Minimum Manhattan Networks (Master Thesis)
    [pdf], [slides]

  • Ilia Belozerov: Packing Algorithms for Boxes [in German] (Bachelor Thesis)
    [pdf], [slides]

  • Fabian Lipp: Computing the Flip Distance of Triangulations (Bachelor Thesis)
    [pdf], [slides]

  • Benedikt Budig: An algorithm for map matching on incomplete road databases (Bachelor Thesis)
    [pdf], [slides]

  • Nils Wisiol: Simulation of Proof Systems (Bachelor Thesis)

  • Christian Reitwiessner: Multiobjective Optimization and Language Equations (PhD Thesis)

  • Florian Stefan: XXUL - Deklarative GUI-Entwicklung mit XPCE (Diploma Thesis)

  • Esther Fee Feichtner: Musikanalyse mit MusicXML-Daten - Implementierung in Prolog (Diploma Thesis)

2011

  • Philipp Kindermann: Tour Planing with Time Windows for Several Vehicles [in German] (Diploma Thesis)
    [pdf]

  • Julian Schuhmann: Automated Drawing of Metro Maps using Bézier Curves [in German] (Bachelor Thesis)
    [pdf], [slides]

  • Nadine Schwartges : Approximation Algorithms for the Directed Maximum Leaf Spanning Tree Problem [in German] (Diploma Thesis)
    [pdf]

  • Christian Moldovan: Aggregation in Node-Partitioned Graphs [in German] (Bachelor Thesis)

  • Oleksandr Kovalchuk: Deklarative Methoden zur Analyse von metabolischen Pathways (Diploma Thesis)

2010

  • Johannes Schnappauf: Detection of Symmetries in Polygons [in German] (Bachelor Thesis)

  • Joachim Spoerhase: Competitive and Voting Location (PhD Thesis)
    [pdf]

2009

  • Martin Fink: Centrality Measures in Complex Networks based on Shortest Paths [in German] (Diploma Thesis)
    [pdf]

  • Martin Knauer: Spannende Bäume unter Beschränkung der Blätterzahl - Approximative Verfahren (Diploma Thesis)

  • Julian Einwag: Approximation und Visualisierung mehrkriterieller Optimierungsprobleme (Diploma Thesis)