Algorithms and Complexity Group
  • People
  • Research
  • Courses
  • Talks
  • Jobs
  • Contact

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)

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.

Call for Applications

We are currently hiring two PhD students and one Postdoctoral Researcher.

Call for Applications for PhD Students

The positions are part of the project "Parameterized Graph Drawing" and are hosted by the Algorithms and Complexity Group at TU Wien (the Vienna University of Technology). The accepted students will be co-supervised by Robert Ganian and Martin Nöllenburg.

We offer the possibility of working on exciting research projects in an international research group, with ample travel funding, and the option of collaborating not only with postdocs and PhD students within the project but also with other members of the Algorithms and Complexity Group (https://www.ac.tuwien.ac.at/). There are no major teaching obligations associated with the position and the working language in the group is English. The starting date is flexible, but no earlier than June 1, 2023, and the position is offered for 3.5 years with possibility of extension to 4 years. The salary will follow the FWF's salary tables for Doctoral candidates (see
https://www.fwf.ac.at/en/research-funding/personnel-costs/) and includes standard bonuses in the form of a 13th and 14th salary, altogether allowing for a convenient life in Vienna close to the city center.

Applicants are required to have or soon receive a Master degree in Computer Science, Mathematics or a related field and are expected to have a strong interest in scientific research, at least a basic understanding of parameterized complexity or graph drawing, and a willingness to work in the intersection of these two fields.

The application should include the candidate's CV, a short motivation letter, and optionally also a letter of recommendation (all in a single pdf file; alternatively, the letter of recommendation may be sent directly by their authors). Applicants are invited to also send a copy of their Master thesis as a separate pdf file. The application should mention possible starting dates and should be sent to pgd@ac.tuwien.ac.at by Tuesday the 25th of April 2023.

Informal enquiries and questions about the position are very welcome and should also be sent to pgd@ac.tuwien.ac.at.

Call for Applications for Postdoctoral Researcher

The position is part of the project "Parameterized Graph Drawing" and is hosted by the Algorithms and Complexity Group at TU Wien (the Vienna University of Technology). The position will be jointly supervised by Robert Ganian and Martin Nöllenburg.

We offer the possibility of working on exciting research projects in an international research group, with ample travel funding, and the option of collaborating not only within the project but also with other members of the Algorithms and Complexity Group (https://www.ac.tuwien.ac.at/). There are essentially no teaching obligations associated with the position and the working language in the group is English. The starting date is flexible and the position is offered for 2 years, with a possibility for extension. The salary will follow the FWF's salary tables for Postdocs (see https://www.fwf.ac.at/en/research-funding/personnel-costs/) and includes standard bonuses in the form of a 13th and 14h salary, altogether allowing for a convenient life in Vienna close to the city center.

Applicants are required to have a PhD in Computer Science (or a related field) and are expected to have a strong research record in parameterized complexity or graph drawing, and a willingness to work in the intersection of these two fields.

The application should include the candidate's CV, a list of publications, a short motivation letter, and two letters of recommendation (all in a single pdf file; alternatively, letters of recommendation may be sent directly by their authors). The application should also mention possible starting dates and should be sent to pgd@ac.tuwien.ac.at by Wednesday the 3rd of May 2023.

Informal enquiries and questions about the position are very welcome and should also be sent to pgd@ac.tuwien.ac.at.

Publications

2022

2 results
2023
[2]The Parameterized Complexity of Coordinated Motion Planning
Eduard Eiben, Robert Ganian, Iyad Kanj
39th International Symposium on Computational Geometry, SoCG 2023, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Note: to appear
[bibtex]
[1]Extending Orthogonal Planar Graph Drawings is Fixed-Parameter Tractable
Sujoy Bhore, Robert Ganian, Liana Khazaliya, Fabrizio Montecchiani, Martin Nöllenburg
39th International Symposium on Computational Geometry, SoCG 2023, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Note: to appear
[bibtex]

News

  • PhD completed by Andre Schidler

    PhD completed by Andre Schidler

    2023-05-31
    Congratulations to André Schidler, who successfully defended his PhD thesis "Scalability for SAT-based combinatorial problem solving" today.   Thanks to …Read More »
  • PhD completed by Vaidyanathan P.R.

    PhD completed by Vaidyanathan P.R.

    2023-05-12
    Congratulations to Vaidyanathan P.R., who successfully defended his PhD thesis Scalable Bayesian Network Structure Learning using SAT-based Methods today. Thanks …Read More »
  • New FWF ESPRIT Postdocs

    New FWF ESPRIT Postdocs

    2022-11-09
    Leroy Chew and Alexis de Colnet just joined the Algorithms and Complexity group as PIs of their own FWF ESPRIT …Read More »
  • Best student paper award at DIAGRAMS 2022

    Best student paper award at DIAGRAMS 2022

    2022-10-01
    Alexander Dobler received the Best Student Paper Award at the 13th International Conference on the Theory and Application of Diagrams …Read More »
  • Robert Ganian promoted to Associate Professor

    Robert Ganian promoted to Associate Professor

    2022-07-01
    Effective as of today, Robert Ganian is promoted to a tenured Associate Professor at the Algorithms and Complexity group. Congratulations, …Read More »

News archive

All news for 2015, 2016, 2017, 2018, 2019, 2020, 2021 and 2022.
TU Wien Informatics
Offenlegung (§25 MedienG) Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. – Disclaimer – Datenschutzerklärung
Log in requires cookies.