Parameterized Graph Drawing
- Funding organization: Vienna Science and Technology Fund, WWTF
- Project number: ICT22-029 (Information and Communication Technology 2022)
Project Team
The Project Team
Research Statement
The project is centered around two well-established fields of information and communication technology: (1) graph drawing and visualization, which deals with the construction and analysis of geometric representations of graphs and networks subject to specific layout conventions, and (2) parameterized complexity analysis, which offers the tools to design efficient algorithms as well as lower bounds custom-tailored to the specific structural properties of relevant inputs. Recent advances have highlighted the huge potential for the application of parameterized techniques on graph drawing and visualization problems. The two PIs of this proposal – Robert Ganian and Martin Nöllenburg – have already spearheaded an initial push to bring the two fields closer together, and this proposal will allow them to bring these efforts into fruition by targeting and resolving some of the most prominent questions in this intersection.
The project focuses on developing the tools and frameworks that will facilitate the parameterized analysis of central problems in graph drawing and visualization. The work is split into four fundamental themes, covering Extension Problems, Linear and Layered Layouts, Geometric Graph Representations and Bridges to Network Visualization. The output of each theme will include not only new algorithms but also tight lower bounds and, where relevant, implementations, significantly advancing the state of the art in these increasingly prominent fields of research.
Project Developments
2026
Mihai Pătrașcu Best Paper Award at SOSA 2026
January 12, 2026. Ajaykrishnan E S, Robert Ganian, Daniel Lokshtanov, and Vaishali Surianarayanan have been awarded the inaugural Mihai Pătrașcu Best Paper Award at the 2026 SIAM Symposium on Simplicity in Algorithms (SOSA) for their paper, "A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs." The paper targets an alternative formulation of the Book Thickness problem, which is central to the PGD project.
2025
Three Contest Awards for Graph Drawing Student Teams
September 26, 2025. At the 33rd International Symposium on Graph Drawing and Network Visualization in Norrköping, Sweden, student teams from TU Wien—originating from Martin Nöllenburg’s Graph Drawing Algorithms Master course—achieved top honors in multiple categories of the annual Graph Drawing Contest. In the creative category, which required designing a 360° visualization of cause-and-effect relationships from the Netflix series Dark for a 6-meter cylindrical display, the student team of Florian Saß, Jakob Speitkamp, and Guilherme Monteiro Oliveira (supervised by Thomas Depian) won first prize for their project, "Journey of a Time Machine." Additionally, in the automatic live challenge—a one-hour competition focused on implementing custom, highly efficient algorithms to minimize edge crossings in complex graphs—TU Wien students supervised by Simon D. Fink excelled further, with Christoph Weber securing second prize and the team of Stefan Brandmair and Luca Marius Cobzaru taking third place.
Best Paper Award at SOFSEM 2025
January 23, 2025. Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, and Martin Nöllenburg (i.e., the whole PGD team) received the Best Paper Award for their paper "Pathways to Tractability for Geometric Thickness" at the 50th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM) held in Bratislava, Slovakia from January 20-23, 2025.
2024
State Prize for Thomas Depian's Master Thesis
November 21, 2024. Our project team member Thomas Depian won the Appreciation Award given by the Federal Ministry for Education, Science and Research. This state prize is awarded annually to the best 55 Master graduates among each year's about 16.000 graduates of all Austrian universities. In 2024 Thomas, as one of only two students of TU Wien, received this prestigious award for his Master's thesis "Grouping and Ordering Constraints in Boundary Labeling", supervised by Martin Nöllenburg. Thomas will present the results of his thesis at the 35th International Symposium on Algorithms and Computation (ISAAC'24) in Sydney, Australia in December 2024.
