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 [7, 5, 10, 20], 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.

In a nutshell, a parameterization of a problem Π is the association of a parameter k with every instance of Π, capturing how "structured" the instance is. The main goal in parameterized complexity is to confine the combinatorial explosion in the runtime to a suitable parameter k, rather than to let it depend on the entire input size n. So, fixed-parameter algorithms naturally "scale" with the amount of structure of a given instance. Formally, a problem is fixed-parameter tractable (in short, in FPT) with respect to a parameter k if it can be solved by an algorithm, called a fixed-parameter algorithm, whose runtime is bounded by f(k) ⋅ n^O(1) for some computational function f of k. Over the past four decades, the parameterized complexity paradigm has yielded a rich and deep theory, with powerful approaches to obtain fixed-parameter algorithms for a variety of problems as well as machinery that can rule out such algorithms. For problems in FPT, it also offers the necessary tools to develop the fastest possible fixed-parameter algorithms (often with tight conditional lower bounds).

While the parameterized paradigm can be applied in a wide range of different fields, the focus of this Dagstuhl Seminar lay squarely on its potential synergies with graph drawing, a self-standing discipline that has evolved tremendously over the last decades. 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. Today, graph drawing is a mature area of computer science [6, 17, 21, 22] with its own annual conference, the International Symposium on Graph Drawing and Network Visualization (GD). The focus of graph drawing as a research area today is on both fundamental and practical aspects, such as combinatorics and algorithm design on the one hand, and the development of network visualization systems and interfaces on the other hand. 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, grid 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 not reached its full potential.

Parameterized Graph Drawing. Most of the early efforts to conduct research at the intersection of parameterized complexity and graph drawing have been directed at variants of the classic Crossing Minimization problem, introduced by Turán in 1940 [23], parameterized by the number of crossings. Here, the objective is to draw a given graph in the plane so as to induce the minimum number of crossings, which was shown to be FPT already in 2001 [13]. A few subsequent works followed [18, 15], including the best paper of GD 2019 [16]. Other examples of graph drawing problems successfully targeted by the parameterized paradigm include crossing minimization in restricted settings [8, 19], crossing-sensitive subgraph detection [1, 14], parameterized algorithms for stack and queue layouts [2, 3, 4], and drawing extension problems [9, 11]. While these and other works already lay down the foundations of possible positive synergies between the two fields, there still is a multitude of problems and opportunities in graph drawing where parameterized analysis would be beneficial and has not yet been carried out.

Seminar Goals

The main goal of the seminar was to explore and initiate collaborations at the intersection of Graph Drawing and Parameterized Complexity, with emphasis on new research frontiers. In particular:

• First, the seminar focused on prominent topics in Graph Drawing, encouraging the consideration of topics that have been only little - or not at all - studied from the perspective of Parameterized Complexity. Here, the discussions centered on the identification of open problems of wide interest as well as directions for future research.
• Second, the seminar focused on new tools and sub-areas of Parameterized Complexity, such as structural parameterization, non-standard general decomposition theorems, and FPT-approximation, which have been rarely - or not at all - examined in the context of Graph Drawing. The aim was to understand their potential and relevance in the context of the aforementioned topics.

The seminar included invited talks focused on the above goals, setting the ground for the participants to propose problems (and, more generally, research directions) to work on, as well as be familiar with relevant tools to work with. The final selection of problems targeted by working groups was carried out during the seminar itself. This, in turn, also resulted in the establishment of new and fruitful collaborations.

Seminar Program

We started the seminar week on Monday morning with short self-introduction presentations of all participants, followed by the four invited overview talks mentioned above, which aimed to set the grounds for the research discussions throughout the week. We invited two speakers from each of the two communities coming together in this seminar to create a common understanding of research questions, tools, and terminology. The first of these lectures was given by Saket Saurabh on the topic of fixed-parameter tractability for geometric intersection graphs. Next, Ignaz Rutter spoke about the widely used SPQR tree data structure for representing planar graph embeddings. As the third speaker, Bart M. P. Jansen highlighted three frontiers in parameterized graph drawing based on lossy (structural) kernelization and hybrid parameterizations. Lastly, Giordano Da Lozzo presented complexity results and parameterized algorithms for the upward book embedding problem. Further, we had a short session for reports about the final results of working groups from the previous edition of the seminar in 2021. Section 3 of the full report contains more detailed abstracts of the invited lectures and the reports from Dagstuhl Seminar 21293.

