https://www.dagstuhl.de/23162

April 16 – 21 , 2023, Dagstuhl Seminar 23162

New Frontiers of Parameterized Complexity in Graph Drawing

Organizers

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)

For support, please contact

Susanne Bach-Bernhard for administrative matters

Michael Gerke for scientific matters

Motivation

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.

Motivation text license
  Creative Commons BY 4.0
  Robert Ganian, Fabrizio Montecchiani, Martin Nöllenburg, and Meirav Zehavi

Related Dagstuhl Seminar

Classification

  • Computational Complexity
  • Computational Geometry
  • Data Structures And Algorithms

Keywords

  • Parameterized complexity
  • Graph drawing
  • Computational geometry
  • Algorithm design

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.