Algorithms and Data Structures

This volume contains the papers presented at the 11th Algorithms and Data Structures Symposium, WADS 2009 (formerly Workshop on Algorithms and Data Structures), held during August 21-23, 2009 in Ban?, Alberta, Canada. WADS alternates with the Scandinavian Workshop on Algorithms Theory (SWAT), continuing the tradition of SWAT and WADS starting with SWAT 1988 and WADS 1989. Inresponsetothecallforpapers,126papersweresubmitted. Fromtheses- missions, the ProgramCommittee selected 49 papers for presentation at WADS 2009. In addition, invited lectures were given by the following distinguished researchers: Erik Demaine, Richard Karp, and Christos Papadimitriou. On behalf of the Program Committee, we would like to express our appre- ation to the invited speakers, reviewers and all authors who submitted papers. May 2009 Frank Dehne Marina Gavrilova J] org-Ru ]diger Sack Csaba D. T´ oth Conference Organization Program Chairs Frank Dehne Marina Gavrilova Joerg-Ruediger Sack Csaba D. Toth Program Committee Sergei Bereg Allan Borodin Gerth Stolting Brodal Timothy Chan Mark de Berg Frank Devai Matt Duckham Rolf Fagerberg Randolph Franklin Joachim Gudmundsson Susanne Hambrusch Rolf Klein Mike Langston Ming Li Friedhelm Meyer auf der Heide Ian Munro Jon Rokne Shashi Shekhar Bettina Speckmann Paul Spirakis Gabor Tardos Je? Vitter Frances F. Yao Local Organization Marina Gavrilova Csaba D. Toth Jon Rokne Maruf Monwar Kushan Ahmadian Table of Contents On the Power of the Semi-Separated Pair Decomposition. . . . . . . . . . . . . . 1 Mohammad Ali Abam, Paz Carmi, Mohammad Farshi, and Michiel Smid Plane Graphs with Parity Constraints. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

This book constitutes the refereed proceedings of the 11th Algorithms and Data Structures Symposium, WADS 2009, held in Banff, Canada, in August 2009.

The Algorithms and Data Structures Symposium - WADS (formerly "Workshop on Algorithms and Data Structures") is intended as a forum for researchers in the area of design and analysis of algorithms and data structures. The 49 revised full papers presented in this volume were carefully reviewed and selected from 126 submissions. The papers present original research on algorithms and data structures in all areas, including bioinformatics, combinatorics, computational geometry, databases, graphics, and parallel and distributed computing.