Institute of Theoretical Informatics, Algorithmics

Publications

Book chapters

  1. Simultaneous Embedding of Planar Graphs.
    In: Handbook of Graph Drawing and Visualization, pages 349–381. CRC Press, 2013.
    Joint work with Stephen G. Kobourov and Ignaz Rutter.

Journal articles

  1. How to Draw a Planarization.
    Journal of Graph Algorithms and Applications, 23(4):653–682, 2019.
    Joint work with Marcel Radermacher and Ignaz Rutter.
    [ html ]
  2. Local and union boxicity.
    Discrete Mathematics, 341(5):1307–1315, May 2018.
    Joint work with Peter Stumpf and Torsten Ueckerdt.
    [ html ]
  3. Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths.
    Journal of Computational Geometry, 9(1):24–70, 2018.
    Joint work with Moritz Baum, Andreas Gemsa, Ignaz Rutter, and Franziska Wegner.
    [ html ]
  4. Optimal Orthogonal Graph Drawing with Convex Bend Costs.
    ACM Transactions on Algorithms, 12(3):33:1–33:30, June 2016.
    Joint work with Ignaz Rutter and Dorothea Wagner.
    [ html ]
  5. Orthogonal Graph Drawing with Inflexible Edges.
    Computational Geometry: Theory and Applications, 2016.
    To appear.
    Joint work with Sebastian Lehmann and Ignaz Rutter.
  6. A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem.
    Theoretical Computer Science, 609:306–315, 2016.
    Joint work with Ignaz Rutter.
    [ html ]
  7. Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems.
    ACM Transactions on Algorithms, 12(2):16, 2016.
    Joint work with Ignaz Rutter.
  8. Disconnectivity and relative positions in simultaneous embeddings.
    Computational Geometry: Theory and Applications, 48(6):459–478, 2015.
    Joint work with Ignaz Rutter.
    [ html ]
  9. Testing Mutual Duality of Planar Graphs.
    International Journal of Computational Geometry and Applications, 24(4):325–346, 2014.
    Joint work with Patrizio Angelini and Ignaz Rutter.
  10. Orthogonal Graph Drawing with Flexibility Constraints.
    Algorithmica, 68(4):859–885, 2014.
    Joint work with Marcus Krug, Ignaz Rutter, and Dorothea Wagner.
    [ html ]

Conference articles

  1. 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, Emil Dohse, and Paul Jungeblut.
    [ html | pdf ]
  2. How to Draw a Planarization.
    In: Proceedings of the 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'17), Lecture Notes in Computer Science, pages 295–308. Springer, 2017.
    Joint work with Marcel Radermacher and Ignaz Rutter.
    [ html | pdf ]
  3. Computing Minimum-Link Separating Polygons in Practice.
    In: Proceedings of the 32nd European Workshop on Computational Geometry (EuroCG'16), 2016.
    Joint work with Moritz Baum, Andreas Gemsa, Ignaz Rutter, and Franziska Wegner.
    [ pdf ]
  4. Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths.
    In: Proceedings of the 24th Annual European Symposium on Algorithms (ESA'16), volume 57 of Leibniz International Proceedings in Informatics, pages 7:1–7:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
    Joint work with Moritz Baum, Andreas Gemsa, Ignaz Rutter, and Franziska Wegner.
    [ html | pdf ]
  5. 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, Ignaz Rutter, Torsten Ueckerdt, and Alexander Wolff.
    [ html ]
  6. Orthogonal Graph Drawing with Inflexible Edges.
    In: Proceedings of the 9th Conference on Algorithms and Complexity (CIAC'15), volume 9079 of Lecture Notes in Computer Science. Springer, 2015.
    To appear.
    Joint work with Sebastian Lehmann and Ignaz Rutter.
    [ html ]
  7. Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model.
    In: Proceedings of the 22nd Annual European Symposium on Algorithms (ESA'14), volume 8737 of Lecture Notes in Computer Science, pages 161–172. Springer, September 2014.
    Joint work with Guido Brückner and Ignaz Rutter.
    [ html ]
  8. PIGRA – A Tool for Pixelated Graph Representations.
    In: Proceedings of the 22nd International Symposium on Graph Drawing (GD'14), volume 8871 of Lecture Notes in Computer Science, pages 513–514. Springer, 2014.
    Poster abstract.
    Joint work with Fabian Klute, Benjamin Niedermann, and Martin Nöllenburg.
    [ pdf ]
  9. A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem.
    In: Proceedings of the 22nd International Symposium on Graph Drawing (GD'14), volume 8871 of Lecture Notes in Computer Science, pages 440–451. Springer, 2014.
    Joint work with Ignaz Rutter.
  10. Testing Mutual Duality of Planar Graphs.
    In: Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC'13), volume 8283 of Lecture Notes in Computer Science, pages 350–360. Springer, 2013.
    Joint work with Patrizio Angelini and Ignaz Rutter.
  11. Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings.
    In: Proceedings of the 21st International Symposium on Graph Drawing (GD'13), volume 8242 of Lecture Notes in Computer Science, pages 460–471. Springer, 2013.
    Full version available at http://arxiv.org/abs/1308.6778.
    Joint work with Therese Biedl, Benjamin Niedermann, Martin Nöllenburg, Roman Prutkin, and Ignaz Rutter.
    [ html | pdf ]
  12. Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices.
    In: Proceedings of the 21st International Symposium on Graph Drawing (GD'13), volume 8242 of Lecture Notes in Computer Science, pages 220–231. Springer, 2013.
    Joint work with Annette Karrer and Ignaz Rutter.
  13. Disconnectivity and Relative Positions in Simultaneous Embeddings.
    In: Proceedings of the 20th International Symposium on Graph Drawing (GD'12), volume 7704 of Lecture Notes in Computer Science, pages 31–42. Springer, 2013.
    Joint work with Ignaz Rutter.
  14. Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems.
    In: Proceedings of the 24th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA'13), pages 1030–1043. SIAM, 2013.
    Joint work with Ignaz Rutter.
  15. Optimal Orthogonal Graph Drawing with Convex Bend Costs.
    In: Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP'13), volume 7965 of Lecture Notes in Computer Science, pages 184–195. Springer, 2013.
    Joint work with Ignaz Rutter and Dorothea Wagner.
  16. Orthogonal Graph Drawing with Flexibility Constraints.
    In: Proceedings of the 18th International Symposium on Graph Drawing (GD'10), volume 6502 of Lecture Notes in Computer Science, pages 92–104. Springer, 2011.
    Joint work with Marcus Krug, Ignaz Rutter, and Dorothea Wagner.
    [ html ]

Master's Thesis

  1. Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems.
    Master's thesis, Karlsruher Institut für Technologie (KIT), September 2011.
    [ pdf ]

Technical reports

  1. Scalable Isocontour Visualization in Road Networks via Minimum-Link Paths.
    Technical Report 1602.01777, ArXiv e-prints, 2016.
    Joint work with Moritz Baum, Andreas Gemsa, Ignaz Rutter, and Franziska Wegner.
    [ html | pdf ]
  2. Orthogonal Graph Drawing with Flexibility Constraints.
    Technical Report 2010-18, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2010.
    Joint work with Marcus Krug, Ignaz Rutter, and Dorothea Wagner.
    [ html ]