List of accepted papers for WADS 2009:


Piotr Berman, Bhaskar DasGupta and Marek Karpinski. 
Approximating Transitive Reductions for Directed Networks 

Adrian Dumitrescu and Minghui Jiang. 
On reconfiguration of disks in the plane and related problems 

Bourgeois Nicolas, Bruno Escoffier and Vangelis Paschos. 
Efficient approximation of combinatorial problems by moderately exponential algorithms 

Atlas F. Cook IV and Carola Wenk. 
Shortest Path Problems on a Polyhedral Surface 

Joan Boyar, Sandy Irani and Kim S. Larsen. 
A Comparison of Performance Measures for Online Algorithms 

Artur Czumaj, Jurek Czyzowicz, Leszek Gasieniec, Jesper Jansson, Andrzej Lingas and Pawe? ?yli?ski. 
Approximation Algorithms for Buy-at-Bulk Geometric Network Design 

Travis Gagie and Yakov Nekrich. 
Worst-Case Optimal Adaptive Prefix Coding 

Farzad Hassanzadeh and David Rappaport. 
Approximation Algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments 

Tom Kamphans and Elmar Langetepe. 
Inspecting a Set of Strips Optimally 

Mathias Weller, Christian Komusiewicz, Rolf Niedermeier and Johannes Uhlmann. 
On Making Directed Graphs Transitive 

David Eppstein and Elena Mumford. 
Orientation-Constrained Rectangular Layouts 

Wenliang Du, David Eppstein, Michael Goodrich and George Lueker. 
On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem 

David Eppstein and Emma S. Spiro. 
The h-index of a graph and its application to dynamic subgraph statistics 

Sandor Fekete, Tom Kamphans and Nils Schweer. 
Online Square Packing 

Walter Didimo, Peter Eades and Giuseppe Liotta. 
Drawing Graphs with Right Angle Crossings 

Chenyu Yan, Yang Xiang and Feodor Dragan. 
Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs 

David Eppstein and Kevin Wortman. 
Optimal embedding into star metrics 

Takehiro Ito, Marcin Kaminski and Erik D. Demaine. 
Reconfiguration of List Edge-Colorings in a Graph 

Christiane Lammersen, Anastasios Sidiropoulos and Christian Sohler. 
Streaming Embeddings with Slack 

Mohammad Ali Abam, Paz Carmi, Mohammad Farshi and Michiel Smid. 
On the Power of the Semi-Separated Pair Decomposition 

Karim Dou?eb and Prosenjit Bose. 
Efficient Construction of Near-Optimal Binary and Multiway Search Trees 

Krishnam Raju Jampani and Anna Lubiw. 
The Simultaneous Membership Problem for Chordal, Comparability and Permutation graphs 

Prosenjit Bose, John Howat and Pat Morin. 
A Distribution-Sensitive Dictionary with Low Space Overhead 

G?nter Rote and Andr? Schulz. 
Resolving Loads with Positive Interior Stresses 

Prosenjit Bose, Meng He, Anil Maheshwari and Pat Morin. 
Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing 

Klaus Jansen, Lars Pr?del and Ulrich M. Schwarz. 
Two for One: Tight approximation of 2D Bin Packing 

Matthew J. Katz and Gila Morgenstern. 
A Scheme for Computing Minimum Covers within Simple Regions 

Allan Gr?nlund J?rgensen, Gerth St?lting Brodal and Thomas M?lhave. 
Fault Tolerant External Memory Algorithms 

Robert G?rke, Tanja Hartmann and Dorothea Wagner. 
Dynamic Graph Clustering Using Minimum-Cut Trees 

Alexander Gilbers and Rolf Klein. 
New Results on Visibility in Simple Polygons 

Lukasz Kowalik and Marcin Mucha. 
Two approximation algorithms for ATSP with strengthened triangle inequality 

Hiroaki Yamamoto and Daichi Takenouchi. 
Bit-Parallel Tree Pattern Matching Algorithms for Unordered Labeled Trees 

Jonathan Derryberry and Daniel Sleator. 
Skip-Splay: Toward Achieving the Unified Bound in the BST Model 

Piotr Berman, Marek Karpinski and Alex Zelikovsky. 
1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2 

Brian Dean and Zachary Jones. 
Rank-Sensitive Priority Queues 

Kevin Buchin, Maarten L?ffler, Pat Morin and Wolfgang Mulzer. 
Delaunay Triangulation of Imprecise Points Simplified and Extended 

Oswin Aichholzer, Thomas Hackl, Michael Hoffmann, Alexander Pilz, Guenter Rote, Bettina Speckmann and Birgit Vogtenhuber. 
Plane Graphs with Parity Constraints 

Martin Knauer and Joachim Spoerhase. 
Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem 

Patrizio Angelini, Fabrizio Frati and Michael Kaufmann. 
Straight-Line Rectangular Drawings of Clustered Graphs 

Brad Ballinger, David Charlton, Erik D. Demaine, Martin L. Demaine, John Iacono, Ching-Hao Liu and Sheung-Hung Poon. 
Minimal Locked Trees 

Boris Aronov, Kevin Buchin, Maike Buchin, Marc van Kreveld, Maarten L?ffler, Jun Luo, Rodrigo Silveira and Bettina Speckmann.
Connect the Dot: Computing Feed-links with Minimum Dilation 

Spyros Angelopoulos. 
Online Priority Steiner Tree Problems 

David L. Millman and Jack Snoeyink. 
Computing the implicit Voronoi diagram in triple precision 

Reza Dorrigiv, Stephane Durocher, Arash Farzan, Robert Fraser, Alejandro Lopez-Ortiz, J. Ian Munro, Alejandro Salinger and Matthew Skala. 
Finding a Hausdorff Core of a Polygon: On Convex Polygon Containment with Bounded Hausdorff Distance 

Daniel Kane, Gregory N. Price and Erik D. Demaine. 
A pseudopolynomial algorithm for Alexandrov's Theorem 

Jianer Chen and Yang Liu. 
An Improved Algorithm for the General Satisfiability Problem 

Nadia Benbernou, Prosenjit Bose, David Bremner, Erik Demaine, Martin Demaine, Ferran Hurtado, Vera Sacristan and Perouz Taskakian. 
Efficient Reconfiguration of Pivoting Tiles 

Andreas S. Schulz, James Orlin and Abraham Punnen. 
Integer Programming: Optimization and Evaluation are Equivalent 

Bernhard Haeupler, Siddhartha Sen and Robert E. Tarjan. 
Balanced Trees Simplified