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.

Creative Commons BY 3.0 DE

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