At the conference 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024), taking place September 16 - 20, 2024, in Vienna, Austria, two articles from our research group have been accepted:

1. On k-Plane Insertion into Plane Drawings von Julia Katheder, Philipp Kindermann, Fabian Klute, Irene Parada & Ignaz Rutter
   Proceedings Version: TBA
   Arxiv Version: https://arxiv.org/abs/2402.14552
2. Weakly Leveled Planarity with Bounded Span von Michael A. Bekos, Giordano Da Lozzo, Fabrizio Frati, Siddharth Gupta, Philipp Kindermann, Giuseppe Liotta, Ignaz Rutter & Ioannis G. Tollis
   Proceedings Version: TBA
   Arxiv Version: https://arxiv.org/abs/2409.01889

The article Perfect Matchings with Crossings by Aichholzer, Ruy Fabila Monroy, Philipp Kindermann, Irene Parada, Rosna Paul, Daniel Perz, Patrick Schnider & Birgit Vogtenhuber has been published in the journal Algorithmica in the Special Issue der IWOCA 2022.

Journal Version: https://doi.org/10.1007/s00453-023-01147-7

The article On k-Plane Insertion into Plane Drawings by Julia Katheder, Philipp Kindermann, Fabian Klute, Irene Parada & Ignaz Rutter has been accepted at the conference 40th European Workshop on Computational Geometry (EuroCG 2024), which will take place März 13 - 15, 2024, in Ioannina, Greece.

Proceedings Version: https://eurocg2024.math.uoi.gr/data/uploads/paper_56.pdf
Arxiv Version: https://arxiv.org/abs/2402.14552

The article Recognizing well-dominated graphs is coNP-complete by Akanksha Agrawal, Henning Fernau, Philipp Kindermann, Kevin Mann & Uéverton S. Souza has been published in the journal Information Processing Letters.

Journal Version: https://doi.org/10.1016/j.ipl.2023.106419
Arxiv Version: https://arxiv.org/abs/2208.08864​​​​​​​

The article Geometric Thickness of Multigraphs is ∃ℝ-Complete byHenry Förster, Philipp Kindermann, Tillmann Miltzow, Irene Parada, Soeren Terziadis & Birgit Vogtenhuber has been accepted at the conference 16th Latin American Symposium on Theoretical Informatics (LATIN 2024), which takes place March 18 - 22, 2024, in Puerto Varas, Chile.

Proceedings Version: https://doi.org/10.1007/978-3-031-55598-5_22
Arxiv Version: https://arxiv.org/abs/2312.05010

The article On Layered Area-Proportional Rectangle Contact Representations by Carolina Haase & Philipp Kindermann has been accepted at the conference 18th International Conference and Workshops on Algorithms and Computation (WALCOM 2024), which takes place on March 18 - 20, 2024, in Kanazawa, Japan.

Proceedings Version: https://doi.org/10.1007/978-981-97-0566-5_12
Arxiv Version: https://arxiv.org/abs/2311.15057

The article The Computational Complexity of the ChordLink Model by Philipp Kindermann, Jan Sauer & Alexander Wolff has been published in the Journal of Graph Algorithms and Applications.

Journal Version: https://doi.org/10.1016/j.comgeo.2021.101820

The article The st-Planar Edge Completion Problem Is Fixed-Parameter Tractable by Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani & Kirill Simonov has been accepted at the 34th International Symposium on Algorithms and Computation (ISAAC 2023), which takes place on December 03 - 06, 2023, in Kyoto, Japan.

Proceedings Version: https://doi.org/10.4230/LIPIcs.ISAAC.2023.46
Arxiv Version: https://arxiv.org/abs/2309.15454

At the conference 31st International Symposium on Graph Drawing and Network Visualization (GD 2023), taking place September 18 - 22, 2023, in Isola delle Femmine (Palermo), Italy, three articles from our research group have been accepted:

1. Upward and Orthogonal Planarity are W[1]-Hard Parameterized by Treewidth von Bart M. P. Jansen, Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani & Kirill Simonov
   Proceedings Version: https://doi.org/10.1007/978-3-031-49275-4_14
   Arxiv Version: https://arxiv.org/abs/2309.01264
2. Mutual Witness Proximity Drawings of Isomorphic Trees von Carolina Haase, Philipp Kindermann, William J. Lenhart & Giuseppe Liotta
   Proceedings Version: https://doi.org/10.1007/978-3-031-49272-3_21
   Arxiv Version: https://arxiv.org/abs/2309.01463
3. Three Edge-Disjoint Plane Spanning Paths in a Point Set von Philipp Kindermann, Jan Kratochvíl, Giuseppe Liotta & Pavel Valtr
   Proceedings Version: https://doi.org/10.1007/978-3-031-49272-3_22
   Arxiv Version: https://arxiv.org/abs/2306.07237

Giordano Da Lozzo & Philipp Kindermann have edited a special issue of the Journal of Graph Algorithms and Applications with the title Special Issue on Parameterized and Approximation Algorithms in Graph Drawing.

