| 2009 | Computing the Implicit Voronoi Diagram in Triple Precision. | David L. Millman, Jack Snoeyink |
| 2009 | Streaming Embeddings with Slack. | Christiane Lammersen, Anastasios Sidiropoulos, Christian Sohler |
| 2009 | Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality. | Lukasz Kowalik, Marcin Mucha |
| 2009 | Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem. | Martin Knauer, Joachim Spoerhase |
| 2009 | A Scheme for Computing Minimum Covers within Simple Regions. | Matthew J. Katz, Gila Morgenstern |
| 2009 | A Pseudopolynomial Algorithm for Alexandrov's Theorem. | Daniel Kane, Gregory N. Price, Erik D. Demaine |
| 2009 | Inspecting a Set of Strips Optimally. | Tom Kamphans, Elmar Langetepe |
| 2009 | Two for One: Tight Approximation of 2D Bin Packing. | Klaus Jansen, Lars Prdel, Ulrich M. Schwarz |
| 2009 | The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs. | Krishnam Raju Jampani, Anna Lubiw |
| 2009 | Reconfiguration of List Edge-Colorings in a Graph. | Takehiro Ito, Marcin Kaminski, Erik D. Demaine |
| 2009 | Approximation Algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments. | Farzad Hassanzadeh, David Rappaport |
| 2009 | Rank-Balanced Trees. | Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan |
| 2009 | Dynamic Graph Clustering Using Minimum-Cut Trees. | Robert Grke, Tanja Hartmann, Dorothea Wagner |
| 2009 | New Results on Visibility in Simple Polygons. | Alexander Gilbers, Rolf Klein |
| 2009 | Worst-Case Optimal Adaptive Prefix Coding. | Travis Gagie, Yakov Nekrich |
| 2009 | Online Square Packing. | Sndor P. Fekete, Tom Kamphans, Nils Schweer |
| 2009 | Optimal Embedding into Star Metrics. | David Eppstein, Kevin A. Wortman |
| 2009 | The | David Eppstein, Emma S. Spiro |
| 2009 | Orientation-Constrained Rectangular Layouts. | David Eppstein, Elena Mumford |
| 2009 | On Reconfiguration of Disks in the Plane and Related Problems. | Adrian Dumitrescu, Minghui Jiang |
| 2009 | On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem. | Wenliang Du, David Eppstein, Michael T. Goodrich, George S. Lueker |
| 2009 | Finding a Hausdorff Core of a Polygon: On Convex Polygon Containment with Bounded Hausdorff Distance. | Reza Dorrigiv, Stephane Durocher, Arash Farzan, Robert Fraser, Alejandro Lpez-Ortiz, J. Ian Munro, Alejandro Salinger, Matthew Skala |
| 2009 | Drawing Graphs with Right Angle Crossings. | Walter Didimo, Peter Eades, Giuseppe Liotta |
| 2009 | Skip-Splay: Toward Achieving the Unified Bound in the BST Model. | Jonathan Derryberry, Daniel Dominic Sleator |
| 2009 | Algorithms Meet Art, Puzzles, and Magic. | Erik D. Demaine |