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. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . von Dehne, Frank