Institut für Theoretische Informatik, Algorithmik

Veröffentlichungen

Tagungsbände

  1. Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD'21).
    Lecture Notes in Computer Science. Springer, 2021.
    Jointly edited with Helen C. Purchase.

Buchbeiträge

  1. Simultaneous Embedding of Planar Graphs.
    In: Handbook of Graph Drawing and Visualization, pages 349–381. CRC Press, 2013.
    Joint work with Thomas Bläsius and Stephen G. Kobourov.
  2. The Many Faces of Planarity – Matching, Augmentation, and Embedding Algorithms for Planar Graphs –.
    In: Ausgezeichnete Informatikdissertationen 2011, volume D-12 of Lecture Notes in Informatics, pages 161–170. 2012.
    [ pdf ]

Artikel in Zeitschriften

  1. Drawing Clustered Planar Graphs on Disk Arrangements.
    Journal of Graph Algorithms and Applications, 24(2):105–131, 2020.
    Joint work with Tamara Mchedlidze, Marcel Radermacher, and Nina Zimbel.
    [ html ]
  2. Geometric Heuristics for Rectilinear Crossing Minimization.
    ACM Journal of Experimental Algorithmics, 24(1):1.12:1–1.12:21, July 2019.
    Joint work with Marcel Radermacher, Klara Reichard, and Dorothea Wagner.
    [ html | pdf ]
  3. How to Draw a Planarization.
    Journal of Graph Algorithms and Applications, 23(4):653–682, 2019.
    Joint work with Thomas Bläsius and Marcel Radermacher.
    [ html ]
  4. 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, Thomas Bläsius, Andreas Gemsa, and Franziska Wegner.
    [ html ]
  5. Aligned Drawings of Planar Graphs.
    Journal of Graph Algorithms and Applications, 22(3):401–429, 2018.
    Joint work with Tamara Mchedlidze and Marcel Radermacher.
    [ html ]
  6. Extending Partial Representations of Proper and Unit Interval Graphs.
    Algorithmica, 77(4):1071–1104, 2017.
    Joint work with Pavel Klavík, Jan Kratochvíl, Yota Otachi, Toshiki Saitoh, Maria Saumell, and Tomás Viskočil.
  7. Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions.
    International Journal of Computational Geometry and Applications, 27(1–2):121–158, 2017.
    Special issue on selected papers from ISAAC�15.
    Joint work with Martin Nöllenburg and Roman Prutkin.
  8. Multi-Sided Boundary Labeling.
    Algorithmica, 76(1):225–258, September 2016.
    Joint work with Philipp Kindermann, Benjamin Niedermann, Marcus Schaefer, André Schulz, and Alexander Wolff.
    [ html ]
  9. Optimal Orthogonal Graph Drawing with Convex Bend Costs.
    ACM Transactions on Algorithms, 12(3):33:1–33:30, June 2016.
    Joint work with Thomas Bläsius and Dorothea Wagner.
    [ html ]
  10. Search-space size in contraction hierarchies.
    Theoretical Computer Science, 645:112–127, 2016.
    Joint work with Reinhard Bauer, Tobias Columbus, and Dorothea Wagner.
  11. Orthogonal Graph Drawing with Inflexible Edges.
    Computational Geometry: Theory and Applications, 2016.
    To appear.
    Joint work with Thomas Bläsius and Sebastian Lehmann.
  12. A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem.
    Theoretical Computer Science, 609:306–315, 2016.
    Joint work with Thomas Bläsius.
    [ html ]
  13. Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems.
    ACM Transactions on Algorithms, 12(2):16, 2016.
    Joint work with Thomas Bläsius.
  14. Consistent labeling of rotating maps.
    Journal of Computational Geometry, 7(1):308–331, 2016.
    Joint work with Andreas Gemsa and Martin Nöllenburg.
  15. Evaluation of Labeling Strategies for Rotating Maps.
    ACM Journal of Experimental Algorithmics, 2016.
    Special Issue of SEA'14. To appear.
    Joint work with Andreas Gemsa and Martin Nöllenburg.
  16. Extending Convex Partial Drawings of Graphs.
    Algorithmica, 2016.
    Article in press.
    Joint work with Tamara Mchedlidze and Martin Nöllenburg.
    [ html ]
  17. On Self-Approaching and Increasing-Chord Drawings of 3-Connected Planar Graphs.
    Journal of Computational Geometry, 7(1):47–69, 2016.
    Joint work with Martin Nöllenburg and Roman Prutkin.
  18. Testing Planarity of Partially Embedded Graphs.
    ACM Transactions on Algorithms, 11(4):32, 2015.
    Joint work with Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Vít Jelínek, Jan Kratochvíl, and Maurizio Patrignani.
    [ html ]
  19. Many-to-One Boundary Labeling with Backbones.
    Journal of Graph Algorithms and Applications, 19(3):761–778, 2015.
    Joint work with Michael Bekos, Sabine Cornelsen, Martin Fink, Seok-Hee Hong, Michael Kaufmann, Martin Nöllenburg, and Antonios Symvonis.
  20. Disconnectivity and relative positions in simultaneous embeddings.
    Computational Geometry: Theory and Applications, 48(6):459–478, 2015.
    Joint work with Thomas Bläsius.
    [ html ]
  21. Online Dynamic Power Management with Hard Real-Time Guarantees.
    Theoretical Computer Science, 595:46–64, 2015.
    Joint work with Jian-Jia Chen, Mong-Jen Kao, Der-Tsai Lee, and Dorothea Wagner.
  22. Regular Augmentation of Planar Graphs.
    Algorithmica, 73(2):306–370, 2015.
    Joint work with Tanja Hartmann and Jonathan Rollin.
    [ html ]
  23. Testing Mutual Duality of Planar Graphs.
    International Journal of Computational Geometry and Applications, 24(4):325–346, 2014.
    Joint work with Patrizio Angelini and Thomas Bläsius.
  24. Generalizing Geometric Graphs.
    Journal of Graph Algorithms and Applications, 18(1):35–76, 2014.
    Joint work with Edith Brunel, Andreas Gemsa, Marcus Krug, and Dorothea Wagner.
  25. Column-Based Graph Layouts.
    Journal of Graph Algorithms and Applications, 18(5):677–708, 2014.
    Joint work with Gregor Betz, Andreas Gemsa, Christof Mathies, and Dorothea Wagner.
    [ html ]
  26. Orthogonal Graph Drawing with Flexibility Constraints.
    Algorithmica, 68(4):859–885, 2014.
    Joint work with Thomas Bläsius, Marcus Krug, and Dorothea Wagner.
    [ html ]
  27. On d-regular Schematization of Embedded Paths.
    Computational Geometry: Theory and Applications, 47(3A):381–406, 2014.
    Joint work with Daniel Delling, Andreas Gemsa, Martin Nöllenburg, and Thomas Pajor.
    [ html | pdf ]
  28. Fork-forests in bi-colored complete bipartite graphs.
    Discrete Applied Mathematics, 161(10–11):1363–1366, 2013.
    Joint work with Maria Axenovich, Marcus Krug, and Georg Osang.
    [ html ]
  29. On the Complexity of Partitioning Graphs for Arc-Flags.
    Journal of Graph Algorithms and Applications, 17(3):265–299, 2013.
    Joint work with Reinhard Bauer, Moritz Baum, and Dorothea Wagner.
    [ html ]
  30. Cops-and-robbers: remarks and problems.
    Journal of Combinatorial Mathematics and Combinatorial Computing, 85:141–159, 2013.
    Joint work with Michel Boyer, Sif El Harti, Amal El Ouarari, Robert Ganian, Tomas Gavenciak, Geňa Hahn, Carsten Moldenauer, Benoit Theriault, and Martin Vatshelle.
  31. A Kuratowski-Type Theorem for Planarity of Partially Embedded Graphs.
    Computational Geometry: Theory and Applications, 46(4):466–492, 2013.
    Special issue of SoCG'11.
    Joint work with Vít Jelínek and Jan Kratochvíl.
  32. The Density Maximization Problem in Graphs.
    Journal of Combinatorial Optimization, 26(4):723–754, 2013.
    Special issue of COCOON'11.
    Joint work with Mong-Jen Kao, Bastian Katz, Marcus Krug, Der-Tsai Lee, and Dorothea Wagner.
    [ html ]
  33. Edge-weighted contact representations of planar graphs.
    Journal of Graph Algorithms and Applications, 17(4):441–473, 2013.
    Special issue of GD 2012.
    Joint work with Martin Nöllenburg and Roman Prutkin.
    [ html | pdf ]
  34. Testing the Simultaneous Embeddability of two Graphs whose Intersection is a Biconnected or a Connected Graph.
    Journal of Discrete Algorithms, 14:150–172, 2012.
    Special issue of IWOCA'10.
    Joint work with Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, and Maurizio Patrignani.
    [ html ]
  35. Hamiltonian orthogeodesic alternating paths.
    Journal of Discrete Algorithms, 16:34–52, 2012.
    Special issue of IWOCA'11.
    Joint work with Emilio Di Giacomo, Luca Grilli, Marcus Krug, and Giuseppe Liotta.
    [ html ]
  36. An algorithmic study of switch graphs.
    Acta Informatica, 49(5):295–312, 2012.
    Joint work with Bastian Katz and Gerhard J. Woeginger.
    [ pdf ]
  37. Augmenting the Connectivity of Planar and Geometric Graphs.
    Journal of Graph Algorithms and Applications, 16(2):599–628, 2012.
    Joint work with Alexander Wolff.
    [ html ]
  38. Computing Large Matchings in Planar Graphs with Fixed Minimum Degree.
    Theoretical Computer Science, 412(32):4092–4099, 2010.
    Joint work with Robert Franke and Dorothea Wagner.
    [ html ]
  39. Computing Large Matchings Fast.
    ACM Transactions on Algorithms, 7(1), 2010.
    Joint work with Alexander Wolff.
  40. Augmenting the Connectivity of Planar and Geometric Graphs.
    Electronic Notes in Discrete Mathematics, 31:53–56, 2008.
    Joint work with Alexander Wolff.
    [ html ]

