| 2019 | WADS | Geometric Firefighting in the Half-Plane. | Sang-Sub Kim, Rolf Klein, David Kbel, Elmar Langetepe, Barbara Schwarzwald |
| 2018 | ISAAC | Partially Walking a Polygon. | Franz Aurenhammer, Michael Steinkogler, Rolf Klein |
| 2014 | LATIN | Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems. | Rolf Klein, Christos Levcopoulos, Andrzej Lingas |
| 2013 | ICALP | On the Complexity of Higher Order Abstract Voronoi Diagrams. | Cecilia Bohler, Panagiotis Cheilaris, Rolf Klein, Chih-Hung Liu, Evanthia Papadopoulou, Maksym Zavershynskyi |
| 2013 | ISAAC | Abstract Voronoi Diagrams with Disconnected Regions. | Cecilia Bohler, Rolf Klein |
| 2012 | COCOON | Optimally Solving a Transportation Problem Using Voronoi Diagrams. | Darius Gei, Rolf Klein, Rainer Penninger |
| 2011 | ESA | Tolerant Algorithms. | Rolf Klein, Rainer Penninger, Christian Sohler, David P. Woodruff |
| 2010 | ISAAC | Spanning Ratio and Maximum Detour of Rectilinear Paths in the | Ansgar Grne, Tien-Ching Lin, Teng-Kai Yu, Rolf Klein, Elmar Langetepe, D. T. Lee, Sheung-Hung Poon |
| 2009 | WADS | New Results on Visibility in Simple Polygons. | Alexander Gilbers, Rolf Klein |
| 2008 | AAIM | A Meeting Scheduling Problem Respecting Time and Space. | Florian Berger, Rolf Klein, Doron Nussbaum, Jrg-Rdiger Sack, Jiehua Yi |
| 2007 | AAIM | Approximating the Maximum Independent Set and Minimum Vertex Coloring on Box Graphs. | Xin Han, Kazuo Iwama, Rolf Klein, Andrzej Lingas |
| 2006 | GD | Computing Geometric Minimum-Dilation Graphs Is NP-Hard. | Rolf Klein, Martin Kutz |
| 2005 | COCOON | Exploring Simple Grid Polygons. | Christian Icking, Thomas Kamphans, Rolf Klein, Elmar Langetepe |
| 2005 | ISAAC | Embedding Point Sets into Plane Graphs of Small Dilation. | Annette Ebbers-Baumann, Ansgar Grne, Marek Karpinski, Rolf Klein, Christian Knauer, Andrzej Lingas |
| 2005 | ISAAC | Exact and Approximation Algorithms for Computing the Dilation Spectrum of Paths, Trees, and Cycles. | Rolf Klein, Christian Knauer, Giri Narasimhan, Michiel H. M. Smid |
| 2005 | WADS | On Geometric Dilation and Halving Chords. | Adrian Dumitrescu, Annette Ebbers-Baumann, Ansgar Grne, Rolf Klein, Gnter Rote |
| 2004 | ESA | Competitive Online Approximation of the Optimal Search Ratio. | Rudolf Fleischer, Thomas Kamphans, Rolf Klein, Elmar Langetepe, Gerhard Trippen |
| 2004 | WAFR | Online Searching with an Autonomous Robot. | Sndor P. Fekete, Rolf Klein, Andreas Nchter |
| 2003 | ISAAC | On the Geometric Dilation of Finite Point Sets. | Annette Ebbers-Baumann, Ansgar Grne, Rolf Klein |
| 2002 | ISAAC | Maximizing a Voronoi Region: The Convex Case. | Frank K. H. A. Dehne, Rolf Klein, Raimund Seidel |
| 2001 | ESA | Smallest Color-Spanning Objects. | Manuel Abellanas, Ferran Hurtado, Christian Icking, Rolf Klein, Elmar Langetepe, Lihong Ma, Beln Palop, Vera Sacristn |
| 2001 | ESA | A Fast Algorithm for Approximating the Detour of a Polygonal Chain. | Annette Ebbers-Baumann, Rolf Klein, Elmar Langetepe, Andrzej Lingas |
| 2000 | IV | BibRelEx: Exploring Bibliographic Databases by Visualization of Annotated Contents-Based Relations. | Anne Brggemann-Klein, Rolf Klein, Britta Landgraf |
| 1999 | STACS | An Optimal Competitive Strategy for Walking in Streets. | Christian Icking, Rolf Klein, Elmar Langetepe |
| 1998 | ISAAC | Generalized Self-Approaching Curves. | Oswin Aichholzer, Franz Aurenhammer, Christian Icking, Rolf Klein, Elmar Langetepe, Gnter Rote |
| 1997 | SODA | A Competitive Strategy for Learning a Polygon. | Frank Hoffmann, Christian Icking, Rolf Klein, Klaus Kriegel |
| 1995 | ESA | Fast Skeleton Construction. | Rolf Klein, Andrzej Lingas |
| 1994 | ISAAC | Hamiltonian Abstract Voronoi Diagrams in Linear Time. | Rolf Klein, Andrzej Lingas |
| 1994 | MFCS | "The Big Sweep": On the Power of the Wavefront Approach to Voronoi Diagrams. | Frank K. H. A. Dehne, Rolf Klein |
| 1991 | FOCS | Walking an Unknown Street with Bounded Detour | Rolf Klein |
| 1989 | WG | Combinatorial Properties of Abstract Voronoi Diagrams. | Rolf Klein |
| 1988 | STACS | Voronoi Diagrams Based on General Metrics in the Plane. | Rolf Klein, Derick Wood |
| 1988 | WG | Voronoi Diagrams in the Moscow Metric (Extended Abstract). | Rolf Klein |
| 1987 | WG | A Sweepcircle Algorithm for Voronoi Diagrams. | Frank K. H. A. Dehne, Rolf Klein |
| 1987 | WG | Priority Search Trees in Secondary Memory (Extended Abstract). | Christian Icking, Rolf Klein, Thomas Ottmann |
| 1986 | WG | The Node Visit Cost of Brother Trees. | Rolf Klein, Derick Wood |