https://www.dagstuhl.de/21062

February 7 – 12 , 2021, Dagstuhl Seminar 21062

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

Jutka Gasiorowski for administrative matters

Shida Kunz for scientific matters

Motivation

Graph-based models are pervasive in many fields of science and technology. Very often scientists and users analyze these models and communicate their findings by means of graphical representations. This motivated the birth and evolution of graph drawing, a self-standing discipline that has evolved tremendously over the past 50 years. Today graph drawing is a mature area of computer science, whose focus is on combinatorial and algorithmic aspects of drawing graphs as well as on the design of network visualization systems and interfaces. Graph drawing is motivated by applications where it is crucial to visually analyze and interact with relational datasets. Examples of such application areas include data science, social sciences, web computing, information systems, biology, geography, business intelligence, information security, and software engineering.

Numerous computational problems of wide interest, including classic graph drawing problems, are known to be NP-hard in general. Yet, it is often possible to utilize the structure implicitly underlying many real-world instances to find exact solutions efficiently. The graph drawing area has seen a long-standing systematic research of tractability results for various problems on specific classes of instances; indeed, research in this direction constitutes one of the fundamental aspects of computer science. However, in many real-world situations it is not possible to define a clear-cut class of instances that we wish to solve; instead of being black and white (belonging to a specific class or not), instances often come in various shades of grey (having certain degrees of internal structure). The relatively young parameterized complexity paradigm offers the perfect tools to deal with this situation. In the parameterized setting, we associate each instance with a numerical parameter, which captures how “structured” the instance is. This then allows the development of algorithms whose performance strongly depends on the parameter.

Research at the intersection of graph drawing and parameterized complexity (and parameterized algorithms in particular) is in its infancy. Most of the early efforts have been directed at variants of the classic Crossing Minimization problem, introduced by Turán in 1940, parameterized by the number of crossings. This Dagstuhl Seminar is designed to foster new research collaborations between researchers in the graph drawing and parameterized complexity communities, whose paths rarely cross in the traditional conferences. These collaborations are very likely to result in new breakthroughs and results, and we expect that the seminar will lead to tangible progress in our understanding of problems of interest.

The main goal of the 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.

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

Classification

  • Computational Geometry
  • Data Structures And Algorithms

Keywords

  • Graph Drawing
  • Parameterized Complexity
  • Graph Algorithms
  • Exact Computation

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).

Publications

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

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.