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

4 results
2023
[4]From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem
Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider
18th International Symposium on Parameterized and Exact Computation, IPEC 2023, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Note: to appear
[bibtex]
[3]The Parameterized Complexity of Coordinated Motion Planning
Eduard Eiben, Robert Ganian, Iyad Kanj
39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA (Erin W. Chambers, Joachim Gudmundsson, eds.), volume 258 of LIPIcs, pages 28:1–28:16, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[2]Fixed-Parameter Algorithms for Computing RAC Drawings of Graphs
Cornelius Brand, Robert Ganian, Sebastian Röder, Florian Schager
31st International Symposium on Graph Drawing and Network Visualization (GD 2023), 2023, Springer Verlag.
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, June 12-15, 2023, Dallas, Texas, USA (Erin W. Chambers, Joachim Gudmundsson, eds.), volume 258 of LIPIcs, pages 18:1–18:16, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]

News

  • Jiehua Chen: promotion to tenured Associate Professor

    Jiehua Chen: promotion to tenured Associate Professor

    2023-10-18
    After her successful tenure evaluation, our colleague Jiehua Chen has been promoted to an Associate Professor. Hua joined the Algorithms …Read More »
  • Successful Graph Drawing conference 2023 in Palermo

    Successful Graph Drawing conference 2023 in Palermo

    2023-09-23
    The 31st edition of the International Symposium on Graph Drawing and Network Visualization in Palermo, Italy, ended on September 22, …Read More »
  • PhD completed by Anaïs Villedieu

    PhD completed by Anaïs Villedieu

    2023-07-24
    Anaïs Villedieu successfully defended her PhD thesis “Engineering Human-in-the-loop Graph Drawing Algorithms” on July 24, 2023. Congratulations, Dr. Villedieu! Anaïs …Read More »
  • 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 »

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.