Dagstuhl-Seminar 23162
New Frontiers of Parameterized Complexity in Graph Drawing
( 16. Apr – 21. Apr, 2023 )
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/23162
Organisatoren
- Robert Ganian (TU Wien, AT)
- Fabrizio Montecchiani (University of Perugia, IT)
- Martin Nöllenburg (TU Wien, AT)
- Meirav Zehavi (Ben Gurion University - Beer Sheva, IL)
Kontakt
- Michael Gerke (für wissenschaftliche Fragen)
- Susanne Bach-Bernhard (für administrative Fragen)
Dagstuhl Reports
As part of the mandatory documentation, participants are asked to submit their talk abstracts, working group results, etc. for publication in our series Dagstuhl Reports via the Dagstuhl Reports Submission System.
- Upload (Use personal credentials as created in DOOR to log in)
Dagstuhl Seminar Wiki
- Dagstuhl Seminar Wiki (Use personal credentials as created in DOOR to log in)
Gemeinsame Dokumente
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
In modern life, it is of paramount importance that computational tasks be performed both precisely and efficiently. Thus, the design and analysis of algorithms to execute such tasks lie at the heart of computer science. However, since the proof of the Cook-Levin theorem in the 1970s, numerous problems have been shown to be NP-hard. Fortunately, the field of parameterized complexity, initiated in the 1980s by Downey and Fellows, yields (in)tractability results that are both deeper and fine-grained. Specifically, it shows that the “hardness” of an NP-hard problem can often be traced to particular parameters of its instances.
While the parameterized complexity paradigm can be applied in a wide range of different fields, the focus of this seminar will lie squarely on its potential synergies with graph drawing, a self-standing discipline that has evolved tremendously over the last decades, as witnessed by the annual International Symposium on Graph Drawing and Network Visualization (GD). Indeed, given the ubiquity of graphs in many fields of science and technology, there is a strong interest in algorithms that can provide effective graphical representations of graphs, for the sake of both analysis and communication. At a very high level, graph drawing deals with the construction and analysis of geometric representations of graphs and networks subject to specific layout conventions and constraints, such as different notions of planarity or more general crossing constraints, linear layouts, orthogonal drawings, and many more. Notably, this gives rise to many computational problems that are NP-hard in the classical sense but naturally multivariate, making parameterized analysis particularly attractive. Yet, so far, research at the intersection of parameterized complexity and graph drawing has been limited to a narrow set of problems.
The main goal of this Dagstuhl Seminar is to chart new paths towards research combining the latest findings and techniques in parameterized complexity and graph drawing. In particular, the seminar will focus on several prominent topics in graph drawing as well as state-of-the-art tools in parameterized complexity. Here, the discussions will address both concrete open problems as well as general directions for future research. A central topic to address in the discussions is the applicability of cutting-edge tools in parameterized complexity to graph drawing.
We aim for a seminar format that is centered around in-depth research discussions in several smaller break-out groups composed of researchers mixed from both communities, interleaved with few, but regular, plenary sessions throughout the week. The break-out groups will work on discussing and solving open problems suggested by the participants with opportunities for joint publications after the seminar.
Creative Commons BY 4.0
Robert Ganian, Fabrizio Montecchiani, Martin Nöllenburg, and Meirav Zehavi
- Akanksha Agrawal (Indian Institute of Techology Madras, IN) [dblp]
- Sergio Cabello (University of Ljubljana, SI) [dblp]
- Giordano Da Lozzo (University of Rome III, IT) [dblp]
- Walter Didimo (University of Perugia, IT) [dblp]
- Eduard Eiben (Royal Holloway, University of London, GB) [dblp]
- Fedor V. Fomin (University of Bergen, NO) [dblp]
- Robert Ganian (TU Wien, AT) [dblp]
- Petr A. Golovach (University of Bergen, NO) [dblp]
- Siddharth Gupta (University of Warwick - Coventry, GB) [dblp]
- Thekla Hamm (Utrecht University, NL) [dblp]
- Petr Hlinený (Masaryk University - Brno, CZ) [dblp]
- Tanmay Inamdar (University of Bergen, NO)
- Bart Jansen (TU Eindhoven, NL) [dblp]
- Michael Kaufmann (Universität Tübingen, DE) [dblp]
- Liana Khazaliya (TU Wien, AT)
- Philipp Kindermann (Universität Trier, DE) [dblp]
- Stephen G. Kobourov (University of Arizona - Tucson, US) [dblp]
- Giuseppe Liotta (University of Perugia, IT) [dblp]
- Bojan Mohar (Simon Fraser University - Burnaby, CA) [dblp]
- Fabrizio Montecchiani (University of Perugia, IT) [dblp]
- Martin Nöllenburg (TU Wien, AT) [dblp]
- Sebastian Ordyniak (University of Leeds, GB) [dblp]
- Ignaz Rutter (Universität Passau, DE) [dblp]
- Saket Saurabh (The Institute of Mathematical Sciences - Chennai, IN) [dblp]
- Raimund Seidel (Universität des Saarlandes - Saarbrücken, DE) [dblp]
- Roohani Sharma (MPI für Informatik - Saarbrücken, DE) [dblp]
- Marie Diana Sieper (Universität Würzburg, DE)
- Kirill Simonov (Hasso-Plattner-Institut, Universität Potsdam, DE) [dblp]
- Manuel Sorge (TU Wien, AT)
- Yushi Uno (Osaka Metropolitan University, JP) [dblp]
- Alexander Wolff (Universität Würzburg, DE) [dblp]
- Meirav Zehavi (Ben Gurion University - Beer Sheva, IL) [dblp]
Verwandte Seminare
- Dagstuhl-Seminar 21293: Parameterized Complexity in Graph Drawing (2021-07-18 - 2021-07-23) (Details)
Klassifikation
- Computational Complexity
- Computational Geometry
- Data Structures and Algorithms
Schlagworte
- parameterized complexity
- graph drawing
- computational geometry
- algorithm design