The remainder of the seminar focused on research discussions on new frontiers of parameterized graph drawing. In order to identify these frontiers, we had two open problem sessions, one on Monday afternoon and one on Tuesday morning. A total of 13 open research questions (see Section 4of the full report) were contributed by the participants. Based on a preference vote, we created five working groups for the seminar week, each having six or seven participants mixed from the two communities joined in this seminar. The following five topics were investigated in depth:

1. Parameterized Complexity of the Maximum Bimodal Subgraph Problem
2. Parameterized Complexity of Upward Planarity and st-Planar Edge Completion Problems
3. Parameterized Algorithms for the Sequential Crossing Number Problem
4. Deleting Few Edges from Ordered Graphs to Make them k-Plane
5. Clustered Planarity and Planar ℱ-Augmentations

For each of the five working groups, Section 5 of the full report contains a detailed report of their current state of research. During the seminar, on Tuesday and Thursday afternoon, we had plenary sessions for the groups’ progress reports sharing their latest results and further plans. Wednesday afternoon was reserved for the traditional excursion, for which we enjoyed a Treetop-Walk near the Great Bend in the Saar and then hiked to Mettlach for a traditional brewery dinner.

Future Plans

The composition of the working groups was made having in mind two main criteria: balancing the number of participants from the two communities, guaranteeing the presence of some young researcher in each group. This strategy was indeed successful and it led to new collaborations between researchers in the graph drawing and parameterized complexity communities, as well as to new opportunities for young researchers. As a primary outcome of the seminar, we expect research papers published at the core conferences and journals for the graph drawing and parameterized complexity communities, for instance:

• The International Symposium on Computational Geometry (SoCG),
• The International Symposium on Graph Drawing and Network Visualization (GD),
• The ACM-SIAM Symposium on Discrete Algorithms (SODA), and
• The International Symposium on Algorithms and Computation (ISAAC).

In the mid- and long-term horizon, the seminar will also help to gradually blend the boundary between the two communities, with young researchers building their academic journey on the intersection of the two fields. In this respect, the seminar can also lead to the development of new parameterized tools and techniques that are designed to deal with the specific obstacles that arise when trying to apply parameterized approaches in the graph drawing setting.

This Dagstuhl Seminar and its predecessor (Dagstuhl Seminar 21293) have revealed, in a systematic way, the astounding wealth of problems in Graph Drawing that are naturally multivariate and hence suitable for parameterized analysis. The two communities are now aware of these problems, and the above mentioned conferences (among others) publish every year a growing number of results making progress on these problems. Besides this, informal feedback from the communities confirms the great interest in having such seminars on a more regular basis. We therefore plan to have follow-up seminars to support the growth of parameterized complexity in graph drawing.

Evaluation

Taking into account the results of the Dagstuhl survey conducted after the seminar and informal feedback to the organizers, it is fair to say that the seminar was highly appreciated. The participants provided significantly above-average scores for the seminar, particularly in areas concerning new collaborative research projects, identification of novel research directions, and collaboration between different research communities. Overall, we believe that the seminar’s goals of identifying new research directions and initiating collaborations at the intersection of the two different fields of Graph Drawing and Parameterized Complexity were very successful. We are looking forward to seeing the first scientific outcomes of the seminar in the near future and to continuing the efforts to support the growth of interest in parameterized analysis of problems in Graph Drawing.

Acknowledgments

