Application
You can apply to write your thesis at the Chair of Efficient Algorithms either by applying for a suggested topic (see current offerings below) or by applying with your own project proposal. In either case, please send your complete application, including (i) a short description of your motivation, (ii) your CV, (iii) your current transcript of record, and (iv) if you are interested in multiple suggested topics, a list of these topics in order of preference to application(at)algo.cit.tum.de. If you are applying with your own project, please attach a one- to two-page long project proposal, covering your research question, the state of the literature, your intended contribution, data sources, and methods.
| Topic | Type | Details |
| Tiling the Castle: Tiling a Polygonal Region with a Set of Given Rectangles | Research Project, Bachelor, Master | Motivated by a real-world problem, we seek an algorithm for tiling a polygon (forecourt of a hotel) with rectangles (stone slabs) from a given set of rectangles such that several objective functions are taken into account; among them: filling the area as much as possible, equal distribution of differently colored slabs, small and short gaps. |
| Using Game-Playing Reinforcement-Learning Frameworks for Graph Drawing Problems | Research Project, Bachelor, Master | On the Internet, there exist several reinforcement-learning frameworks for (board) games: one formulates the rules of the game and a reward function in the language of the framework. Then, in a training phase, the reinforcement-learning agent figures out a good strategy to maximize the reward. We are interested in formulating graph-drawing problems as rules + reward functions in these frameworks and test how well this works and which potentials for improvement exist. An example for such a graph drawing problem is the following. Given a graph and a grid, find a placement of nodes onto grid points such that the number of crossings in a straight-line drawing is minimized. |
| Can MLLM See Local Properties in a Drawing of a Graph? | Research Project, Bachelor | Recently, we conducted an experiment with Multimodal Large Language Models (MLLM) on evaluating global properties of drawings of graphs. In the experiment, we showed the MLLM two drawings of a graph and the MLLM decided which one is better regarding a certain property. The results show, that MLLM can perform this task with similar (or even better) accuracy compared to human experts. Our conjecture is that the MLLM use visual proxies such as node distribution or edge lengths to arrive at a decision. As a follow-up, we want to extend this experiment and investigate local properties, such as local crossing number or edge length ratio, of a graph. |
| Visualization in Hyperbolic Spaces | Research Project, Bachelor, Master | Hyperbolic space is a consistent geometry in which parallel lines diverge. As a geometry, it is more “information dense” than Euclidean space and so has become of interest as a target space for neural networks, graphs, and dimension reduction. Here, there are several open problems:
|
| Interesting Subspaces in High Dimensional Data | Research Project, Master | Often a first task at understanding a high-dimensional dataset is to project it into 2 dimensions for an overview. There are often hidden relationships in these reduced plots, but manually finding them is a non-trivial task. We are interested in identifying “interesting” relationships between groups of datapoints to be used as a starting point in a visual analytics system. One example of interesting relationships might be a pair of clusters which are similar in one or more dimensions, but have been placed far apart in the 2d embedding. Such relationships might be identified through a mixture of classical analysis algorithms, machine learning tools, and novel ideas. |
| Stress-based Graph Embedding on the Torus | Research Project, Master | The surface of a torus is a two dimensional geometry with genus 1; that is, there is a hole in the topology. This surface can be embedded in two dimensions as a rectangle with opposite sides identified or “wrapped around”. This has been used in old arcade games such as Pac-Man and more recently as a proposed visualization style for node-link diagrams of graphs. However, the current algorithms to produce these diagrams are limited in scalability and distortion. In this project, a student will investigate prior torus-embedding approaches, be instructed on how to implement an improved torus-embedding approach, and make the algorithm available in a online system. |
| Do Perturbations Help in Solving Graph Tasks? | Research Project, Bachelor, Master | The human eye is particularly well suited to capturing movement, however many graph tasks are performed on static graphs. One might think that small “mini-animations” or “perturbations” around relevant areas of a graph drawing might improve task accuracy. We want to test several types of perturbations on several different graph tasks in a human-subject study to draw conclusions. |
| Measuring Symmetry of Graph Drawings | Research Project, Bachelor, Master | Several metrics to explicitly measure the symmetry of a graph drawing have been proposed, but are limited in computational complexity and interpret-ability. Other measures are known to be good proxies for symmetry when the symmetry exists, but still give unintuitive values when there is no symmetry in the drawing. We wish to create a novel symmetry measure by either leveraging techniques from computer vision and image recognition, or through a concrete mathematical formulation. |
| What properties are helpful in 2-layer Bipartite Drawings? | Research Project, Bachelor | Several objective functions for aesthetics in 2-layer bipartite drawings have been proposed, e.g. number of crossings, or the total span of the neighbors of vertices. However, there is as of yet no consensus on what is actually useful in terms of task support. A student will implement some of the current state-of-the-art algorithms and heuristics for 2-layer drawings, and help design and conduct a human-subjects study to understand each variants effectiveness. |
| To Split or Not to Split? Evaluating Vertex Splitting on 2-layer Bipartite Drawings. | Research Project, Bachelor | Vertex splitting is a technique to reduce the clutter in drawings of graphs. Splitting a vertex is replacing the original vertex with two copies and partitioning the edges from the original vertex over the two copies. While we potentially reduce the number of crossings and long edges in the graph, we now have to keep track of two copies. In this project, we would like to perform a human-subject study and compare split and unsplit drawings of bipartite graphs. |
| Interactive Optimization of Metaphorical Metro Maps. | Research Project, Bachelor, Master | The metro map metaphor is used to visualize set data. Set data occurs naturally in many real-world contexts, for example, patients (elements) and symptoms (sets), or musicians (elements) and music genres (sets). In this metaphor, set elements are the stations in the metro map and sets are the metro lines. If a line runs through a station, then the set element is a member of the set. Recently, a interactive approach for schematic maps for transport networks has been presented. This project would investigate, if this approach can be extended to visualizing set systems with the metro map metaphor. |