Welcome to the Efficient Algorithms and Visualization research group at the Technical University of Munich (TUM), led by Prof. Stephen Kobourov. We are part of the TUM School of Computation, Information and Technology (Campus Heilbronn) and our work bridges theory and practice in computer science. As Prof. Kobourov often notes, “in theory there is no difference between theory and practice, but in practice there is”. Guided by this philosophy, our group conducts research that ranges from fundamental algorithm design and analysis to real-world applications in data visualization and geometry. We specialize in efficient algorithms covering areas such as graph algorithms, computational geometry, dimensionality reduction, and visualization with a dual focus on rigorous theoretical foundations and practical impact. Our goal is to develop new algorithms and tools and apply them to solve complex problems in graphs, networks, and high-dimensional data, in an approachable way that inspires students and collaborators alike.

Research Themes

• Graph Algorithms: We design and analyze algorithms for problems on graphs (networks). This includes developing faster or more memory-efficient solutions for classical graph problems and new network structures. Examples range from graph spanners (sparse subgraphs that preserve distances) to network design and optimization problems like Steiner trees. By creating efficient graph algorithms, we tackle challenges in communication networks, social network analysis, and other domains that rely on large-scale graphs. Our approach often blends combinatorial theory with careful implementation (algorithm engineering) to ensure our solutions are both provably good in theory and effective in practice.
• Computational Geometry: Many problems we study have a geometric flavor. In computational geometry, we explore algorithms for spatial data and geometric structures. This can involve planar graphs, geometric representations of graphs, clustering in the plane, or problems like facility location and point set matching. We seek algorithms that handle geometric constraints (e.g. points, distances, shapes) efficiently. These geometric algorithms underpin applications such as graphics, spatial data analysis, geographic information systems, and even robotics. By understanding the geometry behind algorithmic problems, we can achieve solutions that are both mathematically elegant and useful for real-world spatial data.
• Graph Drawing & Network Visualization: We have a strong focus on graph drawing, which addresses how to automatically draw networks (graphs) in an informative and aesthetically pleasing way. Graph drawing combines algorithms and visualization: we develop methods to position nodes and route edges so that the resulting diagrams of networks are easy to read and analyze. Our research in this area includes optimizing layout aesthetics (like minimizing edge crossings or improving angle clarity) and studying the perception of graph drawings (what layout features help people understand networks). Closely related is graph & network visualization, where we create interactive visual tools for exploring complex networks. For example, we’ve studied a broad range of graph layout quality metrics (such as crossings, angular resolution, edge lengths, etc.) to compare different layout algorithms. Understanding these metrics helps in choosing or even automating the best layout for a given graph, and our recent work has provided new insights into how layout algorithms perform across these criteria. Overall, this theme connects theory (graph algorithms for drawing) with practical visualization techniques, enabling clearer insight into data ranging from social networks to biological networks.
• Dimensionality Reduction: High-dimensional data (with dozens or thousands of attributes) is often hard to understand. We work on dimensionality reduction techniques, which create lower-dimensional representations of complex data while preserving important structure. A prominent example is t-SNE and related algorithms that embed high-dimensional datasets into 2D or 3D for visualization. In our group, we not only apply such techniques but also develop new ones. For instance, we created an approach called ENS-t-SNE that extends t-SNE to 3D embeddings, allowing multiple views of the same data to be visualized simultaneously. By embedding neighborhoods simultaneously, different clusters or patterns in the data become visible from different viewpoints within one coherent visualization. This line of research ties into machine learning, as we explore how to maintain meaningful structure (like clusters or nearest-neighbor relationships) when reducing dimensions. Effective dimensionality reduction is crucial in fields like bioinformatics, image and text analysis, where visualizing the data can lead to new insights. Our focus is on algorithms that are both mathematically well-founded and useful for interactive data exploration.
• Applications and Interdisciplinary Work: While our primary expertise lies in algorithms and visualization, we actively apply our work to interdisciplinary projects. Group members have worked on visual analytics systems, network analysis in neuroscience and social science, and interactive tools for exploring data. We believe that applying our algorithms to real data sets or collaborating with domain experts not only demonstrates the utility of our methods but also inspires new theoretical questions. Students in our group often have the opportunity to engage in projects that connect theory with practice – for example, implementing a graph drawing tool for a specific application, or optimizing an algorithm to handle real datasets in biology or engineering. This practical orientation complements our theoretical research, and it provides a rich training ground for students to develop a broad skill set.

Selected Recent Publications

To get a flavor of our work, here are a few recent publications from the group, illustrating our blend of theory and practice:

• “The Multi-Dimensional Landscape of Graph Drawing Metrics.” In IEEE PacificVis 2024, we explore how different quantitative metrics can characterize the quality of graph layouts. By analyzing ten normalized layout metrics across many graphs and layout algorithms, this study reveals which drawing algorithms produce a broad range of layouts and how various aesthetics (like edge crossings, angles, distances) correlate with each other. This paper was recognized with the Best Paper Award at PacificVis 2024, underscoring its impact in the visualization community.
• “ENS-t-SNE: Embedding Neighborhoods Simultaneously.” Presented at IEEE PacificVis 2024, this work introduces a novel dimensionality reduction technique that generalizes the popular t-SNE algorithm to enable multiple views of high-dimensional data in a single embedding. By using a 3D projection, ENS-t-SNE allows viewers to see different types of clusters or groupings from different angles of the same embedding, which is difficult with traditional 2D plotsexperts.arizona.edu. We demonstrated the utility of this approach on real-world datasets and showed that it helps in tracking various clustering patterns without losing the correspondence between points when switching views.
• “Multi-level Weighted Additive Spanners.” In Symposium on Experimental Algorithms (SEA) 2021, we tackled a problem in graph algorithms related to network design. This paper presents new algorithms for constructing graph spanners, sparse subgraphs that preserve distances approximately, in a multi-level context. Here, vertices have different priority levels (or quality-of-service requirements), and the goal is to maintain small distance errors for high-priority vertices while keeping the overall subgraph very sparse. We provided both theoretical generalizations of spanner constructions to weighted graphs and an extensive experimental evaluation of our algorithms. The results help in designing efficient network backbones that can cater to tiered service levels (for example, in multi-tier network infrastructures) with provable guarantees.
• “MetroSets: Visualizing Sets as Metro Maps.” Presented at IEEE InfoVis 2020, this project combines graph drawing with information visualization to handle set systems. MetroSets is a novel visualization technique where each data set is drawn as a “metro line” and each element of the sets is a “station.” If an element belongs to multiple sets, it appears as an interchange connecting those lines. We developed a complete pipeline of algorithms to generate these metro map layouts for sets (modeled as hypergraphs). The result is an intuitive visual representation that scales to dozens of sets and hundreds of elements, leveraging the familiar metaphor of metro transit maps. MetroSets makes it easier to see overlaps and relationships in complex set data (beyond what Venn diagrams can show), and it demonstrates how theoretical concepts like hypergraphs and planarity can be applied to create user-friendly visualization toolsar5iv.org. (Fun fact: we even released an interactive prototype for MetroSets, so anyone can turn their own dataset into a metro map!)