Institute of Theoretical Informatics, Algorithmics

Publications

Journal articles

  1. Primal-Dual Cops and Robber.
    Computing in Geometry and Topology, 3(2):42:1–42:12, 2024.
    Joint work with Minh Tuan Ha, Torsten Ueckerdt, and Pawel Żyliński.
    [ html | pdf ]
  2. The Product Structure of Squaregraphs.
    Journal of Graph Theory, 105(2):179–191, 2023.
    Joint work with Robert Hickingbotham, Laura Merker, and David R. Wood.
    [ html | pdf ]
  3. The Complexity of the Hausdorff Distance.
    Discrete and Computational Geometry, 71(1):177–213, 2023.
    Joint work with Linda Kleist and Tillmann Miltzow.
    [ html | pdf ]
  4. A Sublinear Bound on the Page Number of Upward Planar Graphs.
    SIAM Journal on Discrete Mathematics, 37(4):2312–2331, 2023.
    Joint work with Laura Merker and Torsten Ueckerdt.
    [ html | pdf ]
  5. Multilevel Planarity.
    Journal of Graph Algorithms and Applications, 25(1):151–170, January 2021.
    Joint work with Lukas Barth, Guido Brückner, and Marcel Radermacher.
    [ html | pdf ]

Conference articles

  1. Recognition Complexity of Subgraphs of 2- and 3-Connected Planar Cubic Graphs.
    In: Proceedings of the 40th European Workshop on Computational Geometry (EuroCG 2024), 2024.
    Joint work with Miriam Goetze and Torsten Ueckerdt.
    [ html | pdf ]
  2. On the Complexity of Lombardi Graph Drawing.
    In: Proceedings of the 31th International Symposium on Graph Drawing and Network Visualization (GD 2023), volume 14465 of Lecture Notes in Computer Science, pages 180–194. Springer, 2024.
    [ html | pdf ]
  3. Recognizing Unit Disk Graphs in Hyperbolic Geometry is ER-Complete.
    In: Proceedings of the 39th European Workshop on Computational Geometry (EuroCG 2023), pages 35:1–35:8, 2023.
    Joint work with Nicholas Bieker, Thomas Bläsius, and Emil Dohse.
    [ html | pdf ]
  4. Training Fully Connected Neural Networks is ER-Complete.
    In: Advances in Neural Information Processing Systems 36 (NeurIPS 2023), 2023.
    Joint work with Daniel Bertschinger, Christoph Hertrich, Tillmann Miltzow, and Simon Weber.
    [ html | pdf ]
  5. Primal-Dual Cops and Robber.
    In: Proceedings of the 39th European Workshop on Computational Geometry (EuroCG 2023), pages 58:1–58:6, 2023.
    Joint work with Minh Tuan Ha and Torsten Ueckerdt.
    [ html | pdf ]
  6. Directed Acyclic Outerplanar Graphs Have Constant Stack Number.
    In: Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2023), pages 1937–1952. IEEE, 2023.
    Joint work with Laura Merker and Torsten Ueckerdt.
    [ html | pdf ]
  7. Cops and Robber - When Capturing is not Surrounding.
    In: Proceedings of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2023), volume 14093 of Lecture Notes in Computer Science, pages 403–416. Springer, 2023.
    Joint work with Samuel Schneider and Torsten Ueckerdt.
    [ html | pdf ]
  8. Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs.
    In: Proceedings of the 30th Annual European Symposium on Algorithms (ESA 2022), volume 244 of Leibniz International Proceedings in Informatics, pages 62:1–62:15, 2022.
    Joint work with Miriam Goetze and Torsten Ueckerdt.
    [ html | pdf ]
  9. The Complexity of the Hausdorff Distance.
    In: 38th International Symposium on Computational Geometry (SoCG 2022), volume 224 of Leibniz International Proceedings in Informatics, pages 48:1–48:17, 2022.
    Joint work with Linda Kleist and Tillmann Miltzow.
    [ html | pdf ]
  10. The Complexity of the Hausdorff Distance.
    In: Proceedings of the 38th European Workshop on Computational Geometry (EuroCG 2022), pages 1:1–1:7, 2022.
    Joint work with Linda Kleist and Tillmann Miltzow.
    [ pdf ]
  11. A Sublinear Bound on the Page Number of Upward Planar Graphs.
    In: Proceedings of the 2022 Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 963–978. SIAM, 2022.
    Joint work with Laura Merker and Torsten Ueckerdt.
    [ html | pdf ]
  12. Edge Guarding Plane Graphs.
    In: Proceedings of the 36th European Workshop on Computational Geometry (EuroCG 2020), pages 178–183, 2020.
    Joint work with Torsten Ueckerdt.
    [ pdf ]
  13. Guarding Quadrangulations and Stacked Triangulations with Edges.
    In: Proceedings of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2020), volume 12301 of Lecture Notes in Computer Science, pages 14–26. Springer, 2020.
    Joint work with Torsten Ueckerdt.
    [ pdf ]
  14. Multilevel Planarity.
    In: Proceedings of the 13th Conference and Workshops on Algorithms and Computation (WALCOM 2019), volume 11355 of Lecture Notes in Computer Science, pages 219–231. Springer, 2019.
    Joint work with Lukas Barth, Guido Brückner, and Marcel Radermacher.
    [ html | pdf ]

Dissertation

  1. Capturing the Computational Complexity of Geometric Problems by the First-Order Theory of the Reals.
    PhD thesis, Karlsruher Institut für Technologie (KIT), May 2024.
    [ html | pdf ]

Master's Thesis

  1. Edge Guarding Plane Graphs.
    Master's thesis, October 2019.
    Advisor: Torsten Ueckerdt.
    [ pdf ]
  2. On Interval Planar Graphs.
    Bachelor's thesis, October 2017.
    Advisors: Lukas Barth, Guido Brückner, Marcel Radermacher.
    [ pdf ]