Special Issue: https://jgaa.info/index.php/jgaa/issue/view/issue27.6

The article Splitting Vertices in 2-Layer Graph Drawings by Abu Reyan Ahmed, Patrizio Angelini, Michael A. Bekos, Giuseppe Di Battista, Michael Kaufmann, Philipp Kindermann, Stephen G. Kobourov, Martin Nöllenburg, Antonios Symvonis, Anaïs Villedieu & Markus Wallinger has been published in the journal IEEE Computer Graphics and Applications.

Journal Version: https://doi.org/10.1109/MCG.2023.3264244​​​​​​​
Arxiv Version: https://arxiv.org/abs/2301.10872

The article On mixed linear layouts of series-parallel graphs by Patrizio Angelini, Michael A. Bekos, Philipp Kindermann & Tamara Mchedlidze has been published in the journal Theoretical Computer Science.

Journal Version: https://doi.org/10.1016/j.tcs.2022.09.019
Arxiv Version: https://arxiv.org/abs/2008.10475

At the conference 48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2022), taking place January 15 - 18, 2023, in Nový Smokovec, Slovakia, stattfinden wird, three articles from our research group have been accepted:

1. The Complexity of Finding Tangles von Oksana Firman, Philipp Kindermann, Boris Klemz, Alexander Ravsky, Alexander Wolff & Johannes Zink
   Proceedings Version: https://doi.org/10.1007/978-3-031-23101-8_1
   Arxiv Version: https://arxiv.org/abs/2312.16213
2. Parameterized Approaches to Orthogonal Compaction von Walter Didimo, Siddharth Gupta, Philipp Kindermann, Giuseppe Liotta, Alexander Wolff & Meirav Zehavi
   Proceedings Version: https://doi.org/10.1007/978-3-031-23101-8_8
   Arxiv Version: https://arxiv.org/abs/2210.05019

We have the pleasure of welcoming a new team member: Carolina Haase is starting her doctoral studies today. She wrote her master's thesis on the topic of "On Layered Area-Proportional Rectangle Contact Representations" under the supervision of Philipp Kindermann.

At the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022), taking place on September 13 - 16, 2022, in Tokyo, three articles from our research group have been accepted:

1. Outside-Obstacle Representations with All Vertices on the Outer Face von Oksana Firman, Philipp Kindermann, Jonathan Klawitter, Boris Klemz, Felix Klesen & Alexander Wolff
   Proceedings Version: https://doi.org/10.1007/978-3-031-22203-0_31
   Arxiv Version: https://arxiv.org/abs/2202.13015
2. Morphing Rectangular Duals von Steven Chaplick, Philipp Kindermann, Jonathan Klawitter, Ignaz Rutter, Alexander Wolff
   Proceedings Version: https://doi.org/10.1007/978-3-031-22203-0_28
   Arxiv Version: https://arxiv.org/abs/2112.03040
3. The Rique-Number of Graphs von Michael A. Bekos, Stefan Felsner, Philipp Kindermann, Stephen G. Kobourov, Jan Kratochvíl, Ignaz Rutter
   Proceedings Version: https://doi.org/10.1007/978-3-031-22203-0_27
   Arxiv Version: https://doi.org/10.48550/arXiv.2209.00424

The article Simple algorithms for partial and simultaneous rectangular duals with given contact orientations by Steven Chaplick, Stefan Felsner, Philipp Kindermann, Jonathan Klawitter, Ignaz Rutter & Alexander Wolff has been published in the journalTheoretical Computer Science.

Journal Version: https://doi.org/10.1016/j.tcs.2022.03.031
Arxiv Version: https://arxiv.org/abs/2102.02013

The article Perfect Matchings with Crossings by Oswin Aichholzer, Ruy Fabila Monroy, Philipp Kindermann, Irene Parada, Rosna Paul, Daniel Perz, Patrick Schnider & Birgit Vogtenhuber has been accepted at the 33rd International Workshop on Combinatorial Algorithms (IWOCA 2022), which will take place on June 7 - 9, 2022, in Trier.

Proceedings Version: https://doi.org/10.1007/978-3-031-06678-8_4

The 30th International Symposium on Graph Drawing and Network Visualization will take (hopefully) place in Tokyo, Japan, from September 13 to 16, 2022. As has been tradition since 1994, the symposium will be accompanied by a Graph Drawing Contest, allowing all community members to demonstrate their graph drawing skills in a fun competitive setting. Due to the uncertainty regarding future travel and physical meeting restrictions caused by the Corona virus outbreak, the contest will be either held completely online or in a hybrid format. Details of the exact format of the contest will be announced around the Graph Drawing submission deadline. The contest has two parts: the Creative Topics and the Live Challenge.

1. Live Challenge

Following popular tradition, a live challenge will be held the day before the symposium in a format similar to a typical programming contest. Teams are presented with a collection of challenge graphs and have approximately one hour to submit their highest scoring drawings. This year, the challenge focuses on

        minimizing the planar polyline edge-length ratio on a fixed grid.

