TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 23162

New Frontiers of Parameterized Complexity in Graph Drawing

( Apr 16 – Apr 21, 2023 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/23162

Organizers

Contact

Shared Documents

Schedule

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.

Copyright Robert Ganian, Fabrizio Montecchiani, Martin Nöllenburg, and Meirav Zehavi

Participants

Related Seminars
  • Dagstuhl Seminar 21293: Parameterized Complexity in Graph Drawing (2021-07-18 - 2021-07-23) (Details)

Classification
  • Computational Complexity
  • Computational Geometry
  • Data Structures and Algorithms

Keywords
  • parameterized complexity
  • graph drawing
  • computational geometry
  • algorithm design