Artikel in Tagungsbänden

  1. Towards a Characterization of Stretchable Aligned Graphs.
    In: Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD'20), Lecture Notes in Computer Science. Springer, 2020.
    Joint work with Marcel Radermacher and Peter Stumpf.
  2. Geometric Crossing-Minimization - A Scalable Randomized Approach.
    In: Proceedings of the 27th Annual European Symposium on Algorithms (ESA'19), volume 144 of Leibniz International Proceedings in Informatics, pages 76:1–76:16, September 2019.
    Joint work with Marcel Radermacher.
    [ html ]
  3. Drawing Clustered Graphs on Disk Arrangements.
    In: Proceedings of the 13th Conference and Workshops on Algorithms and Computation (WALCOM 2019), volume 11355 of Lecture Notes in Computer Science. Springer, 2019.
    Joint work with Tamara Mchedlidze, Marcel Radermacher, and Nina Zimbel.
    [ html ]
  4. Efficient Algorithms for Ortho-Radial Graph Drawing.
    In: Proceedings of the 35th International Symposium on Computational Geometry (SoCG 2019), Leibniz International Proceedings in Informatics, pages 53:1–53:14, 2019.
    Joint work with Benjamin Niedermann and Matthias Wolf.
    [ html ]
  5. The Maximum Transmission Switching Flow Problem.
    In: Proceedings of the 9th ACM e-Energy International Conference on Future Energy Systems (ACM e-Energy'18), pages 340–360. ACM Press, 2018.
    Joint work with Alban Grastien, Dorothea Wagner, Franziska Wegner, and Matthias Wolf.
    [ html ]
  6. Drawing Connected Planar Clustered Graphs on Disk Arrangements.
    In: Proceedings of the 34th European Workshop on Computational Geometry (EuroCG'18), 2018.
    Joint work with Tamara Mchedlidze, Marcel Radermacher, and Nina Zimbel.
    [ html ]
  7. Efficient Algorithms for Ortho-Radial Graph Drawing.
    In: Proceedings of the 34th European Workshop on Computational Geometry (EuroCG'18), 2018.
    Preprint.
    Joint work with Benjamin Niedermann and Matthias Wolf.
    [ html | pdf ]
  8. Inserting an Edge into a Geometric Embedding.
    In: Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD'18), Lecture Notes in Computer Science, pages 402–415. Springer, 2018.
    Joint work with Marcel Radermacher.
    [ html ]
  9. A Geometric Heuristic for Rectilinear Crossing Minimization.
    In: Proceedings of the 20th Meeting on Algorithm Engineering and Experiments (ALENEX'18), pages 129–138. SIAM, 2018.
    Joint work with Marcel Radermacher, Klara Reichard, and Dorothea Wagner.
    [ html ]
  10. Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings.
    In: Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017), Leibniz International Proceedings in Informatics, pages 14:1–14:16, 2017.
    Joint work with Lukas Barth, Benjamin Niedermann, and Matthias Wolf.
    [ html ]
  11. Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings.
    In: Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG'17), 2017.
    Preprint.
    Joint work with Lukas Barth, Benjamin Niedermann, and Matthias Wolf.
    [ html | pdf ]
  12. Partial and Constrained Level Planarity.
    In: Proceedings of the 28th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA'17), pages 2000–2011. SIAM, 2017.
    Joint work with Guido Brückner.
  13. 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 Thomas Bläsius and Marcel Radermacher.
    [ html | pdf ]
  14. A Simulated-Annealing-Based Approach for Wind Farm Cabling.
    In: Proceedings of the 8th ACM e-Energy International Conference on Future Energy Systems (ACM eEnergy'17), pages 203–215. ACM Press, 2017.
    Joint work with Sebastian Lehmann, Dorothea Wagner, and Franziska Wegner.
    [ html ]
  15. Aligned Drawings of Planar Graphs.
    In: Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG'17), 2017.
    Joint work with Tamara Mchedlidze and Marcel Radermacher.
  16. Aligned Drawings of Planar Graphs.
    In: Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD'17), Lecture Notes in Computer Science, pages 3–16. Springer, 2017.
    Joint work with Tamara Mchedlidze and Marcel Radermacher.
    [ html ]
  17. Radial Contour Labeling with Straight Leaders.
    In: Proceedings of IEEE Pacific Visualization Symposium (PacificVis'17). IEEE Computer Society, 2017.
    To appear.
    Joint work with Benjamin Niedermann and Martin Nöllenburg.
  18. Radial Contour Labeling with Straight Leaders.
    In: Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG'17), 2017.
    Preprint.
    Joint work with Benjamin Niedermann and Martin Nöllenburg.
    [ html ]
  19. Simultaneous Orthogonal Planarity.
    In: Proceedings of the 24th International Symposium on Graph Drawing (GD'16), Lecture Notes in Computer Science, pages 532–545. Springer, 2016.
    Joint work with Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, Giordano Da Lozzo, Giuseppe Di Battista, Peter Eades, Philipp Kindermann, Jan Kratochvíl, and Fabian Lipp.
  20. Windrose Planarity: Embedding Graphs with Direction-Constrained Edges.
    In: Proceedings of the 27th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA'16), pages 306–315. SIAM, 2016.
    Joint work with Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Valentino Di Donato, Philipp Kindermann, and Günter Rote.
    [ html ]
  21. Beyond Level Planarity.
    In: Proceedings of the 24th International Symposium on Graph Drawing (GD'16), Lecture Notes in Computer Science, pages 482–495. Springer, 2016.
    Joint work with Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, and Maurizio Patrignani.
  22. 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, Thomas Bläsius, Andreas Gemsa, and Franziska Wegner.
    [ pdf ]
  23. 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, Thomas Bläsius, Andreas Gemsa, and Franziska Wegner.
    [ html | pdf ]
  24. Linear-Time Recognition of Map Graphs with Outerplanar Witness.
    In: Proceedings of the 15th Scandinavian Symposium and Workshop on Algorithm Theory (SWAT'16), Lecture Notes in Computer Science. Springer, 2016.
    To appear.
    Joint work with Matthias Mnich and Jens M. Schmidt.
  25. Software Visualization via Hierarchic Micro/Macro Layouts.
    In: Proceedings of the 11th Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP '16) – Volume 2: IVAPP, pages 155–162, 2016.
    Joint work with Martin Nöllenburg and Alfred Schuhmacher.
  26. 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, Torsten Ueckerdt, and Alexander Wolff.
    [ html ]
  27. Intersection-Link Representations of Graphs.
    In: Proceedings of the 23rd International Symposium on Graph Drawing (GD'15), Lecture Notes in Computer Science, pages 217–230. Springer, 2015.
    Joint work with Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, and Maurizio Patrignani.
    [ html ]
  28. 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 Thomas Bläsius and Sebastian Lehmann.
    [ html ]
  29. Optimal Shuffle Code with Permutation Instructions.
    In: Algorithms and Data Structures, 14th International Symposium (WADS'15), Lecture Notes in Computer Science, pages 528–541. Springer, 2015.
    Joint work with Sebastian Buchwald and Manuel Mohr.
    [ html ]
  30. Planarity of Streamed Graphs.
    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 Giordano Da Lozzo.
    [ html ]
  31. Operating Power Grids with few Flow Control Buses.
    In: Proceedings of the 6th ACM e-Energy International Conference on Future Energy Systems, pages 289–294. ACM Press, 2015.
    Full version available at http://arxiv.org/abs/1505.05747.
    Joint work with Thomas Leibfried, Tamara Mchedlidze, Nico Meyer-Hübner, Martin Nöllenburg, Peter Sanders, Dorothea Wagner, and Franziska Wegner.
    [ html ]
  32. Towards Realistic Flow Control in Power Grid Operation.
    In: Proceedings of the 4th D-A-CH Conference on Energy Informatics, volume 9424 of Lecture Notes in Computer Science, pages 192–199. Springer, 2015.
    Joint work with Tamara Mchedlidze, Martin Nöllenburg, Dorothea Wagner, and Franziska Wegner.
    [ html ]
  33. Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions.
    In: Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC'15), Lecture Notes in Computer Science, pages 637–649. Springer, 2015.
    Joint work with Martin Nöllenburg and Roman Prutkin.
    [ html ]
  34. 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 Thomas Bläsius and Guido Brückner.
    [ html ]
  35. 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 Thomas Bläsius.
  36. Online Dynamic Power Management with Hard Real-Time Guarantees.
    In: Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS'14), Leibniz International Proceedings in Informatics, pages 226–238, 2014.
    Joint work with Jian-Jia Chen, Mong-Jen Kao, Der-Tsai Lee, and Dorothea Wagner.
  37. Planar Embeddings with Small and Uniform Faces.
    In: Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC'14), volume 8889 of Lecture Notes in Computer Science, pages 633–645. Springer, 2014.
    Joint work with Giordano Da Lozzo, Vít Jelínek, and Jan Kratochvíl.
  38. Drawing Simultaneously Embedded Graphs with Few Bends.
    In: Proceedings of the 22nd International Symposium on Graph Drawing (GD'14), volume 8871 of Lecture Notes in Computer Science, pages 40–51. Springer, 2014.
    Joint work with Luca Grilli, Seok-Hee Hong, and Jan Kratochvíl.
  39. Evaluation of Labeling Strategies for Rotating Maps.
    In: Proceedings of the 13th International Symposium on Experimental Algorithms (SEA'14), volume 8504 of Lecture Notes in Computer Science, pages 235–246. Springer, 2014.
    Full version available at http://arxiv.org/abs/1404.1849.
    Joint work with Andreas Gemsa and Martin Nöllenburg.
    [ html | pdf ]
  40. Extending Partial Representations of Proper and Unit Interval Graphs.
    In: Proceedings of the 14th Scandinavian Symposium and Workshop on Algorithm Theory (SWAT'14), volume 8503 of Lecture Notes in Computer Science, pages 253–264. Springer, 2014.
    Joint work with Pavel Klavík, Jan Kratochvíl, Yota Otachi, Toshiki Saitoh, Maria Saumell, and Tomás Viskočil.
  41. On Self-Approaching and Increasing-Chord Drawings of 3-Connected Planar Graphs .
    In: Proceedings of the 22nd International Symposium on Graph Drawing (GD'14), volume 8871 of Lecture Notes in Computer Science, pages 476–487. Springer, 2014.
    Full version available at http://arxiv.org/abs/1409.0315.
    Joint work with Martin Nöllenburg and Roman Prutkin.
    [ html | pdf ]
  42. 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 Thomas Bläsius.
  43. 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, Thomas Bläsius, Benjamin Niedermann, Martin Nöllenburg, and Roman Prutkin.
    [ html | pdf ]
  44. Many-to-One Boundary Labeling with Backbones.
    In: Proceedings of the 21st International Symposium on Graph Drawing (GD'13), volume 8242 of Lecture Notes in Computer Science, pages 244–255. Springer, 2013.
    Full version available at http://arxiv.org/abs/1308.6801.
    Joint work with Michael Bekos, Sabine Cornelsen, Martin Fink, Seok-Hee Hong, Michael Kaufmann, Martin Nöllenburg, and Antonios Symvonis.
    [ html | pdf ]
  45. Search-Space Size in Contraction Hierarchies.
    In: Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP'13), volume 7965 of Lecture Notes in Computer Science, pages 93–104. Springer, 2013.
    Joint work with Reinhard Bauer, Tobias Columbus, and Dorothea Wagner.
  46. Column-based Graph Layouts.
    In: Proceedings of the 20th International Symposium on Graph Drawing (GD'12), volume 7704 of Lecture Notes in Computer Science, pages 236–247. Springer, 2013.
    Joint work with Gregor Betz, Christof Doll, Andreas Gemsa, and Dorothea Wagner.
  47. 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 Thomas Bläsius and Annette Karrer.
  48. 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 Thomas Bläsius.
  49. 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 Thomas Bläsius.
  50. 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 Thomas Bläsius and Dorothea Wagner.
  51. Extending partial representations of proper and unit interval graphs.
    In: Proceedings of the 29th European Workshop on Computational Geometry (EuroCG'13), 2013.
    To appear.
    Joint work with Pavel Klavík, Jan Kratochvíl, Yota Otachi, Toshiki Saitoh, Maria Saumell, and Tomás Viskočil.
  52. Two-Sided Boundary Labeling with Adjacent Sides.
    In: Algorithms and Data Structures, 13th International Symposium (WADS'13), volume 8037 of Lecture Notes in Computer Science, pages 463–474. Springer, 2013.
    Joint work with Philipp Kindermann, Benjamin Niedermann, Marcus Schaefer, André Schulz, and Alexander Wolff.
  53. Two-Sided Boundary Labeling with Adjacent Sides.
    In: Proceedings of the 29th European Workshop on Computational Geometry (EuroCG'13), 2013.
    Joint work with Philipp Kindermann, Benjamin Niedermann, Marcus Schaefer, André Schulz, and Alexander Wolff.
  54. Drawing Planar Graphs with a Prescribed Cycle.
    In: Proceedings of the 21st International Symposium on Graph Drawing (GD'13), volume 8242 of Lecture Notes in Computer Science, pages 316–327. Springer, 2013.
    Full version available at http://arxiv.org/abs/1308.3370.
    Joint work with Tamara Mchedlidze and Martin Nöllenburg.
    [ html | pdf ]
  55. Edge-weighted Contact Representations of Planar Graphs.
    In: Proceedings of the 20th International Symposium on Graph Drawing (GD'12), volume 7704 of Lecture Notes in Computer Science, pages 224–235. Springer, 2013.
    Joint work with Martin Nöllenburg and Roman Prutkin.
    [ html | pdf ]
  56. On the Complexity of Partitioning Graphs for Arc-Flags.
    In: Proceedings of the 12th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'12), volume 25 of OpenAccess Series in Informatics (OASIcs), pages 71–82. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012.
    Joint work with Reinhard Bauer, Moritz Baum, and Dorothea Wagner.
    [ html | pdf ]
  57. Generalizing Geometric Graphs.
    In: Proceedings of the 19th International Symposium on Graph Drawing (GD'11), Lecture Notes in Computer Science, pages 179–190. Springer, 2012.
    Joint work with Edith Brunel, Andreas Gemsa, Marcus Krug, and Dorothea Wagner.
    [ html ]
  58. Cubic Augmentation of Planar Graphs.
    In: Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC'12), volume 7676 of Lecture Notes in Computer Science, pages 402–412. Springer, 2012.
    Full version available at http://arxiv.org/abs/1209.3865.
    Joint work with Tanja Hartmann and Jonathan Rollin.
    [ html ]
  59. Competitive Design and Analysis for Machine-Minimizing Job Scheduling Problem.
    In: Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC'12), volume 7676 of Lecture Notes in Computer Science, pages 75–84. Springer, 2012.
    Joint work with Mong-Jen Kao, Jian-Jia Chen, Der-Tsai Lee, and Dorothea Wagner.
  60. 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 Thomas Bläsius, Marcus Krug, and Dorothea Wagner.
    [ html ]
  61. Hamiltonian Orthogeodesic Alternating Paths.
    In: Proceedings of the 22nd International Workshop on Combinatorial Algorithms (IWOCA'11), Lecture Notes in Computer Science, pages 170–181. Springer, 2011.
    Joint work with Emilio Di Giacomo, Luca Grilli, Marcus Krug, and Giuseppe Liotta.
    [ html ]
  62. Automatic Generation of Route Sketches.
    In: Proceedings of the 18th International Symposium on Graph Drawing (GD'10), volume 6502 of Lecture Notes in Computer Science, pages 391–392. Springer, 2011.
    Poster abstract.
    Joint work with Andreas Gemsa, Martin Nöllenburg, and Thomas Pajor.
    [ html | pdf ]
  63. On d-regular Schematization of Embedded Paths.
    In: Proceedings of the 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'11), volume 6543 of Lecture Notes in Computer Science, pages 260–271. Springer, January 2011.
    Joint work with Andreas Gemsa, Martin Nöllenburg, and Thomas Pajor.
    [ html | pdf ]
  64. Consistent Labeling of Rotating Maps.
    In: Proceedings of the 27th European Workshop on Computational Geometry (EuroCG'11), pages 171–174, 2011.
    Joint work with Andreas Gemsa and Martin Nöllenburg.
    [ pdf ]
  65. Consistent Labeling of Rotating Maps.
    In: Algorithms and Data Structures, 12th International Symposium (WADS'11), volume 6844 of Lecture Notes in Computer Science, pages 451–462. Springer, 2011.
    Full version available at http://arxiv.org/abs/1104.5634.
    Joint work with Andreas Gemsa and Martin Nöllenburg.
    [ html | pdf ]
  66. Sliding Labels for Dynamic Point Labeling.
    In: Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG '11), pages 205–210. University of Toronto Press, 2011.
    Joint work with Andreas Gemsa and Martin Nöllenburg.
    [ pdf ]
  67. A Kuratowski-Type Theorem for Planarity of Partially Embedded Graphs .
    In: Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG'11), pages 107–116. ACM Press, 2011.
    Joint work with Vít Jelínek and Jan Kratochvíl.
  68. Connecting Two Trees with Optimal Routing Cost.
    In: Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG '11), pages 43–47. University of Toronto Press, 2011.
    Joint work with Mong-Jen Kao, Bastian Katz, Marcus Krug, Der-Tsai Lee, Martin Nöllenburg, and Dorothea Wagner.
    [ html | pdf ]
  69. The Density Maximization Problem in Graphs.
    In: Proceedings of the 17th Annual International Conference on Computing Combinatorics (COCOON'11), volume 6842 of Lecture Notes in Computer Science, pages 25–36. Springer, 2011.
    Joint work with Mong-Jen Kao, Bastian Katz, Marcus Krug, Der-Tsai Lee, and Dorothea Wagner.
  70. Speed Dating: An Algorithmic Case Study Involving Matching and Scheduling.
    In: Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11), volume 6630 of Lecture Notes in Computer Science, pages 292–303. Springer, 2011.
    Joint work with Bastian Katz, Ben Strasser, and Dorothea Wagner.
  71. Gateway Decompositions for Constrained Reachability Problems.
    In: Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10), volume 6049 of Lecture Notes in Computer Science, pages 449–461. Springer, May 2010.
    Joint work with Bastian Katz, Marcus Krug, Andreas Lochbihler, Gregor Snelting, and Dorothea Wagner.
  72. Testing Planarity of Partially Embedded Graphs.
    In: Proceedings of the 21st Annual ACM–SIAM Symposium on Discrete Algorithms (SODA'10), pages 202–221. SIAM, 2010.
    Joint work with Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Vít Jelínek, Jan Kratochvíl, and Maurizio Patrignani.
    [ html ]
  73. Testing the Simultaneous Embeddability of Two Graphs whose Intersection is a Biconnected Graph or a Tree.
    In: Proceedings of the 21st International Workshop on Combinatorial Algorithms (IWOCA'10), volume 6460 of Lecture Notes in Computer Science, pages 212–225. Springer, 2010.
    Joint work with Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, and Maurizio Patrignani.
  74. How Alexander the Great Brought the Greeks Together While Inflicting Minimal Damage to the Barbarians.
    In: Proceedings of the 26th European Workshop on Computational Geometry (EuroCG'10), pages 73–76, 2010.
    Joint work with Mark de Berg, Dirk Gerrits, Amirali Khosravi, Constantinos Tsirogiannis, and Alexander Wolff.
  75. Manhattan-Geodesic Embedding of Planar Graphs.
    In: Proceedings of the 17th International Symposium on Graph Drawing (GD'09), volume 5849 of Lecture Notes in Computer Science, pages 207–218. Springer, 2010.
    Joint work with Bastian Katz, Marcus Krug, and Alexander Wolff.
    [ html ]
  76. An Algorithmic Study of Switch Graphs.
    In: Proceedings of the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'09), volume 5911 of Lecture Notes in Computer Science, pages 226–237. Springer, June 2009.
    Joint work with Bastian Katz and Gerhard J. Woeginger.
    [ html ]
  77. Computing Large Matchings in Planar Graphs with Fixed Minimum Degree.
    In: Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC'09), volume 5878 of Lecture Notes in Computer Science, pages 872–881. Springer, 2009.
    Joint work with Robert Franke and Dorothea Wagner.
  78. Augmenting the connectivity of planar and geometric graphs.
    In: Proceedings of the 24th European Workshop on Computational Geometry (EuroCG'08), pages 71–74, 2008.
    Joint work with Alexander Wolff.
    [ pdf ]
  79. Augmenting the connectivity of planar and geometric graphs.
    In: Topological & Geometric Graph Theory (TGGT'08), pages 55–58, 2008.
    Joint work with Alexander Wolff.
    [ pdf ]
  80. Computing Large Matchings Fast.
    In: Proceedings of the 19th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA'08), pages 183–192, 2008.
    Joint work with Alexander Wolff.
    [ pdf ]

Dissertation

  1. The Many Faces of Planarity – Matching, Augmentation, and Embedding Algorithms for Planar Graphs –.
    PhD thesis, Fakultät für Informatik, Karlsruher Institut für Technologie (KIT), July 2011.
    [ html | pdf ]

Abschlussarbeiten

  1. Schnelle Berechnung von großen Matchings.
    Master's thesis, Fakultät für Informatik, Universität Karlsruhe, April 2007.
    [ pdf ]

Technische Berichte

  1. Scalable Isocontour Visualization in Road Networks via Minimum-Link Paths.
    Technical Report 1602.01777, ArXiv e-prints, 2016.
    Joint work with Moritz Baum, Thomas Bläsius, Andreas Gemsa, and Franziska Wegner.
    [ html | pdf ]
  2. Operating Power Grids with Few Flow Control Buses.
    Technical Report 1505.05747, ArXiv e-prints, 2015.
    Joint work with Thomas Leibfried, Tamara Mchedlidze, Nico Meyer-Hübner, Martin Nöllenburg, Peter Sanders, Dorothea Wagner, and Franziska Wegner.
    [ html | pdf ]
  3. Online Power-Managing Strategy with Hard Real-Time Guarantees .
    Technical report, ITI Wagner, Department of Informatics, Karlsruhe Institute of Technology (KIT), 2013.
    accepted for publication in Theoretical Computer Science.
    Joint work with Jian-Jia Chen, Mong-Jen Kao, Der-Tsai Lee, and Dorothea Wagner.
    [ html ]
  4. Cubic augmentation of planar graphs.
    Technical Report arXiv:1209.3865, ITI Wagner, Department of Informatics, Karlsruhe Institute of Technology (KIT), 2012.
    Full version of conference paper at ISAAC'12.
    Joint work with Tanja Hartmann and Jonathan Rollin.
    [ html ]
  5. Generalizing Geometric Graphs.
    Technical Report 2011-27, ITI Wagner, Department of Informatics, Karlsruhe Institute of Technology (KIT), 2011.
    Joint work with Edith Brunel, Andreas Gemsa, Marcus Krug, and Dorothea Wagner.
    [ html ]
  6. The Density Maximization Problem in Graphs.
    Technical Report 2011-18, ITI Wagner, Department of Informatics, Karlsruhe Institute of Technology (KIT), 2011.
    Joint work with Ming-Yang Kao, Bastian Katz, Marcus Krug, Der-Tsai Lee, and Dorothea Wagner.
    [ html ]
  7. Orthogonal Graph Drawing with Flexibility Constraints.
    Technical Report 2010-18, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2010.
    Joint work with Thomas Bläsius, Marcus Krug, and Dorothea Wagner.
    [ html ]
  8. On d-regular Schematization of Embedded Paths.
    Technical Report 2010-21, Faculty of Informatics, Karlsruhe Institute of Technology, 2010.
    Joint work with Andreas Gemsa, Martin Nöllenburg, and Thomas Pajor.
    [ html | pdf ]
  9. Computing Large Matchings in Planar Graphs with Fixed Minimum Degree.
    Technical Report 2009-18, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2009.
    Joint work with Robert Franke and Dorothea Wagner.
    [ html | pdf ]
  10. Manhattan-Geodesic Point-Set Embeddability and Polygonization .
    Technical Report 2009-17, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2009.
    Joint work with Bastian Katz, Marcus Krug, and Alexander Wolff.
    [ html | pdf ]
  11. Augmenting the Connectivity of Planar and Geometric Graphs.
    Technical Report 2008-3, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2008.
    Joint work with Alexander Wolff.
    [ pdf ]
  12. Computing large matchings fast.
    Technical Report 2007-19, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2007.
    Joint work with Alexander Wolff.
    [ html | pdf ]