Teams may either draw the graphs manually (manual category), or use their own customized tools (automatic category). Remote participation will be possible for both the manual and the automatic category.
The live challenge will take place during the conference.
To solve the instances and submit your solutions, you will be provided with a dedicated tool:

    https://graphdrawingcontest.appspot.com/tool.jsp

Note that the target function changed slightly compared to last year, but the tool has not been updated yet for the new function.
For more details, visit

    http://graphdrawing.org/gdcontest/contest2022/challenge.html

2. Creative Topics

For your entertainment and inspiration, we have composed two nice graphs that you may draw with full artistic freedom.

1. Opera Network
   The data represents a collection of opera performances that took place across Europe between 1775 and 1833. The data was extracted from the RISM database and was offered by Frans Wiering - professor of Utrecht University studing Musicology. There are several possibilities on how a network can be extracted from this data. We leave it to the participants to decide how and whether to model this data set as a network.
2. Aesthetic Experience Network
   The data set represents 8 networks that model an aesthetic experience of the viewers when observing artworks. The analyzed artworks are 8 paintings by Klee, Kandinsky, Mortensen, Miro and Winter. Each of the 14 nodes represents one of the two polarities of an aesthetic effect, and the edges are weighted by conditional dependence relations among aesthetic effects.

In both cases, you may visualize the graph in any way you like. Submissions will be judged on a list of criteria that includes, but is not limited to, readability, aesthetics, novelty, and design quality. The weighting of the criteria might be different for the two graphs. Submissions will be handled through EasyChair. For more details, visit

    http://graphdrawing.org/gdcontest/contest2022/topics.html

Submission deadline: September 05 (23:59 PDT)

3. Awards

We are hoping to be able to award a monetary prize to up to three submissions in each of the four different categories. Details will follow.

We are looking forward to your submissions!

The Graph Drawing Contest Committee,
Philipp Kindermann (chair), Tamara Mchedlidze, and Wouter Meulemans

From June 7th to 9th, we are organizing the 33rd International Workshop on Combinatorial Algorithms (IWOCA'22) in Trier. You can find further information on the conference website.

The article Crossing numbers of beyond-planar graphs by Markus Chimani, Philipp Kindermann, Fabrizio Montecchiani & Pavel Valtr has been published in the journal Theoretical Computer Science.

Journal Version: https://doi.org/10.1016/j.tcs.2021.10.016
Arxiv Version: https://arxiv.org/abs/1908.03153

The article Minimum rectilinear polygons for given angle sequences by William S. Evans, Krzysztof Fleszar, Philipp Kindermann, Noushin Saeedi, Chan-Su Shin & Alexander Wolff has been published in the journal Computational Geometry: Theory & Applications.

Journal Version: https://doi.org/10.1016/j.comgeo.2021.101820
Arxiv Version: https://arxiv.org/abs/1606.06940​​​​​​​​​​​​​

The article One-Bend Drawings of Outerplanar Graphs Inside Simple Polygons by Patrizio Angelini, Philipp Kindermann, Andre Löffler, Lena Schlipf & Antonios Symvonis has been accepted at the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021), which will take place in Tübingen on September 14 - 17, 2021.

Proceedings Version: https://doi.org/10.1007/978-3-030-92931-2_13
Arxiv Version: https://arxiv.org/abs/2108.12321

The article ClusterSets: Optimizing Planar Clusters in Categorical Point Data by Jakob Geiger, Sabine Cornelsen, Jan-Henrik Haunert, Philipp Kindermann, Tamara Mchedlidze, Martin Nöllenburg, Yoshio Okamoto & Alexander Wolff has been published in the journal Computer Graphics Forum.

Journal Version (Open Access): https://doi.org/10.1111/cgf.14322

The article ClusterSets: Optimizing Planar Clusters in Categorical Point Data by Jakob Geiger, Sabine Cornelsen, Jan-Henrik Haunert, Philipp Kindermann, Tamara Mchedlidze, Martin Nöllenburg, Yoshio Okamoto & Alexander Wolff has been accepted at the 23rd Annual Eurographics Visualization Conference (EuroVis 2021), scheduled to take place online on June 14 - 18. The article will be published in the journal Computer Graphics Forum.

Journal Version (Open Access): https://doi.org/10.1111/cgf.14322

The article Extending Partial Representations of Rectangular Duals with Given Contact Orientations by Steven Chaplick, Philipp Kindermann, Jonathan Klawitter, Ignaz Rutter & Alexander Wolff has been accepted at the 12th International Conference on Algorithms and Complexity (CIAC 2021), which will take place online on May 10 - 12, 2021.

Proceedings Version: https://link.springer.com/chapter/10.1007/978-3-030-75242-2_24
Arxiv Version: https://arxiv.org/abs/2102.02013

As of April 1, 2021, Philipp Kindermann was appointed to the junior professorship for Algorithms in the Department IV - Computer Science. The Algorithmics research group focuses on problems across all areas of algorithm development and analysis, particularly in the visualization of graphs, graph algorithms, and computational geometry.