Parameterized Graph Drawing
- Funding organization: Vienna Science and Technology Fund, WWTF
- Project number: ICT22-029 (Information and Communication Technology 2022)
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.
2024 | |
[3] | The Parameterized Complexity Landscape of the Unsplittable Flow Problem Robert Ganian, Mathis Rocton, Daniel Unterberger Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2024, Spik, Slovenia, June 19-21, 2024, Revised Selected Papers, 2024, Springer Verlag. Note: to appear [bibtex] |
[2] | A Tight Subexponential Algorithm for Two-Page Book Embedding Robert Ganian, Haiko Müller, Sebastian Ordyniak, Giacomo Paesani, Mateusz Rychlicki 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-13, 2024, Tallinn, Estonia, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Note: to appear [bibtex] |
[1] | Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy Eduard Eiben Robert Ganian Iyad Kanj Argyrios Deligkas, Ramanujan M. Sridharan 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-13, 2024, Tallinn, Estonia, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Note: to appear [bibtex] |
2023 | |
[5] | 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, September 6-8, 2023, Amsterdam, The Netherlands (Neeldhara Misra, Magnus Wahlström, eds.), volume 285 of LIPIcs, pages 16:1–16:14, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. [bibtex] [pdf] [doi] |
[4] | 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] |
[3] | Upward and Orthogonal Planarity are W[1]-Hard Parameterized by Treewidth Bart M. P. Jansen, Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani, Kirill Simonov Graph Drawing and Network Visualization - 31st International Symposium, GD 2023, Isola delle Femmine, Palermo, Italy, September 20-22, 2023, Revised Selected Papers, Part II (Michael A. Bekos, Markus Chimani, eds.), volume 14466 of Lecture Notes in Computer Science, pages 203–217, 2023, Springer Verlag. [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] |