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, Paul Jungeblut, and Pawel Żyliński.
    [ html | pdf ]
  2. A Sublinear Bound on the Page Number of Upward Planar Graphs.
    SIAM Journal on Discrete Mathematics, 37(4):2312–2331, 2023.
    Joint work with Paul Jungeblut and Laura Merker.
    [ html | pdf ]
  3. On covering numbers, Young diagrams, and the local dimension of posets.
    SIAM Journal on Discrete Mathematics, 35(2):915–927, 2021.
    Joint work with Gábor Damásdi, Stefan Felsner, António Girão, Balázs Keszegh, David Lewis, and Dániel T. Nagy.
    [ html ]
  4. The interval number of a planar graph is at most three.
    Journal of Combinatorial Theory Series B, 146:61–67, 2021.
    Joint work with Guillaume Guégan, Kolja Knauer, and Jonathan Rollin.
    [ html ]
  5. The number of crossings in multigraphs with no empty lens.
    Journal of Graph Algorithms and Applications, 25(1):383–396, 2021.
    Joint work with Michael Kaufmann, János Pach, and Géza Tóth.
    [ html ]
  6. Planar graphs have bounded queue-number.
    Journal of the ACM, 67(4):1–38, August 2020.
    Joint work with Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, and David R. Wood.
    [ html ]
  7. Four pages are indeed necessary for planar graphs.
    Journal of Computational Geometry, 11(1):332–353, 2020.
    Joint work with Michael Kaufmann, Michael Bekos, Fabian Klute, Sergey Pupyrev, and Chrysanthi Raftopoulou.
    [ html ]
  8. Induced and weak induced arboricities.
    Discrete Mathematics, 342(2):511–519, 2019.
    Joint work with Maria Axenovich, Philip Dörr, and Jonathan Rollin.
    [ html ]
  9. Planar Ramsey graphs.
    The Electronic Journal of Combinatorics, 26(4), 2019.
    Joint work with Maria Axenovich, Ursula Schade, and Carsten Thomassen.
    [ html ]
  10. Planar graphs of bounded degree have bounded queue number.
    SIAM Journal on Computing, 48(5):1487–1502, 2019.
    Joint work with Michael Bekos, Henry Förster, Martin Gronemann, Tamara Mchedlidze, Fabrizio Montecchiani, and Chrysanthi Raftopoulou.
    [ html ]
  11. Decomposing 4-connected planar triangulations into two trees and one path.
    Journal of Combinatorial Theory Series B, 134:88–109, 2019.
    Joint work with Kolja Knauer.
    [ html ]
  12. Local and union boxicity.
    Discrete Mathematics, 341(5):1307–1315, May 2018.
    Joint work with Thomas Bläsius and Peter Stumpf.
    [ html ]
  13. The k-strong induced arboricity of a graph.
    European Journal of Combinatorics, 67:1–20, January 2018.
    Joint work with Maria Axenovich, Daniel Gonçalves, and Jonathan Rollin.
    [ html ]
  14. On the Maximum Crossing Number.
    Journal of Graph Algorithms and Applications, 22(1):67–87, January 2018.
    Joint work with Markus Chimani, Stefan Felsner, Stephen G. Kobourov, Pavel Valtr, and Alexander Wolff.
    [ html ]
  15. Conditions on Ramsey Nonequivalence.
    Journal of Graph Theory, 86(2):159–192, October 2017.
    Joint work with Maria Axenovich and Jonathan Rollin.
    [ html ]
  16. Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths.
    Journal of Graph Theory, 85(3):601–618, July 2017.
    Joint work with Maria Axenovich and Pascal Weiner.
    [ html ]
  17. Chromatic number of ordered graphs with forbidden ordered subgraphs.
    Combinatorica, 2017.
    Joint work with Maria Axenovich and Jonathan Rollin.
    [ html ]
  18. The chromatic number of ordered graphs with constrained conflict graphs.
    The Australasian Journal of Combinatorics, 69(1):74–104, 2017.
    Joint work with Maria Axenovich and Jonathan Rollin.
    [ html ]
  19. Intersection graphs of L-shapes and segments in the plane.
    Discrete Applied Mathematics, 206:48–55, June 2016.
    Joint work with Stefan Felsner, Kolja Knauer, and George B. Mertzios.
    [ html ]
  20. Spectrum of Mixed Bi-uniform Hypergraphs.
    Graphs and Combinatorics, 32(2):453–461, March 2016.
    Joint work with Maria Axenovich and Enrica Cherubini.
    [ html ]
  21. Three ways to cover a graph.
    Discrete Mathematics, 339(2):745–758, February 2016.
    Joint work with Kolja Knauer.
    [ html ]
  22. Density of range capturing hypergraphs.
    Journal of Computational Geometry, 7(1), 2016.
    Joint work with Maria Axenovich.
    [ html ]
  23. A Note on Concurrent Graph Sharing Games.
    Integers, 16, 2016.
    Joint work with Steven Chaplick, Piotr Micek, and Veit Wiechert.
    [ html | pdf ]
  24. Playing weighted Tron on trees.
    Discrete Mathematics, 338(12):2341–2347, December 2015.
    Joint work with Daniel Hoske, Jonathan Rollin, and Stefan Walzer.
    [ html ]
  25. On the bend-number of planar and outerplanar graphs.
    Discrete Applied Mathematics, 179:109–119, December 2014.
    Joint work with Daniel Heldt and Kolja Knauer.
    [ html ]
  26. Twins in graphs.
    European Journal of Combinatorics, 39:188–197, July 2014.
    Joint work with Maria Axenovich and Ryan Martin.
    [ html ]
  27. Edge-intersection graphs of grid paths: The bend-number.
    Discrete Applied Mathematics, 167:144–162, April 2014.
    Joint work with Daniel Heldt and Kolja Knauer.
    [ html ]
  28. Online and size anti-Ramsey numbers.
    Journal of Combinatorics, 5(1):87–114, 2014.
    Joint work with Maria Axenovich, Kolja Knauer, and Judith Stumpp.
    [ html ]
  29. Packing polyominoes clumsily.
    Computational Geometry, 47(1):52–60, January 2014.
    Joint work with Maria Axenovich and Stefan Walzer.
    [ html ]
  30. Making Octants Colorful and Related Covering Decomposition Problems.
    SIAM Journal on Discrete Mathematics, 28(4):1948–1959, 2014.
    Joint work with Jean Cardinal, Kolja Knauer, and Piotr Micek.
    [ html ]
  31. Computing Cartograms with Optimal Complexity.
    Discrete and Computational Geometry, 50(3):784–810, October 2013.
    Joint work with Md. Jawaherul Alam, Therese Biedl, Stefan Felsner, Michael Kaufmann, and Stephen G. Kobourov.
    [ html ]
  32. Making triangles colorful.
    Journal of Computational Geometry, 4(1), 2013.
    Joint work with Jean Cardinal, Kolja Knauer, and Piotr Micek.
    [ html ]
  33. Planar Graphs as VPG-Graphs.
    Journal of Graph Algorithms and Applications, 17(4):475–494, 2013.
    Joint work with Steven Chaplick.
    [ html ]
  34. How to eat 4/9 of a pizza.
    Discrete Mathematics, 311(16):1635–1645, August 2011.
    Joint work with Kolja Knauer and Piotr Micek.
    [ html ]
  35. Points with large quadrant depth.
    Journal of Computational Geometry, 2(1), 2011.
    Joint work with Roel Apfelbaum, Itay Ben-Dan, Stefan Felsner, Tillmann Miltzow, Rom Pinchasi, and Ran Ziv.
    [ html ]
  36. Cycle bases in graphs characterization, algorithms, complexity, and applications.
    Computer Science Review, 3(4):199–243, November 2009.
    Joint work with Telikepalli Kavitha, Christian Liebchen, Kurt Mehlhorn, Dimitrios Michail, Romeo Rizzi, and Katharina A. Zweig.
    [ html ]

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 Paul Jungeblut.
    [ html | pdf ]
  2. 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 Paul Jungeblut.
    [ html | pdf ]
  3. 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 Paul Jungeblut and Laura Merker.
    [ html | pdf ]
  4. 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 Paul Jungeblut and Samuel Schneider.
    [ html | pdf ]
  5. 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 Paul Jungeblut.
    [ html | pdf ]
  6. 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 Paul Jungeblut and Laura Merker.
    [ html | pdf ]
  7. Linear Layouts of Complete Graphs.
    In: Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD'21), Lecture Notes in Computer Science, pages 257–270. Springer, 2021.
    Joint work with Stefan Felsner, Laura Merker, and Pavel Valtr.
    [ html | pdf ]
  8. An Evaluation of Graph Algorithms for the Wind Farm Cable Layout Problem under Electrical Aspects.
    In: Proceedings of the 56th International Universities Power Engineering Conference, 2021.
    Joint work with Sascha Gritzbach, Hüseyin Çakmak, Pascal Mehnert, and Veit Hagenmeyer.
    [ html ]
  9. Plattenbauten: Touching rectangles in space.
    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 161–173. Springer, 2020.
    Joint work with Stefan Felsner and Kolja Knauer.
    [ html ]
  10. Edge Guarding Plane Graphs.
    In: Proceedings of the 36th European Workshop on Computational Geometry (EuroCG 2020), pages 178–183, 2020.
    Joint work with Paul Jungeblut.
    [ pdf ]
  11. 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 Paul Jungeblut.
    [ pdf ]
  12. The Local Queue Number of Graphs with Bounded Treewidth.
    In: Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD'20), Lecture Notes in Computer Science, pages 26–39. Springer, 2020.
    Joint work with Laura Merker.
    [ html | pdf ]
  13. Engineering Negative Cycle Canceling for Wind Farm Cabling.
    In: Proceedings of the 27th Annual European Symposium on Algorithms (ESA'19), volume 144 of Leibniz International Proceedings in Informatics, pages 55:1–55:16, September 2019.
    Joint work with Sascha Gritzbach, Dorothea Wagner, Franziska Wegner, and Matthias Wolf.
    [ html ]
  14. Planar graphs of bounded degree have constant queue number.
    In: Proceedings of the 51st Annual ACM SIGACT Symposium on the Theory of Computing (STOC'19), pages 176–184. ACM Press, 2019.
    Joint work with Michael Bekos, Henry Förster, Martin Gronemann, Tamara Mchedlidze, Fabrizio Montecchiani, and Chrysanthi Raftopoulou.
    [ html ]
  15. Planar graphs have bounded queue-number.
    In: Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS'19), pages 862–875. IEEE, 2019.
    Joint work with Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, and David R. Wood.
    [ html ]
  16. Local and Union Page Numbers.
    In: Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD'19), Lecture Notes in Computer Science, pages 447–459. Springer, 2019.
    Joint work with Laura Merker.
    [ html | pdf ]
  17. Beyond-planarity: Turán-type results for non-planar bipartite graphs.
    In: 29th International Symposium on Algorithms and Computation (ISAAC'18), volume 123 of Leibniz International Proceedings in Informatics, pages 28:1–28:13, 2018.
    Joint work with Patrizio Angelini, Michael Bekos, Michael Kaufmann, and Maximilian Pfister.
    [ html ]
  18. On the Maximum Crossing Number.
    In: Proceedings of the 28th International Workshop on Combinatorial Algorithms (IWOCA'17), volume 10765 of Lecture Notes in Computer Science, pages 61–74. Springer, 2018.
    Joint work with Markus Chimani, Stefan Felsner, Stephen G. Kobourov, Pavel Valtr, and Alexander Wolff.
    [ html ]
  19. Towards negative cycle canceling in wind farm cable layout optimization.
    In: Proceedings of the 7th DACH+ Conference on Energy Informatics, volume 1 (Suppl 1). Springer, 2018.
    Joint work with Sascha Gritzbach, Dorothea Wagner, Franziska Wegner, and Matthias Wolf.
    [ html ]
  20. The queue-number of posets of bounded width or height.
    In: Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD'18), Lecture Notes in Computer Science, pages 200–212. Springer, 2018.
    Joint work with Kolja Knauer and Piotr Micek.
    [ html ]
  21. The number of crossings in multigraphs with no empty lens.
    In: Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD'18), Lecture Notes in Computer Science, pages 242–254. Springer, 2018.
    Joint work with Michael Kaufmann, János Pach, and Géza Tóth.
    [ html ]
  22. Pixel and Voxel Representations of Graphs.
    In: Proceedings of the 23rd International Symposium on Graph Drawing (GD'15), Lecture Notes in Computer Science, pages 472–486. Springer, 2015.
    Joint work with Md. Jawaherul Alam, Thomas Bläsius, Ignaz Rutter, and Alexander Wolff.
    [ html ]
  23. Contact Graphs of Circular Arcs.
    In: Algorithms and Data Structures, 14th International Symposium (WADS'15), Lecture Notes in Computer Science, pages 1–13. Springer, 2015.
    Joint work with Md. Jawaherul Alam, David Eppstein, Michael Kaufmann, Stephen G. Kobourov, Sergey Pupyrev, and André Schulz.
    [ html ]
  24. Contact Representations of Graphs in 3D.
    In: Algorithms and Data Structures, 14th International Symposium (WADS'15), Lecture Notes in Computer Science, pages 14–27. Springer, 2015.
    Joint work with Md. Jawaherul Alam, William Evans, Stephen G. Kobourov, Sergey Pupyrev, and Jackson Toeniskoetter.
    [ html ]
  25. On-line Coloring between Two Lines.
    In: Proceedings of the 31st International Symposium on Computational Geometry (SoCG 2015), Leibniz International Proceedings in Informatics, pages 630–641, 2015.
    Joint work with Stefan Felsner and Piotr Micek.
    [ html ]
  26. Combinatorial Properties of Triangle-Free Rectangle Arrangements and the Squarability Problem.
    In: Proceedings of the 23rd International Symposium on Graph Drawing (GD'15), Lecture Notes in Computer Science, pages 231–244. Springer, 2015.
    Joint work with Jonathan Klawitter and Martin Nöllenburg.
    [ html ]
  27. Graphs admitting d-realizers: spanning-tree-decompositions and box-representations.
    In: Proceedings of the 30th European Workshop on Computational Geometry (EuroCG'14), March 2014.
    Joint work with William Evans, Stefan Felsner, and Stephen G. Kobourov.
    [ pdf ]
  28. Semantic Word Cloud Representations: Hardness and Approximation Algorithms.
    In: Proceedings of the 11th Latin American Symposium on Theoretical Informatics (LATIN'14), volume 8392 of Lecture Notes in Computer Science, pages 514–525. Springer, 2014.
    Full version available at http://arxiv.org/abs/1311.4778.
    Joint work with Lukas Barth, Sara Irina Fabrikant, Stephen G. Kobourov, Anna Lubiw, Martin Nöllenburg, Yoshio Okamoto, Sergey Pupyrev, Claudio Squarcella, and Alexander Wolff.
    [ html | pdf ]
  29. Making Octants Colorful and Related Covering Decomposition Problems Making Octants Colorful and Related Covering Decomposition Problems.
    In: Proceedings of the 25th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA'14), pages 1424–1432. SIAM, 2014.
    Joint work with Jean Cardinal, Kolja Knauer, and Piotr Micek.
    [ html ]
  30. Intersection Graphs of L-Shapes and Segments in the Plane.
    In: Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS'14), Lecture Notes in Computer Science, pages 299–310. Springer, 2014.
    Joint work with Stefan Felsner, Kolja Knauer, and George B. Mertzios.
    [ html ]
  31. Coloring Hypergraphs Induced by Dynamic Point Sets and Bottomless Rectangles.
    In: Algorithms and Data Structures, 13th International Symposium (WADS'13), volume 8037 of Lecture Notes in Computer Science, pages 73–84. Springer, 2013.
    Joint work with Andrei Asinowski, Jean Cardinal, Nathann Cohen, Sébastien Collette, Thomas Hackl, Michael Hoffmann, Kolja Knauer, Stefan Langerman, Michal Lasoń, Piotr Micek, and Günter Rote.
    [ html ]
  32. Equilateral L-Contact Graphs.
    In: Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'13), Lecture Notes in Computer Science, pages 139–151. Springer, 2013.
    Joint work with Steven Chaplick and Stephen G. Kobourov.
    [ html ]
  33. Planar Graphs as VPG-Graphs.
    In: Proceedings of the 20th International Symposium on Graph Drawing (GD'12), volume 7704 of Lecture Notes in Computer Science, pages 174–186. Springer, 2013.
    Joint work with Steven Chaplick.
    [ html ]
  34. Convex-Arc Drawings of Pseudolines.
    In: Proceedings of the 21st International Symposium on Graph Drawing (GD'13), volume 8242 of Lecture Notes in Computer Science, pages 522–523. Springer, 2013.
    Poster presentation.
    Joint work with David Eppstein, Mereke van Garderen, and Bettina Speckmann.
    [ pdf ]
  35. Non-crossing Connectors in the Plane.
    In: Proceedings of the 10th annual conference on Theory and applications of models of computation, Lecture Notes in Computer Science, pages 108–120. Springer, 2013.
    Joint work with Jan Kratochvíl.
    [ html ]
  36. Combinatorial and Geometric Properties of Planar Laman Graphs Combinatorial and Geometric Properties of Planar Laman Graphs.
    In: Proceedings of the 24th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA'13), pages 1668–1678. SIAM, 2013.
    Joint work with Stephen G. Kobourov and Kevin Verbeek.
    [ html ]
  37. Computing cartograms with optimal complexity.
    In: Proceedings of the 28th Annual ACM Symposium on Computational Geometry (SoCG'12), pages 21–30. ACM Press, 2012.
    Joint work with Md. Jawaherul Alam, Therese Biedl, Stefan Felsner, Michael Kaufmann, and Stephen G. Kobourov.
    [ html ]
  38. On the Bend-Number of Planar and Outerplanar Graphs.
    In: Proceedings of the 10th Latin American Symposium on Theoretical Informatics (LATIN'12), Lecture Notes in Computer Science, pages 458–469, 2012.
    Joint work with Daniel Heldt and Kolja Knauer.
    [ html ]
  39. Points with large quadrant-depth.
    In: Proceedings of the 26th Annual ACM Symposium on Computational Geometry (SoCG'10), pages 358–364. ACM Press, 2010.
    Joint work with Roel Apfelbaum, Itay Ben-Dan, Stefan Felsner, Rom Pinchasi, Tillmann Miltzow, and Ran Ziv.
    [ html ]