https://www.dagstuhl.de/21062

07. – 12. Februar 2021, Dagstuhl-Seminar 21062

Parameterized Complexity in Graph Drawing

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)

Auskunft zu diesem Dagstuhl-Seminar erteilen

Jutka Gasiorowski zu administrativen Fragen

Shida Kunz zu wissenschaftlichen Fragen

Dokumente

Programm des Dagstuhl-Seminars (Hochladen)

(Zum Einloggen bitte persönliche DOOR-Zugangsdaten verwenden)

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

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.