Marcus Krug

Publications

Journal articles

  1. Generalizing Geometric Graphs.
    Journal of Graph Algorithms and Applications, 18(1):35-76, 2014.
    Joint work with Edith Brunel, Andreas Gemsa, Ignaz Rutter, and Dorothea Wagner.
  2. Orthogonal Graph Drawing with Flexibility Constraints.
    Algorithmica, 68(4):859-885, 2014.
    Joint work with Thomas Bläsius, Ignaz Rutter, and Dorothea Wagner.
    [ html ]
  3. Fork-forests in bi-colored complete bipartite graphs.
    Discrete Applied Mathematics, 161(10-11):1363-1366, 2013.
    Joint work with Maria Axenovich, Georg Osang, and Ignaz Rutter.
    [ html ]
  4. 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, D.T. Lee, Ignaz Rutter, and Dorothea Wagner.
    [ html ]
  5. 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, Giuseppe Liotta, and Ignaz Rutter.
    [ html ]
  6. Augmenting k-Core Generation with Preferential Attachment.
    Networks and Heterogeneous Media, 3(2):277-294, June 2008.
    Joint work with Michael Baur, Marco Gaertler, Robert Görke, and Dorothea Wagner.
    [ html | pdf ]

Conference articles

  1. Visualizing Large Hierarchically Clustered Graphs with a Landscape Metaphor.
    In: Proceedings of the 20th International Symposium on Graph Drawing (GD'12), volume 7704 of Lecture Notes in Computer Science, pages 553-554. Springer, 2013.
    Poster abstract.
    Joint work with Jan Christoph Athenstädt, Robert Görke, and Martin Nöllenburg.
    [ html | pdf ]
  2. 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, Ignaz Rutter, and Dorothea Wagner.
    [ html ]
  3. Orthogeodesic Point-Set Embedding of Trees.
    In: Proceedings of the 19th International Symposium on Graph Drawing (GD'11), Lecture Notes in Computer Science. Springer, 2012.
    to appear.
    Joint work with Emilio Di Giacomo, Fabrizio Frati, Radoslav Fulek, and Luca Grilli.
  4. 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, Ignaz Rutter, and Dorothea Wagner.
    [ html ]
  5. 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, Giuseppe Liotta, and Ignaz Rutter.
    [ html ]
  6. 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, D.T. Lee, Martin Nöllenburg, Ignaz Rutter, and Dorothea Wagner.
    [ html | pdf ]
  7. 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, D.T. Lee, Ignaz Rutter, and Dorothea Wagner.
  8. Constructing Optimal Shortcuts in Directed Weighted Paths and Trees.
    In: Proceedings of the 27th European Workshop on Computational Geometry (EuroCG'11), 2011.
    Joint work with Rolf Klein, Elmar Langetepe, D.T. Lee, and Dorothea Wagner.
  9. 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, Andreas Lochbihler, Ignaz Rutter, Gregor Snelting, and Dorothea Wagner.
  10. Preprocessing Speed-Up Techniques is Hard.
    In: Proceedings of the 7th Conference on Algorithms and Complexity (CIAC'10), volume 6078 of Lecture Notes in Computer Science, pages 359-370. Springer, 2010.
    Joint work with Reinhard Bauer, Tobias Columbus, Bastian Katz, and Dorothea Wagner.
  11. Synthetic Road Networks.
    In: Proceedings of the 6th International Conference on Algorithmic Aspects in Information and Management (AAIM'10), volume 6124 of Lecture Notes in Computer Science, pages 46-57. Springer, 2010.
    Joint work with Reinhard Bauer, Sascha Meinert, and Dorothea Wagner.
    [ html ]
  12. Enumerating and Generating Labeled k-Degenerate Graphs.
    In: Proceedings of the Seventh Workshop on Analytic Algorithmics and Combinatorics (ANALCO '10), pages 90-98. SIAM, 2010.
    Joint work with Reinhard Bauer and Dorothea Wagner.
  13. 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, Ignaz Rutter, and Alexander Wolff.
    [ html ]
  14. Minimizing the Area for Planar Straight-Line Grid Drawings.
    In: Proceedings of the 15th International Symposium on Graph Drawing (GD'07), volume 4875 of Lecture Notes in Computer Science, pages 207-212. Springer, January 2008.
    Joint work with Dorothea Wagner.
    [ pdf ]
  15. Generating Graphs with Predefined k-Core Structure.
    In: Proceedings of the European Conference of Complex Systems (ECCS'07), October 2007.
    Joint work with Michael Baur, Marco Gaertler, Robert Görke, and Dorothea Wagner.
    [ pdf ]

Master's Thesis

  1. Minimizing the Area for Planar Straight-Line Grid Drawings.
    Master's thesis, Universität Karlsruhe, 2007.
    [ pdf ]

Technical reports

  1. 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, Ignaz Rutter, and Dorothea Wagner.
    [ html ]
  2. Orthogeodesic Point-Set Embedding of Trees.
    Technical report, ITI Wagner, Department of Informatics, Karlsruhe Institute of Technology (KIT), 2011.
    Joint work with Emilio Di Giacomo, Fabrizio Frati, Radoslav Fulek, and Luca Grilli.
    [ html ]
  3. 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, D.T. Lee, Ignaz Rutter, and Dorothea Wagner.
    [ html ]
  4. Preprocessing Speed-Up Techniques is Hard.
    Technical Report 2010-04, ITI Wagner, Faculty of Informatics, Karlsruhe Institute of Technology, 2010.
    Joint work with Reinhard Bauer, Tobias Columbus, Bastian Katz, and Dorothea Wagner.
    [ html ]
  5. 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, Ignaz Rutter, and Dorothea Wagner.
    [ html ]
  6. 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, Ignaz Rutter, and Alexander Wolff.
    [ html | pdf ]