Institut für Theoretische Informatik, Algorithmik

Veröffentlichungen

Tagungsbände

  1. Geometric Networks and Metric Space Embeddings.
    Number 06481 in Dagstuhl Seminar Proceedings, Schloss Dagstuhl, 2007. Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI).
    Jointly edited with Joachim Gudmundsson, Rolf Klein, Giri Narasimhan, and Michiel Smid.
    [ html ]

Buchbeiträge

  1. A simple and efficient algorithm for high-quality line labeling.
    In: Peter M. Atkinson and David J. Martin, editors, Innovations in GIS VII: GeoComputation, chapter 11, pages 147-159. Taylor & Francis, 2000.
    Joint work with Lars Knipping, Marc van Kreveld, Tycho Strijk, and Pankaj K. Agarwal.
    [ pdf ]
  2. The hardness of approximating set cover.
    In: Ernst W. Mayr, Hans Jürgen Prömel, and Angelika Steger, editors, Lectures on Proof Verification and Approximation Algorithms, volume 1367 of Lecture Notes in Computer Science Tutorial, chapter 10, pages 249-262. Springer-Verlag, 1998.
    [ html | ps ]

Artikel in Zeitschriften

  1. Constructing optimal highways.
    International Journal of Foundations of Computer Science, 20(1):3-23, 2009.
    Joint work with Hee-Kap Ahn, Helmut Alt, Tetsuo Asano, Sang Won Bae, Peter Brass, Otfried Cheong, Christian Knauer, Hyeon-Suk Na, and Chan-Su Shin.
    [ html | pdf | abstract ]
  2. A polynomial-time approximation algorithm for a geometric dispersion problem.
    International Journal of Computational Geometry and Applications, 19(3), 2009.
    To appear; conference version appeared at COCOON'06.
    Joint work with Marc Benkert, Joachim Gudmundsson, Christian Knauer, and René van Oostrum.
    [ html | pdf | abstract ]
  3. Matching points with rectangles and squares.
    Computational Geometry: Theory and Applications, 42(2):93-108, 2009.
    Joint work with Sergey Bereg and Nikolaus Mutsanas.
    [ html | pdf | abstract ]
  4. Optimizing active ranges for consistent dynamic map labeling.
    Computational Geometry: Theory and Applications, 2009.
    To appear; conference version appeared at SoCG'08.
    Joint work with Ken Been, Martin Nöllenburg, and Sheung-Hung Poon.
    [ html | pdf | abstract ]
  5. Trimming of graphs, with application to point labeling.
    Theory of Computing Systems, 2009.
    Appeared online at „http://dx.doi.org/10.1007/s00224-009-9184-8“.
    Joint work with Thomas Erlebach, Torben Hagerup, Klaus Jansen, and Moritz Minzlaff.
    [ html | pdf | abstract ]
  6. Untangling a planar graph.
    Discrete Computational Geometry, 2009.
    Appeared online at „http://dx.doi.org/10.1007/s00454-008-9130-6“.
    Joint work with Xavier Goaoc, Jan Kratochvíl, Yoshio Okamoto, Chan-Su Shin, and Andreas Spillner.
    [ html | pdf | abstract ]
  7. Area aggregation in map generalisation by mixed-integer programming.
    Internat. J. Geogr. Inf. Sci., 2009.
    Under review; conference version appeared at ACM-GIS'06.
    Joint work with Jan-Henrik Haunert.
    [ pdf | abstract ]
  8. Computing large matchings fast.
    ACM Transactions on Algorithms, 2009.
    To appear; conference version appeared at SODA'08.
    Joint work with Ignaz Rutter.
    [ html | pdf | abstract ]
  9. Constructing interference-minimal networks.
    Computational Geometry: Theory and Applications, 40(3):179-194, 2008.
    Joint work with Marc Benkert, Joachim Gudmundsson, and Herman Haverkort.
    [ html | pdf | abstract ]
  10. Constructing the city Voronoi diagram faster.
    International Journal of Computational Geometry and Applications, 18(4):275-294, 2008.
    Joint work with Robert Görke and Chan-Su Shin.
    [ html | pdf | abstract ]
  11. Decomposing a simple polygon into pseudo-triangles and convex polygons.
    Computational Geometry: Theory and Applications, 41(1-2):21-30, 2008.
    Joint work with Stefan Gerdjikov.
    [ html | pdf | abstract ]
  12. Morphing polylines: A step towards continuous generalization.
    32(4):248-260, 2008.
    Joint work with Damian Merrick, Martin Nöllenburg, and Marc Benkert.
    [ html | pdf | abstract ]
  13. Delineating boundaries for imprecise regions.
    Algorithmica, 50(3):386-414, 2008.
    Joint work with Iris Reinbacher, Marc Benkert, Marc van Kreveld, Joseph S.B. Mitchell, and Jack Snoeyink.
    [ html | pdf | abstract ]
  14. Boundary labeling: Models and efficient algorithms for rectangular maps.
    Computational Geometry: Theory and Applications, 36(3):215-236, 2007.
    Joint work with Michael A. Bekos, Michael Kaufmann, and Antonios Symvonis.
    [ html | pdf | abstract ]
  15. Configurations with few crossings in topological graphs.
    Computational Geometry: Theory and Applications, 37(2):104-114, 2007.
    Joint work with Christian Knauer, Étienne Schramm, and Andreas Spillner.
    [ html | pdf | abstract ]
  16. Drawing subway maps: A survey.
    Informatik - Forschung & Entwicklung, 22(1):23-44, 2007.
    [ html | pdf | abstract ]
  17. The minimum Manhattan network problem: Approximations and exact solutions.
    Computational Geometry: Theory and Applications, 35(3):188-208, 2006.
    Joint work with Marc Benkert, Florian Widmann, and Takeshi Shirabe.
    [ html | pdf | abstract ]
  18. Farthest-point queries with geometric and combinatorial constraints.
    Computational Geometry: Theory and Applications, 33(3):174-185, 2006.
    Joint work with Ovidiu Daescu, Ningfang Mi, and Chan-Su Shin.
    [ html | pdf | abstract ]
  19. Optimal spanners for axis-aligned rectangles.
    Computational Geometry: Theory and Applications, 30(1):59-77, 2005.
    Joint work with Tetsuo Asano, Mark de Berg, Otfried Cheong, Hazel Everett, Herman Haverkort, and Naoki Katoh.
    [ html | pdf | abstract ]
  20. Facility location and the geometric minimum-diameter spanning tree.
    Computational Geometry: Theory and Applications, 27(1):87-106, 2004.
    Joint work with Joachim Gudmundsson, Herman Haverkort, Sang-Min Park, and Chan-Su Shin.
    [ html | pdf | abstract ]
  21. Labeling points with weights.
    Algorithmica, 38(2):341-362, 2003.
    Joint work with Sheung-Hung Poon, Chan-Su Shin, Tycho Strijk, and Takeaki Uno.
    [ html | pdf | abstract ]
  22. Towards an evaluation of quality for names placement methods.
    International Journal of Geographical Information Science, 16(7):641-661, 2002.
    Joint work with Steven van Dijk, Marc van Kreveld, and Tycho Strijk.
    [ html | pdf | abstract ]
  23. A tutorial for designing flexible geometric algorithms.
    Algorithmica, 33(1):52-70, 2002.
    Joint work with Vikas Kapoor and Dietmar Kühl.
    [ html | pdf | abstract ]
  24. A simple factor-2/3 approximation algorithm for two-circle point labeling.
    International Journal of Computational Geometry and Applications, 12(4):269-281, 2002.
    Joint work with Michael Thon and Yinfeng Xu.
    [ html | pdf | abstract ]
  25. Labeling points with circles.
    International Journal of Computational Geometry and Applications, 11(2):181-195, 2001.
    Joint work with Tycho Strijk.
    [ html | pdf | abstract ]
  26. Three rules suffice for good label placement.
    Algorithmica, 30(2):334-349, 2001.
    Joint work with Frank Wagner, Vikas Kapoor, and Tycho Strijk.
    [ html | pdf | abstract ]
  27. Point labeling with sliding labels.
    Computational Geometry: Theory and Applications, 13(1):21-47, 1999.
    Joint work with Marc van Kreveld and Tycho Strijk.
    [ html | pdf | abstract ]
  28. A practical map labeling algorithm.
    Computational Geometry: Theory and Applications, 7(5-6):387-404, 1997.
    Joint work with Frank Wagner.
    [ html | pdf | abstract ]

