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 Dagstuhl 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. In recent years, research at the intersection of parameterized complexity and graph drawing has expanded well beyond a handful of problems, with new results and techniques emerging across a broad spectrum of topics.

The first two Dagstuhl Seminars on Parameterized Complexity in Graph Drawing (Dagstuhl Seminar 21293 in 2021 and Dagstuhl Seminar 23162 in 2023) successfully initiated this line of research, leading to new results, collaborations, and even a PACE Challenge edition centered on a graph drawing problem. Building on this success, the present seminar aims to advance the frontier further by tackling two pressing challenges: (i) integrating parameterized complexity with other paradigms such as approximation and counting/enumeration, and (ii) strengthening the practical impact of parameterized algorithms in graph drawing. Here, the discussions will address both concrete open problems as well as general directions for future research, with the aim of broadening the scope of parameterized methods and making them more impactful in practice.

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

Akanksha Agrawal, Philipp Kindermann, Martin Nöllenburg, and Meirav Zehavi