Deutsch Intern
Chair of Computer Science I - Algorithms and Complexity

Dr. Johannes Zink

Johannes Zink

Lehrstuhl für Informatik I
Universität Würzburg
Am Hubland
97074 Würzburg
Deutschland
Building: M4
Room: 1.007
Phone: +49 0 931-31-88038
ORCID: https://orcid.org/0000-0002-7398-718X

  • Theoretical and applied graph drawing
  • Algorithmic problems and their complexity

  • Since October 2024: Postdoc at the Chair for Efficient Algorithms (Prof. S. Kobourov), Technical University of Munich (TUM), Campus Heilbronn
  • May 8, 2023: Defense of my dissertation with the title Algorithms for Drawing Graphs and Polylines with Straight-Line Segments
  • 2018–2024: PhD student (then, Postdoc) at the Chair of Computer Science I (Prof. A. Wolff), University of Würzburg
  • 2015–2017: Master studies in computer science at the University of Würzburg
  • 2012–2015: Bachelor studies in computer science at the University of Würzburg

  • 2024: 1st place in the manual category of the Graph Drawing Live Challenge at the 32nd International Symposium on Graph Drawing and Network Visualization (GD'24) in Vienna, together with Tim Hegemann
  • 2024: Joint PhD prize of the Lower Franconian Memorial Year Foundation for Science and the University of Würzburg for a scientifically outstanding PhD thesis
  • 2023: 1st place in the manual category of the Graph Drawing Live Challenge at the 31st International Symposium on Graph Drawing and Network Visualization (GD'23) in Palermo, together with Tim Hegemann and Florentina Voboril
  • 2023: Prize by the Institute of Computer Science, University of Würzburg for an excellent PhD thesis
  • 2022: 2nd place in the manual category of the Graph Drawing Live Challenge at the 30th International Symposium on Graph Drawing and Network Visualization (GD'22) in Tokyo, together with Felix Klesen
  • 2020: 1st place in the manual category of the Graph Drawing Live Challenge at the 28th International Symposium on Graph Drawing and Network Visualization (GD'20) in Vancouver (online), together with Jonathan Klawitter
  • 2018: 1st place in the manual category of the Graph Drawing Live Challenge at the 26th International Symposium on Graph Drawing and Network Visualization (GD'18) in Barcelona, together with Myroslav Kryven
  • 2015–2017: Deutschlandstipendium (“Germany-scholarship”)
  • 2016: Prize by the Institute of Computer Science, University of Würzburg for excellent academic achievements with an outstanding bachelor thesis (sponsored by denkbares GmbH)

  • Timo Säckl: Automated Drawing of Graphs Using Neural Networks (Bachelor Thesis, in German), 2024
    [pdf]

  • Duy-Khang Tran: Efficiently Computing Alternative Minimum-Bend Orthogonal Representations (Bachelor Thesis, in German), 2023
    [pdf]

  • Nicolai Noah Krapohl: Shelf Restocking via TSP with Precedence Constraints (Master Thesis), 2023

  • Joshua Geis: Upward-Planar Drawings of Outerpaths with Three Slopes (Bachelor Thesis, in German), 2022
    [pdf]

  • Vasil Alistarov: Computing Tangles Using a SAT Solver (Master Project), 2022
    [pdf]

  • Jonas Barth: Clear Drawing of Literary Networks Using the Sugiyama Framework (Bachelor Thesis, in German), 2022
    [pdf]

  • Florian Mittelstädt: About Coloring of Generalized Interval Graphs (Master Thesis, in German), 2022
    [pdf]

  • Lukas Brückner: Orthogonal Drawing as a Coloring Problem in Perfect Graphs (Bachelor Thesis, in German), 2021
    [pdf]

  • Dominique Bau: Algorithm Engineering for a Geometric Set Cover Problem (Master Thesis, in German), 2021
    [pdf]

  • Julian Walter: A Variant of Sugiyama's Algorithm for Undirected Graphs with Port Constraints (Master Thesis, in German), 2020
    [pdf], [slides]

  • Julian Walter: Partial Zooming in Large Network Graphs (Master Project, in German), 2019
    [pdf], [slides]

  • Chris Rettner: Flipped Bitonic st-Orderings of Upward Plane Graphs (Bachelor Thesis), 2019
    [pdf]

  • Program committee member of the conference GD 2023
  • Organization committee member of the conference EuroCG 2020

2024[ to top ]
  • Simultaneous Drawing of Layered Trees. Julia Katheder, Stephen G. Kobourov, Axel Kuckuk, Maximilian Pfister, and Johannes Zink. In Proc. 18th International Conference and Workshops on Algorithms and Computation (WALCOM’24), pp. 47–61. Springer, 2024.
  • Outerplanar and Forest Storyplans. Jiří Fiala, Oksana Firman, Giuseppe Liotta, Alexander Wolff, and Johannes Zink. In Proc. 49th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM’24), pp. 211–225. Springer, 2024.
  • Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines. Martin Koutecký and Johannes Zink. Journal of Scheduling. 2024.
    to appear
  • Creation of a CDE-based data structure for radiotherapeutic decision-making in breast cancer. Fabio Dennstädt, Maximilian Schmalfuss, Johannes Zink, Janna Hastings, Roberto Gaio, Paul Martin Putora, and Nikola Cihoric. In UICC World Cancer Congress (WCC’24). 2024.
    Scientific Abstract
  • Constrained and Ordered Level Planarity Parameterized by the Number of Levels. Vacláv Blažej, Boris Klemz, Felix Klesen, Marie Diana Sieper, Alexander Wolff, and Johannes Zink. In Proc. 40th International Symposium on Computational Geometry (SoCG’24), pp. 21:1–16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024.
  • Morphing Graph Drawings in the Presence of Point Obstacles. Oksana Firman, Tim Hegemann, Boris Klemz, Felix Klesen, Marie Diana Sieper, Alexander Wolff, and Johannes Zink. In Proc. 49th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM’24), pp. 240–254. Springer, 2024.
  • Title and abstract screening for literature reviews using large language models: an exploratory study in the biomedical domain. Fabio Dennstädt, Johannes Zink, Paul Martin Putora, Janna Hastings, and Nikola Cihoric. Systematic Reviews, 13(158). 2024.
  • Algorithms for Drawing Graphs and Polylines with Straight-Line Segments. Johannes Zink. 2024.
    Dissertation, Universität Würzburg
2023[ to top ]
  • Upward Planar Drawings with Three and More Slopes. Jonathan Klawitter and Johannes Zink. Journal of Graph Algorithms and Applications, 27(2), pp. 49–70. 2023.
  • Coloring and Recognizing Mixed Interval Graphs. Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Felix Klesen, Paweł Rzążewski, Alexander Wolff, and Johannes Zink. In Proc. 34th International Symposium on Algorithms and Computation (ISAAC’23), pp. 36:1–36:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023.
  • Optimal Polyline Simplification under the Local Fréchet Distance in (Near-)Quadratic Time. Peter Schäfer, Sabine Storandt, and Johannes Zink. In Proc. 35th Canadian Conference on Computational Geometry (CCCG’23), pp. 225–238. 2023.
  • Tree Drawings with Columns. Jonathan Klawitter and Johannes Zink. In Proc. 31st International Symposium on Graph Drawing and Network Visualization (GD’23), pp. 195–210. Springer, 2023.
  • The Complexity of Finding Tangles. Oksana Firman, Philipp Kindermann, Boris Klemz, Alexander Ravsky, Alexander Wolff, and Johannes Zink. In Proc. 48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM’23), of Lecture Notes in Computer Science, L. Gasieniec (ed.), pp. 3–17. Springer, 2023.
2022[ to top ]
  • Universal Lower Bounds on the Segment Number of Some Classes of Planar Graphs. Jonathan Klawitter, Boris Klemz, Felix Klesen, Stephen Kobourov, Myroslav Kryven, Alexander Wolff, and Johannes Zink. In Proc. 38th Europ. Workshop Comput. Geom. (EuroCG’22), pp. 53:1–6. 2022.
  • The Segment Number: Algorithms and Universal Lower Bounds for Some Classes of Planar Graphs. Ina Goeßmann, Jonathan Klawitter, Boris Klemz, Felix Klesen, Stephen G. Kobourov, Myroslav Kryven, Alexander Wolff, and Johannes Zink. In Proc. 48th Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG’22), M. Bekos, M. Kaufmann (eds.), p. 16 pages. Springer-Verlag, 2022.
  • Coloring Mixed and Directional Interval Graphs. Grzegorz Gutowski, Florian Mittelstädt, Ignaz Rutter, Joachim Spoerhase, Alexander Wolff, and Johannes Zink. In Proc. 30th International Symposium on Graph Drawing and Network Visualization (GD’22), P. Angelini, R. von Hanxleden (eds.). Springer, 2022.
  • Polyline Simplification under the Local Fréchet Distance has Subcubic Complexity. Sabine Storandt and Johannes Zink. In Proc. 38th Europ. Workshop Comput. Geom. (EuroCG’22), pp. 18:1–7. 2022.
  • Layered Drawing of Undirected Graphs with Generalized Port Constraints. Johannes Zink, Julian Walter, Joachim Baumeister, and Alexander Wolff. Computational Geometry: Theory and Applications, 105–106, p. 101886. 2022.
2021[ to top ]
  • Consistent Simplification of Polyline Tree Bundles. Yannick Bosch, Peter Schäfer, Joachim Spoerhase, Sabine Storandt, and Johannes Zink. In Proc. 27th International Computing and Combinatorics Conference (COCOON’21), C.-Y. Chen, W.-K. Hon, L.-J. Hung, C.-W. Lee (eds.), pp. 231–243. Springer, 2021.
  • Upward Planar Drawings with Three Slopes. Jonathan Klawitter and Johannes Zink. In Proc. 37th Europ. Workshop Comput. Geom. (EuroCG’21). 2021.
  • Upward Planar Drawings with Three and More Slopes. Jonathan Klawitter and Johannes Zink. In Proc. 29th International Symposium on Graph Drawing and Network Visualization (GD’21), of Lecture Notes in Computer Science, H. Purchase, I. Rutter (eds.). Springer, 2021.
  • Robust Gateway Placement for Scalable LoRaWAN. Frank Loh, Dominique Bau, Johannes Zink, Alexander Wolff, and Tobias Hoßfeld. In Proc. 13th IFIP Wireless and Mobile Networking Conference (WMNC’21), pp. 71–78. IEEE, 2021.
2020[ to top ]
  • Layered Drawing of Undirected Graphs with Generalized Port Constraints. Julian Walter, Johannes Zink, Joachim Baumeister, and Alexander Wolff. In Proc. 28th International Symposium on Graph Drawing and Network Visualization (GD’20), of Lecture Notes in Computer Science, D. Auber, P. Valtr (eds.). Springer-Verlag, 2020.
  • Recognizing Stick Graphs with and without Length Constraints. Steven Chaplick, Philipp Kindermann, Andre Löffler, Florian Thiele, Alexander Wolff, Alexander Zaft, and Johannes Zink. Journal of Graph Algorithms and Applications, 24(4), pp. 657–681. 2020.
  • Simplification of Polyline Bundles. Joachim Spoerhase, Sabine Storandt, and Johannes Zink. In Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT’20), Vol. 162 of LIPIcs, S. Albers (ed.), pp. 35:1–35:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  • The Complexity of Finding Tangles. Oksana Firman, Stefan Felsner, Philipp Kindermann, Alexander Ravsky, Alexander Wolff, and Johannes Zink. In Proc. 36th Europ. Workshop Comput. Geom. (EuroCG’20). 2020.
  • Erratum: Fast and Simple Horizontal Coordinate Assignment. Ulrik Brandes, Julian Walter, and Johannes Zink. CoRR, abs/2008.01252. 2020.
  • Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines. Martin Koutecký and Johannes Zink. In Proc. 31st International Symposium on Algorithms and Computation (ISAAC’20), of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
