| 2009 | A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs. Louis Ibarra |
| 2009 | A Separator Theorem for String Graphs and Its Applications. Jacob Fox, János Pach |
| 2009 | Algorithms for Computing Diffuse Reflection Paths in Polygons. Subir Kumar Ghosh, Partha P. Goswami, Anil Maheshwari, Subhas C. Nandy, Sudebkumar Prasant Pal, Swami Sarvattomananda |
| 2009 | All Farthest Neighbors in the Presence of Highways and Obstacles. Sang Won Bae, Matias Korman, Takeshi Tokuyama |
| 2009 | An Improved Upward Planarity Testing Algorithm and Related Applications. Sarmad Abbasi, Patrick Healy, Aimal Rextin |
| 2009 | Approximating Shortest Paths in Graphs. Sandeep Sen |
| 2009 | Colinear Coloring on Graphs. Kyriaki Ioannidou, Stavros D. Nikolopoulos |
| 2009 | Core and Conditional Core Path of Specified Length in Special Classes of Graphs. Balasubramanian Sivan, S. Harini, C. Pandu Rangan |
| 2009 | Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings. Tamara Mchedlidze, Antonios Symvonis |
| 2009 | Efficient Enumeration of Ordered Trees with kLeaves (Extended Abstract). Katsuhisa Yamanaka, Yota Otachi, Shin-Ichi Nakano |
| 2009 | Foundations of Exact Rounding. Chee-Keng Yap, Jihun Yu |
| 2009 | Generating All Triangulations of Plane Graphs (Extended Abstract). Mohammad Tanvir Parvez, Md. Saidur Rahman, Shin-Ichi Nakano |
| 2009 | Improved Algorithm for a Widest 1-Corner Corridor. Gautam K. Das, Debapriyay Mukhopadhyay, Subhas C. Nandy |
| 2009 | Line Transversals and Pinning Numbers. Otfried Cheong |
| 2009 | Matched Drawability of Graph Pairs and of Graph Triples. Luca Grilli, Seok-Hee Hong, Giuseppe Liotta, Henk Meijer, Stephen K. Wismath |
| 2009 | Maximum Neighbour Voronoi Games. Md. Muhibur Rasheed, Masud Hasan, M. Sohel Rahman |
| 2009 | Minimum Cuts of Simple Graphs in Almost Always Linear Time. Michael Brinkmeier |
| 2009 | Minmax Tree Cover in the Euclidean Space. Seigo Karakawa, Ehab Morsy, Hiroshi Nagamochi |
| 2009 | Network Design with Weighted Degree Constraints. Takuro Fukunaga, Hiroshi Nagamochi |
| 2009 | Object Caching for Queries and Updates. Philip Little, Amitabh Chaudhary |
| 2009 | On Exact Solutions to the Euclidean Bottleneck Steiner Tree Problem. Sang Won Bae, Chunseok Lee, Sunghee Choi |
| 2009 | On the Computational Complexity of Monotone Constraint Satisfaction Problems. Miki Hermann, Florian Richoux |
| 2009 | Parameterized Complexity of Stabbing Rectangles and Squares in the Plane. Michael Dom, Michael R. Fellows, Frances A. Rosamond |
| 2009 | Random Generation and Enumeration of Proper Interval Graphs. Toshiki Saitoh, Katsuhisa Yamanaka, Masashi Kiyomi, Ryuhei Uehara |
| 2009 | Recognition of Unigraphs through Superposition of Graphs (Extended Abstract). Alessandro Borri, Tiziana Calamoneri, Rossella Petreschi |
| 2009 | Recursive Generation of 5-Regular Planar Graphs. Mahdieh Hasheminezhad, Brendan D. McKay, Tristan Reeves |
| 2009 | Shape Matching by Random Sampling. Helmut Alt, Ludmila Scharf |
| 2009 | Shortest Gently Descending Paths. Mustaq Ahmed, Anna Lubiw, Anil Maheshwari |
| 2009 | Spherical-Rectangular Drawings. Mahdieh Hasheminezhad, S. Mehdi Hashemi, Brendan D. McKay |
| 2009 | Straight-Line Grid Drawings of Label-Constrained Outerplanar Graphs with O(nlogn) Area (Extended Abstract). Muhammad Rezaul Karim, Md. Jawaherul Alam, Md. Saidur Rahman |
| 2009 | The ExemplarBreakpointDistancefor Non-trivial Genomes Cannot Be Approximated. Guillaume Blin, Guillaume Fertin, Florian Sikora, Stéphane Vialette |
| 2009 | The Generalized Stable Allocation Problem. Brian C. Dean, Namrata Swar |
| 2009 | The Minimal Manhattan Network Problem in Three Dimensions. Xavier Muñoz, Sebastian Seibert, Walter Unger |
| 2009 | The Planar k-Means Problem is NP-Hard. Meena Mahajan, Prajakta Nimbhorkar, Kasturi R. Varadarajan |
| 2009 | WALCOM: Algorithms and Computation, Third International Workshop, WALCOM 2009, Kolkata, India, February 18-20, 2009. Proceedings Sandip Das, Ryuhei Uehara |