Algorithms and Data Structures

The papers in this volume were presented at the 9th Workshop on Algorithms and Data Structures (WADS 2005). The workshop took place during August 15 - 17, 2005, at the University of Waterloo, Waterloo, Canada. The workshop alternateswith the ScandinavianWorkshopon Algorithm Theory(SWAT), c- tinuing the traditionof SWAT and WADS startingwith SWAT 1988and WADS 1989. From 90 submissions, the Program Committee selected 37 papers for p- sentation at the workshop. In addition, invited lectures were given by the f- lowing distinguished researchers: Allan Borodin and Max J. Egenhofer. OnbehalfoftheProgramCommittee,wewouldliketoexpressoursincere- preciation to the many persons whose e?ort contributed to making WADS 2005 a success. These include the invited speakers,members of the ste- ing and ProgramCommittees, the authors who submitted papers, and the many referees who assisted the ProgramCommittee. We are indebted to Robert Kane forinstallingandmodifyingthesubmissionsoftware,maintainingthesubmission server and interacting with authors as well as for helping with the preparation of the program. August 2005 Frank Dehne, Alejandro Lop ' ez-Ortiz, and Jorg-R .. u ..diger Sack WADS Organization Organizing Institutions Steering Committee Frank Dehne Carleton University, Canada Ian Munro University of Waterloo, Canada J.. org-Rudig .. er Sack Carleton University, Canada Roberto Tamassia Brown University, Canada Program Co-chairs Frank Dehne Carleton University, Canada Alejandro Lop ' ez-Ortiz University of Waterloo, Canada J.. org-Rudig .. er Sack Carleton University, Canada Conference Chair Alejandro Lop ' ez-Ortiz University of Waterloo, Canada Program Committee Pankaj Agarwal Duke University, USA Michael Atkinson University of Otago, New Zealand Gill Barequet Technion, Israel Mark de Berg Tech.