Parameterized Graph Drawing

• Funding organization: Vienna Science and Technology Fund, WWTF
• Project number: ICT22-029 (Information and Communication Technology 2022)

Project Team

Robert Ganian (Principal Investigator)

Martin Nöllenburg (Principal Investigator)

Simon Dominik Fink (Postdoctoral Researcher)

Thomas Depian (PhD Student)

Alexander Firbas (PhD Student)

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.