Artikel in Tagungsbänden

  1. Drawing (complete) binary tanglegrams: Hardness, approximation, fixed-parameter tractability.
    In: Ioannis G. Tollis and Maurizio Patrignani, editors, Proc. 16th Internat. Sympos. Graph Drawing (GD'08), volume 5417 of Lecture Notes in Computer Science, pages 324-335. Springer-Verlag, 2009.
    Joint work with Kevin Buchin, Maike Buchin, Jaroslaw Byrka, Martin Nöllenburg, Yoshio Okamoto, and Rodrigo I. Silveira.
    [ html | pdf ]
  2. Constructability of trip-lets.
    In: Stefan Langerman, editor, Proc. 25th European Workshop on Computational Geometry (EuroCG'09), Brussels, 2009.
    Joint work with Jeroen Keiren and Freek van Walderveen.
    [ pdf ]
  3. Drawing binary tanglegrams: An experimental evaluation.
    In: Proc. 11th Workshop on Algorithm Engineering and Experiments (ALENEX'09), pages 106-119, 2009.
    Joint work with Martin Nöllenburg, Markus Völker, and Danny Holten.
    [ html | pdf ]
  4. Cover contact graphs.
    In: Seok-Hee Hong, Takao Nishizeki, and Wu Quan, editors, Proc. 15th Internat. Sympos. Graph Drawing (GD'07), volume 4875 of Lecture Notes in Computer Science, pages 171-182. Springer-Verlag, 2008.
    Joint work with Nieves Atienza, Natalia de Castro, Carmen Cortés, M. Ángeles Garrido, Clara I. Grima, Gregorio Hernández, Alberto Márquez, Auxiliadora Moreno, Martin Nöllenburg, José Ramon Portillo, Pedro Reyes, Jesús Valenzuela, and Maria Trinidad Villar.
    [ html | pdf ]
  5. Optimizing active ranges for consistent dynamic map labeling.
    In: Proc. 24th Annu. ACM Sympos. Comput. Geom. (SoCG'08), pages 10-19, 2008.
    Joint work with Ken Been, Martin Nöllenburg, and Sheung-Hung Poon.
    [ html | pdf ]
  6. Optimizing active ranges for consistent dynamic map labeling.
    In: Silvain Petitjean, editor, Proc. 24th European Workshop on Computational Geometry (EuroCG'08), pages 55-58, Nancy, 2008.
    Joint work with Ken Been, Martin Nöllenburg, and Sheung-Hung Poon.
    [ pdf ]
  7. Trimming of graphs, with application to point labeling.
    In: Susanne Albers and Pascal Weil, editors, Proc. 25th Internat. Sympos. Theoretical Aspects Comput. Sci. (STACS'08), pages 265-276, Bordeaux, 2008.
    Joint work with Thomas Erlebach, Torben Hagerup, Klaus Jansen, and Moritz Minzlaff.
    [ html | pdf ]
  8. Moving vertices to make drawings plane.
    In: Seok-Hee Hong, Takao Nishizeki, and Wu Quan, editors, Proc. 15th Internat. Sympos. Graph Drawing (GD'07), volume 4875 of Lecture Notes in Computer Science, pages 101-112. Springer-Verlag, 2008.
    Joint work with Xavier Goaoc, Jan Kratochvíl, Yoshio Okamoto, and Chan-Su Shin.
    [ html | pdf ]
  9. Optimal simplification of building ground plans.
    In: Proc. 21st Congress Internat. Society Photogrammetry Remote Sensing (ISPRS'08), Technical Commision II/3, volume XXXVII, Part B2 of Internat. Archives of Photogrammetry, Remote Sensing and Spatial Informat. Sci., pages 373-378, Beijing, 2008.
    Joint work with Jan-Henrik Haunert.
    [ html | pdf ]
  10. Augmenting the connectivity of planar and geometric graphs.
    In: Silvain Petitjean, editor, Proc. 24th European Workshop on Computational Geometry (EuroCG'08), pages 71-74, Nancy, 2008.
    Joint work with Ignaz Rutter.
    [ pdf ]
  11. Augmenting the connectivity of planar and geometric graphs.
    In: Proc. Internat. Conf. Topological Geom. Graph Theory (TGGT'08), volume 31 of Electronic Notes in Discrete Mathematics, pages 53-56, Paris, 2008.
    Joint work with Ignaz Rutter.
    [ html | pdf ]
  12. Computing large matchings fast.
    In: Proc. 19th ACM-SIAM Sympos. Discrete Algorithms (SODA'08), pages 183-192, 2008.
    Joint work with Ignaz Rutter.
    [ html | pdf ]
  13. Untangling a planar graph.
    In: Viliam Geffert, Juhani Karhumäki, Alberto Bertoni, Bart Preneel, Pavol Návrat, and Mária Bieliková, editors, Proc. 34th Internat. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM'08), volume 4910 of Lecture Notes in Computer Science, pages 473-484. Springer-Verlag, 2008.
    Joint work with Andreas Spillner.
    [ html | pdf ]
  14. Constructing optimal highways.
    In: Barry Jay and Joachim Gudmundsson, editors, Proc. 13th Conf. Computing: The Australasian Theory Sympos. (CATS'07), volume 65 of Conferences in Research and Practice in Information Technology, pages 7-14. Australian Computer Society, 2007.
    Joint work with Hee-Kap Ahn, Helmut Alt, Tetsuo Asano, Sang Won Bae, Peter Brass, Otfried Cheong, Christian Knauer, Hyeon-Suk Na, and Chan-Su Shin.
    [ pdf ]
  15. Minimizing intra-edge crossings in wiring diagrams and public transport maps.
    In: Michael Kaufmann and Dorothea Wagner, editors, Proc. 14th Internat. Sympos. Graph Drawing (GD'06), volume 4372 of Lecture Notes in Computer Science, pages 270-281. Springer-Verlag, 2007.
    Joint work with Marc Benkert, Martin Nöllenburg, and Takeaki Uno.
    [ pdf ]
  16. Straightening drawings of clustered hierarchical graphs.
    In: Jan van Leeuwen, Giuseppe F. Italiano, Wiebe van der Hoek, Christoph Meinel, Harald Sack, and Frantisek Plasil, editors, Proc. 33rd Internat. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM'07), volume 4362 of Lecture Notes in Computer Science, pages 177-186. Springer-Verlag, 2007.
    Joint work with Sergey Bereg, Markus Völker, and Yuanyi Zhang.
    [ html | pdf ]
  17. Morphing polygonal lines: A step towards continuous generalization.
    In: Proc. 15th Annu. Geograph. Inform. Sci. Research Conf. UK (GISRUK'07), pages 390-399, Maynooth, Ireland, 2007.
    Joint work with Damian Merrick, Martin Nöllenburg, and Marc Benkert.
    [ html | pdf ]
  18. Morphing polygonal lines: A step towards continuous generalization.
    In: Oswin Aichholzer and Thomas Hackl, editors, Proc. 23rd European Workshop on Computational Geometry (EWCG'07), pages 6-9, Graz, 2007.
    Joint work with Damian Merrick, Martin Nöllenburg, and Marc Benkert.
    [ pdf ]
  19. Constructing interference-minimal networks.
    In: Jiří Wiedermann, Julius Stuller, Gerard Tel, Jaroslav Pokorny, and Mária Bieliková, editors, Proc. 32nd Internat. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM'06), volume 3831 of Lecture Notes in Computer Science, pages 166-175. Springer-Verlag, 2006.
    Joint work with Marc Benkert, Joachim Gudmundsson, and Herman Haverkort.
    [ html | pdf ]
  20. A polynomial-time approximation algorithm for a geometric dispersion problem.
    In: Danny Z. Chen and Der-Tsai Lee, editors, Proc. 12th Annu. Internat. Comput. Combinatorics Conf. (COCOON'06), volume 4112 of Lecture Notes in Computer Science, pages 166-175. Springer-Verlag, 2006.
    Joint work with Marc Benkert, Joachim Gudmundsson, Christian Knauer, Esther Moet, and René van Oostrum.
    [ html | pdf ]
  21. A polynomial-time approximation algorithm for a geometric dispersion problem.
    In: Proc. 22nd European Workshop on Computational Geometry (EWCG'06), pages 141-144, Delphi, 2006.
    Joint work with Marc Benkert, Joachim Gudmundsson, Christian Knauer, Esther Moet, and René van Oostrum.
    [ pdf ]
  22. Matching points with rectangles and squares.
    In: Jiří Wiedermann, Julius Stuller, Gerard Tel, Jaroslav Pokorny, and Mária Bieliková, editors, Proc. 32nd Internat. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM'06), volume 3831 of Lecture Notes in Computer Science, pages 177-186. Springer-Verlag, 2006.
    Joint work with Sergey Bereg and Nikolaus Mutsanas.
    [ html | pdf ]
  23. A new approximation algorithm for labeling weighted points with sliding labels.
    In: Proc. 22nd European Workshop on Computational Geometry (EWCG'06), pages 137-140, Delphi, 2006.
    Joint work with Thomas Erlebach, Torben Hagerup, Klaus Jansen, and Moritz Minzlaff.
    [ pdf ]
  24. Pseudo-convex decomposition of simple polygons.
    In: Proc. 22nd European Workshop on Computational Geometry (EWCG'06), pages 13-16, Delphi, 2006.
    Joint work with Stefan Gerdjikov.
    [ pdf ]
  25. Improved fixed-parameter algorithms for non-crossing subgraphs.
    In: Proc. ICALP Affiliated Workshop on Improving Exponential-Time Algorithms (iETA'06), pages 31-38, Venice, 2006.
    Joint work with Magnús M. Halldórsson and Takeshi Tokuyama.
    [ pdf ]
  26. Generalization of land cover maps by mixed integer programming.
    In: Proc. 14th Internat. ACM Symp. Advances in Geographic Information Systems (ACM-GIS'06), pages 75-82, 2006.
    Joint work with Jan-Henrik Haunert.
    [ html | pdf ]
  27. A mixed-integer program for drawing high-quality metro maps.
    In: Patrick Healy and Nikola S. Nikolov, editors, Proc. 13th Internat. Sympos. Graph Drawing (GD'05), volume 3843 of Lecture Notes in Computer Science, pages 321-333. Springer-Verlag, 2006.
    Joint work with Martin Nöllenburg.
    [ html | pdf ]
  28. Routing by landmarks.
    In: Proc. 6th Swiss Transport Research Conf. (STRC'06), Ascona, 2006.
    CD-ROM.
    Joint work with Urs-Jakob Rüetschi, David Caduff, Sabine Timpf, and Frank Schulz.
    [ html | pdf | abstract ]
  29. Constructing interference-minimal networks.
    In: Proc. 21st European Workshop on Computational Geometry (EWCG'05), pages 203-206, Eindhoven, 2005.
    Joint work with Marc Benkert, Joachim Gudmundsson, and Herman Haverkort.
    [ pdf ]
  30. Boundary labeling: Models and efficient algorithms for rectangular maps.
    In: János Pach, editor, Proc. 12th Internat. Sympos. Graph Drawing (GD'04), volume 3383 of Lecture Notes in Computer Science, pages 49-59. Springer-Verlag, 2005.
    Joint work with Michael A. Bekos, Michael Kaufmann, and Antonios Symvonis.
    [ html | pdf | abstract ]
  31. The minimum Manhattan network problem: A fast factor-3 approximation.
    In: Jin Akiyama, Mikio Kano, and Xuehou Tan, editors, Proc. 8th Japanese Conf. on Discrete and Computational Geometry (JCDCG'04), volume 3742 of Lecture Notes in Computer Science, pages 16-28. Springer-Verlag, 2005.
    Joint work with Marc Benkert and Florian Widmann.
    [ html | pdf ]
  32. Farthest-point queries with geometric and combinatorial constraints.
    In: Jin Akiyama, Mikio Kano, and Xuehou Tan, editors, Proc. 8th Japanese Conf. on Discrete and Computational Geometry (JCDCG'04), volume 3742 of Lecture Notes in Computer Science, pages 62-75. Springer-Verlag, 2005.
    Joint work with Ovidiu Daescu, Ningfang Mi, and Chan-Su Shin.
    [ html | pdf ]
  33. Constructing the city Voronoi diagram faster.
    In: Proc. 2nd Internat. Symp. on Voronoi Diagrams in Science and Engineering (VD'05), pages 162-172, Seoul, 2005.
    Joint work with Robert Görke.
    [ pdf ]
  34. Constructing the city Voronoi diagram faster.
    In: Proc. 21st European Workshop on Computational Geometry (EWCG'05), pages 155-158, Eindhoven, 2005.
    Joint work with Robert Görke.
    [ pdf ]
  35. Configurations with few crossings in topological graphs.
    In: Xiaotie Deng and Ding-Zhu Du, editors, Proc. 16th Annu. Internat. Symp. Algorithms Comput. (ISAAC'05), volume 3827 of Lecture Notes in Computer Science, pages 604-613. Springer-Verlag, 2005.
    Joint work with Christian Knauer, Étienne Schramm, and Andreas Spillner.
    [ html | pdf | abstract ]
  36. Spanning trees with few crossings in geometric and topological graphs.
    In: Proc. 21st European Workshop on Computational Geometry (EWCG'05), pages 195-198, Eindhoven, 2005.
    Joint work with Christian Knauer, Étienne Schramm, and Andreas Spillner.
    [ pdf ]
  37. Delineating boundaries for imprecise regions.
    In: Gerth Stølting Brodal and Stefano Leonardi, editors, Proc. 13th Annu. Europ. Symp. on Algorithms (ESA'05), volume 3669 of Lecture Notes in Computer Science, pages 143-154. Springer-Verlag, 2005.
    Joint work with Iris Reinbacher, Marc Benkert, Marc van Kreveld, and Joseph S.B. Mitchell.
    [ html | pdf ]
  38. Delineating boundaries for imprecise regions.
    In: Proc. 21st European Workshop on Computational Geometry (EWCG'05), pages 127-130, Eindhoven, 2005.
    Joint work with Iris Reinbacher, Marc Benkert, and Marc van Kreveld.
    [ pdf ]
  39. Optimal spanners for axis-aligned rectangles.
    In: Proc. 20th European Workshop on Computational Geometry (EWCG'04), pages 97-100, Sevilla, 2004.
    Joint work with Tetsuo Asano, Mark de Berg, Otfried Cheong, Hazel Everett, Herman Haverkort, and Naoki Katoh.
    [ pdf ]
  40. The minimum Manhattan network problem: A fast factor-3 approximation.
    In: Abstracts 8th Japanese Conf. on Discrete and Computational Geometry (JCDCG'04), pages 85-86, Tokyo, 2004.
    Joint work with Marc Benkert and Florian Widmann.
    [ pdf ]
  41. Farthest-point queries with geometric and combinatorial constraints.
    In: Proc. 20th European Workshop on Computational Geometry (EWCG'04), pages 45-48, Sevilla, 2004.
    Joint work with Ovidiu Daescu, Ningfang Mi, and Chan-Su Shin.
    [ pdf ]
  42. Farthest-point queries with geometric and combinatorial constraints.
    In: Abstracts 8th Japanese Conf. on Discrete and Computational Geometry (JCDCG'04), pages 110-111, Tokyo, 2004.
    Joint work with Ovidiu Daescu, Ningfang Mi, and Chan-Su Shin.
    [ pdf ]
  43. Algorithms for the placement of diagrams on maps.
    In: Dieter Pfoder, Isabel F. Cruz, and Marc Ronthaler, editors, Proc. 12th Internat. ACM Symp. Advances in Geographic Information Systems (ACM-GIS'04), pages 222-231. ACM Press, New York, 2004.
    Joint work with Marc van Kreveld and Étienne Schramm.
    [ pdf | abstract ]
  44. Web-based delineation of imprecise regions.
    In: Proc. Workshop on Geographic Information Retrieval at SIGIR'04, Sheffield, 2004.
    Joint work with Avi Arampatzis, Marc van Kreveld, Iris Reinbacher, Christopher B. Jones, Subodh Vaid, Paul Clough, Hideo Joho, Mark Sanderson, and Marc Benkert.
    [ pdf ]
  45. The minimum Manhattan network problem: Approximations and exact solutions.
    In: Proc. 20th European Workshop on Computational Geometry (EWCG'04), pages 209-212, Sevilla, 2004.
    Joint work with Marc Benkert and Takeshi Shirabe.
    [ pdf ]
  46. Approximating the geometric minimum-diameter spanning tree.
    In: Proc. 18th European Workshop on Computational Geometry (EWCG'02), pages 41-45, Warszawa, 2002.
    Joint work with Joachim Gudmundsson, Herman Haverkort, Sang-Min Park, and Chan-Su Shin.
    [ pdf | abstract ]
  47. Facility location and the geometric minimum-diameter spanning tree.
    In: Klaus Jansen, Stefano Leonardi, and Vijay Vazirani, editors, Proc. 5th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX'02), volume 2462 of Lecture Notes in Computer Science, pages 146-160. Springer-Verlag, 2002.
    Joint work with Joachim Gudmundsson, Herman Haverkort, Sang-Min Park, and Chan-Su Shin.
    [ html | pdf | abstract ]
  48. Labeling subway lines.
    In: Peter Eades and Tadao Takaoka, editors, Proc. 12th Annu. Internat. Symp. Algorithms and Computation (ISAAC'01), volume 2223 of Lecture Notes in Computer Science, pages 649-659. Springer-Verlag, 2001.
    Joint work with Mari Ángeles Garrido, Claudia Iturriaga, Alberto Márquez, José Ramon Portillo, and Pedro Reyes.
    [ html | pdf | abstract ]
  49. Etiquetado de puntos alineados.
    In: Proc. IX Encuentros de Geometría Computacional (EGC'01), pages 285-294, Girona, 2001.
    Joint work with Mari Ángeles Garrido, Alberto Márquez, Claudia Iturriaga, José Ramon Portillo, and Pedro Reyes.
    [ ps ]
  50. Labeling points with weights.
    In: Proc. 17th European Workshop on Computational Geometry (EWCG'01), pages 97-100, Berlin, 2001.
    Joint work with Sheung-Hung Poon, Chan-Su Shin, and Tycho Strijk.
    [ pdf | abstract ]
  51. Labeling points with weights.
    In: Peter Eades and Tadao Takaoka, editors, Proc. 12th Annu. Internat. Symp. Algorithms Comput. (ISAAC'01), volume 2223 of Lecture Notes in Computer Science, pages 610-622. Springer-Verlag, 2001.
    Joint work with Sheung-Hung Poon, Chan-Su Shin, and Tycho Strijk.
    [ html | pdf | abstract ]
  52. New algorithms for two-label point labeling.
    In: Mike Paterson, editor, Proc. 8th Annu. Europ. Symp. on Algorithms (ESA'00), volume 1879 of Lecture Notes in Computer Science, pages 368-379. Springer-Verlag, 2000.
    Joint work with Zhongping Qin, Yinfeng Xu, and Binhai Zhu.
    [ html | ps ]
  53. Ein neuer Algorithmus zur Beschriftung von Punkten mit je zwei Kreisen.
    In: Gesellschaft für Informatik e.V., editor, Tagungsband der Informatiktage'00, 2000.
    Joint work with Michael Thon and Yinfeng Xu.
  54. A better lower bound for two-circle point labeling.
    In: Der-Tsai Lee, editor, Proc. 11th Annu. Internat. Symp. Algorithms Comput. (ISAAC'00), volume 1969 of Lecture Notes in Computer Science, pages 422-431. Institute of Information Science, Academia Sinica, Springer-Verlag, 2000.
    Joint work with Michael Thon and Yinfeng Xu.
    [ pdf | abstract ]
  55. A simple and efficient algorithm for high-quality line labeling.
    In: Proc. 15th European Workshop on Computational Geometry (EWCG'99), pages 93-96, Sophia-Antipolis, 1999.
    Joint work with Pankaj K. Agarwal, Lars Knipping, Marc van Kreveld, and Tycho Strijk.
  56. Towards an evaluation of quality for label placement methods.
    In: Proc. 19th Internat. Cartographic Conf. (ICA'99), pages 905-913, Ottawa, 1999. Internat. Cartographic Association.
    Joint work with Steven van Dijk, Marc van Kreveld, and Tycho Strijk.
    [ pdf | abstract ]
  57. A simple and efficient algorithm for high-quality line labeling.
    In: David Martin and Fulong Wu, editors, Proc. 7th Annu. Geograph. Inform. Sci. Research Conf. UK (GISRUK'99), pages 146-150, Southampton, 1999.
    Joint work with Lars Knipping, Marc van Kreveld, Tycho Strijk, and Pankaj K. Agarwal.
  58. A combinatorial framework for map labeling.
    In: Sue H. Whitesides, editor, Proc. 6th Internat. Sympos. Graph Drawing (GD'98), volume 1547 of Lecture Notes in Computer Science, pages 316-331. Springer-Verlag, 1999.
    Joint work with Frank Wagner.
    [ ps ]
  59. Point set labeling with sliding labels.
    In: Proc. 14th Annu. ACM Sympos. Comput. Geom. (SoCG'98), pages 337-346, 1998.
    Joint work with Marc van Kreveld and Tycho Strijk.
    [ html | ps ]
  60. MakeIt! - Generating and maintaining makefiles automatically.
    In: Roberto Battini and Alan A. Bertossi, editors, Proc. Workshop on Algorithms and Experiments (ALEX'98), pages 165-174, Trento, 1998.
    Joint work with Sven Schönherr.
    [ html | ps | abstract ]
  61. An efficient and effective approximation algorithm for the map labeling problem.
    In: Paul Spirakis, editor, Proc. 3rd Annu. Europ. Symp. on Algorithms (ESA'95), volume 979 of Lecture Notes in Computer Science, pages 420-433. Springer-Verlag, 1995.
    Joint work with Frank Wagner.
    [ html | ps ]
  62. Fast and reliable map labeling.
    In: Horst Kremers und Werner Pillmann, editor, Proc. 9th Internat. Symp. Computer Science for Environment Protection (CSEP'95), pages 667-675. Metropolis, 1995.
    Joint work with Frank Wagner.
    [ ps ]
  63. Map labeling heuristics: Provably good and practically useful.
    In: Proc. 11th Annu. ACM Sympos. Comput. Geom. (SoCG'95), pages 109-118, 1995.
    Joint work with Frank Wagner.
    [ html | ps ]

Habilitation

  1. Geometrische Netzwerke und ihre Visualisierung.
    Habilitation, Fakultät für Informatik, Universität Karlsruhe, June 2005.
    [ pdf ]

Dissertation

  1. Automated label placement in theory and practice.
    PhD thesis, Fachbereich Mathematik und Informatik, Freie Universität Berlin, May 1999.
    [ pdf ]

Diplomarbeit

  1. Map labeling.
    Master's thesis, Fachbereich Mathematik und Informatik, Freie Universität Berlin, May 1995.
    [ ps ]

Technische Berichte

  1. Cover contact graphs.
    Technical Report 2007-18, Fakultät für Informatik, Universität Karlsruhe, September 2007.
    Available at „http://www.ubka.uni-karlsruhe.de/indexer-vvv/ira/2007/18“.
    Joint work with Nieves Atienza, Natalia de Castro, Carmen Cortés, M. Ángeles Garrido, Clara I. Grima, Gregorio Hernández, Alberto Márquez, Auxiliadora Moreno, Martin Nöllenburg, José Ramon Portillo, Pedro Reyes, Jesús Valenzuela, and Maria Trinidad Villar.
    [ html | pdf ]
  2. Computing large matchings fast.
    Technical Report 2007-19, Fakultät für Informatik, Universität Karlsruhe, 2007.
    Available at „http://digbib.ubka.uni-karlsruhe.de/volltexte/1000007350“.
    Joint work with Ignaz Rutter.
    [ html | pdf ]
  3. A polynomial-time approximation algorithm for a geometric dispersion problem.
    Technical Report 2006-8, Fakultät für Informatik, Universität Karlsruhe, 2006.
    Available at „http://digbib.ubka.uni-karlsruhe.de/volltexte/1000005162“.
    Joint work with Marc Benkert, Joachim Gudmundsson, Christian Knauer, Esther Moet, and René van Oostrum.
    [ html | ps ]
  4. Configurations with few crossings in topological graphs.
    Technical Report 2005-24, Fakultät für Informatik, Universität Karlsruhe, September 2005.
    Available at „http://digbib.ubka.uni-karlsruhe.de/volltexte/1000004122“.
    Joint work with Christian Knauer, Étienne Schramm, and Andreas Spillner.
    [ html | pdf ]
  5. Optimal spanners for axis-aligned rectangles.
    Technical Report UU-CS-2004-008, Department of Computer Science, Utrecht University, 2004.
    Joint work with Tetsuo Asano, Mark de Berg, Otfried Cheong, Hazel Everett, Herman Haverkort, and Naoki Katoh.
    [ pdf ]
  6. Boundary labeling: Models and efficient algorithms for rectangular maps.
    Technical Report 2004-15, Fakultät für Informatik, Universität Karlsruhe, 2004.
    Available at „http://digbib.ubka.uni-karlsruhe.de/volltexte/1000001841“.
    Joint work with Michael A. Bekos, Michael Kaufmann, and Antonios Symvonis.
    [ html | pdf ]
  7. The minimum Manhattan network problem: A fast factor-3 approximation.
    Technical Report 2004-16, Fakultät für Informatik, Universität Karlsruhe, 2004.
    Available at „http://digbib.ubka.uni-karlsruhe.de/volltexte/1000003164“.
    Joint work with Marc Benkert and Florian Widmann.
    [ html | pdf ]
  8. Beschriftungsalgorithmen in Theorie & Praxis.
    Technical Report 13/2002, Institut für Mathematik und Informatik, Universität Greifswald, April 2002.
    Available at „www.math-inf.uni-greifswald.de/preprints/shadow/wolff02_13.rdf.html“.
    Joint work with Katharina Bach, Kristina Hanig, Tim Hoffmann, Wolfgang Kresse, Julia Löcherbach, Paul Rosenthal, Steffen Rudnick, Peter Schreiber, and Michael Thon.
    [ html | pdf ]
  9. Approximating the geometric minimum-diameter spanning tree.
    Technical Report 4/2002, Institut für Mathematik und Informatik, Universität Greifswald, March 2002.
    Available at „www.math-inf.uni-greifswald.de/preprints/shadow/wolff02_4.rdf.html“.
    Joint work with Joachim Gudmundsson, Herman Haverkort, Sang-Min Park, and Chan-Su Shin.
    [ html | pdf | abstract ]
  10. Labeling points with weights.
    Technical Report 7/2001, Institut für Mathematik und Informatik, Universität Greifswald, May 2001.
    Joint work with Sheung-Hung Poon, Chan-Su Shin, and Tycho Strijk.
    [ html | pdf | abstract ]
  11. Towards an evaluation of quality for names placement methods.
    Technical Report UU-CS-2001-43, Department of Computer Science, Utrecht University, 2001.
    Joint work with Steven van Dijk, Marc van Kreveld, and Tycho Strijk.
    [ pdf ]
  12. A simple and efficient algorithm for high-quality line labeling.
    Technical Report UU-CS-2001-44, Department of Computer Science, Utrecht University, 2001.
    Joint work with Lars Knipping, Marc van Kreveld, Tycho Strijk, and Pankaj K. Agarwal.
    [ pdf ]
  13. A simple proof for the NP-hardness of edge labeling.
    Technical Report 11/2000, Institut für Mathematik und Informatik, Universität Greifswald, September 2000.
    [ html | pdf | abstract ]
  14. A generic design concept for geometric algorithms.
    Technical Report B 00-10, Institut für Informatik, Fachbereich Mathematik und Informatik, Freie Universität Berlin, June 2000.
    Joint work with Vikas Kapoor and Dietmar Kühl.
    [ ps ]
  15. New algorithms for two-label point labeling.
    Technical Report HKUST-TCSC-2000-06, Hongkong University of Science and Technology, June 2000.
    Joint work with Zhongping Qin, Yinfeng Xu, and Binhai Zhu.
    [ html | ps ]
  16. Labeling points with circles.
    Technical Report B 99-08, Institut für Informatik, Freie Universität Berlin, April 1999.
    Joint work with Tycho Strijk.
    [ abstract ]
  17. Point set labeling with sliding labels.
    Technical Report UU-CS-1998-40, Department of Computer Science, Utrecht University, 1998.
    Joint work with Marc van Kreveld and Tycho Strijk.
    [ pdf ]
  18. Map labeling heuristics: Provably good and practically useful.
    Technical Report B 95-04, Institut für Informatik, Freie Universität Berlin, April 1995.
    Joint work with Frank Wagner.
    [ ps ]