2019[ to top ]
  • Computing Optimal Tangles Faster. Oksana Firman, Philipp Kindermann, Alexander Ravsky, Alexander Wolff, and Johannes Zink. In Proc. 35th Europ. Workshop Comput. Geom. (EuroCG’19). 2019.
  • Simplification of Polyline Bundles. Joachim Spoerhase, Sabine Storandt, and Johannes Zink. In Proc. 35th Europ. Workshop Comput. Geom. (EuroCG’19). 2019.
  • Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends. Steven Chaplick, Fabian Lipp, Alexander Wolff, and Johannes Zink. Computational Geometry: Theory and Applications, 84, pp. 50–68. 2019.
  • Computing Height-Optimal Tangles Faster. Oksana Firman, Philipp Kindermann, Alexander Ravsky, Alexander Wolff, and Johannes Zink. In Proc. 27th International Symposium on Graph Drawing and Network Visualization (GD’19), of Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (eds.). Springer-Verlag, 2019.
  • Stick Graphs with Length Constraints. Steven Chaplick, Philipp Kindermann, Andre Löffler, Florian Thiele, Alexander Wolff, Alexander Zaft, and Johannes Zink. In Proc. 27th International Symposium on Graph Drawing and Network Visualization (GD’19), of Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (eds.). Springer-Verlag, 2019.