Schloss Dagstuhl, once again, was a perfect location for hosting this research seminar with its great conference and meeting facilities, combined with the unique atmosphere of the castle and lots of opportunities for socializing and networking. On behalf of all participants, we want to express our gratitude to the entire Dagstuhl staff for letting us have such a wonderful week. We further thank Liana Khazaliya for helping us collect the various contributions and prepare this report.

References

1. Akanksha Agrawal, Grzegorz Guspiel, Jayakrishnan Madathil, Saket Saurabh, and Meirav Zehavi. Connecting the Dots (with Minimum Crossings). In Gill Barequet and Yusu Wang, editors, Symposium on Computational Geometry (SoCG 2019), volume 129 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1–7:17, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
2. Michael J. Bannister, David Eppstein, and Joseph A. Simons. Fixed parameter tractability of crossing minimization of almost-trees. In Graph Drawing (GD 2013), volume 8242 of Lecture Notes in Computer Science, pages 340–351. Springer, 2013.
3. Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani, and Martin Nöllenburg. Parameterized algorithms for book embedding problems. J. Graph Algorithms Appl., 24(4):603–620, 2020.
4. Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani, and Martin Nöllenburg. Parameterized algorithms for queue layouts. In Graph Drawing, volume 12590 of Lecture Notes in Computer Science, pages 40–54. Springer, 2020.
5. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.
6. Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, 1999.
7. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer Verlag, 2013.
8. Vida Dujmovic, Michael R. Fellows, Matthew Kitching, Giuseppe Liotta, Catherine Mc- Cartin, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond, Sue Whitesides, and David R. Wood. On the parameterized complexity of layered graph drawing. Algorithmica, 52(2):267–292, 2008.
9. Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute, and Martin Nöllenburg. Extending partial 1-planar drawings. In ICALP, volume 168 of LIPIcs, pages 43:1–43:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020.
10. F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2018.
11. Robert Ganian, Thekla Hamm, Fabian Klute, Irene Parada, and Birgit Vogtenhuber. Crossing-optimal extension of simple drawings. In ICALP, volume 198 of LIPIcs, pages 72:1–72:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.
12. Ashim Garg and Roberto Tamassia. On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput., 31(2):601–625, 2001.
13. Martin Grohe. Computing crossing numbers in quadratic time. J. Comput. Syst. Sci., 68(2):285–302, 2004.
14. Magnús M. Halldórsson, Christian Knauer, Andreas Spillner, and Takeshi Tokuyama. Fixedparameter tractability for non-crossing spanning trees. In Algorithms and Data Structures (WADS 2007), volume 4619 of Lecture Notes in Computer Science, pages 410–421. Springer, 2007.
15. Petr Hlinený and Marek Dernár. Crossing number is hard for kernelization. In Symposium on Computational Geometry (SoCG 2016), volume 51 of LIPIcs, pages 42:1–42:10. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 2016.
16. Petr Hlinený and Abhisekh Sankaran. Exact crossing number parameterized by vertex cover. In Graph Drawing and Network Visualization (GD 2019), volume 11904 of Lecture Notes in Computer Science, pages 307–319. Springer, 2019.
17. Michael Jünger and Petra Mutzel, editors. Graph Drawing Software. Springer, 2004.
18. Ken-ichi Kawarabayashi and Bruce A. Reed. Computing crossing number in linear time. In Symposium on Theory of Computing (STOC 2007), pages 382–390. ACM, 2007.
19. Fabian Klute and Martin Nöllenburg. Minimizing crossings in constrained two-sided circular graph layouts. J. Comput. Geom., 10(2):45–69, 2019.
20. Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. OUP Oxford, 2006.
21. Takao Nishizeki and Md. Saidur Rahman. Planar Graph Drawing, volume 12 of Lecture Notes Series on Computing. World Scientific, 2004.
22. Roberto Tamassia, editor. Handbook on Graph Drawing and Visualization. Chapman and Hall/CRC, 2013.
23. Paul Turán. A note of welcome. Journal of Graph Theory, 1(1):7–9, 1977. 23162

Creative Commons BY 4.0

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