2018[ to top ]
  • Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends. Steven Chaplick, Fabian Lipp, Alexander Wolff, and Johannes Zink. In Proc. 26th International Symposium on Graph Drawing and Network Visualization (GD’18), of Lecture Notes in Computer Science, T. Biedl, A. Kerren (eds.). Springer-Verlag, 2018.
  • Planar Steiner Orientation is NP-complete. Moritz Beck, Johannes Blum, Myroslav Kryven, Andre Löffler, and Johannes Zink. In Proc. 10th Int. Colloquium on Graph Theory and Combinatorics (ICGT’18). 2018.
  • 1-Bend RAC Drawings of NIC-Planar Graphs in Quadratic Area. Steven Chaplick, Fabian Lipp, Alexander Wolff, and Johannes Zink. In Proc. 34th Europ. Workshop Comput. Geom. (EuroCG’18), M. Korman, W. Mulzer (eds.), pp. 28:1–6. 2018.
2017[ to top ]
  • 1-Planar RAC Drawings with Bends. Johannes Zink. 2017.
    Master Thesis, Universität Würzburg
2016[ to top ]
  • Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition. Fabian Lipp, Alexander Wolff, and Johannes Zink. Algorithms, 9(3), p. article 53, 17 pages. 2016.
2015[ to top ]
  • Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition. Fabian Lipp, Alexander Wolff, and Johannes Zink. In Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD’15), Vol. 9411 of Lecture Notes in Computer Science, E. Di Giacomo, A. Lubiw (eds.), pp. 52–59. Springer, 2015.
  • Beschleunigung von kräftebasierten Graphzeichenalgorithmen mittels wohlseparierten Paardekompositionen (Engl. Speeding up Force-Directed Graph Drawing Algorithms Using Well-Separated Pair Decompositions). Johannes Zink. 2015.
    Bachelor Thesis, Universität Würzburg. (in German)