This book constitutes the refereed proceedings of the 14th Algorithms and Data Structures Symposium, WADS 2015, held in Victoria, BC, Canada, August 2015. The 54 revised full papers presented in this volume were carefully reviewed and selected from 148 submissions. The Algorithms and Data Structures Symposium - WADS (formerly Workshop on Algorithms And Data Structures), which alternates with the Scandinavian Workshop on Algorithm Theory, is intended as a forum for researchers in the area of design and analysis of algorithms and data structures. WADS includes papers presenting original research on algorithms and data structures in all areas, including bioinformatics, combinatorics, computational geometry, databases, graphics, and parallel and distributed computing.

This book constitutes the refereed proceedings of the 14th Algorithms and Data Structures Symposium, WADS 2015, held in Victoria, BC, Canada, August 2015. The 54 revised full papers presented in this volume were carefully reviewed and selected from 148 submissions. The Algorithms and Data Structures Symposium - WADS (formerly Workshop on Algorithms And Data Structures), which alternates with the Scandinavian Workshop on Algorithm Theory, is intended as a forum for researchers in the area of design and analysis of algorithms and data structures. WADS includes papers presenting original research on algorithms and data structures in all areas, including bioinformatics, combinatorics, computational geometry, databases, graphics, and parallel and distributed computing.

Thecentralchallengeoftheoreticalcomputerscienceistodeploymathematicsin waysthatservethecreationofusefulalgorithms. Inrecentyearstherehasbeena growinginterest in the two-dimensionalframework of parameterizedcomplexity, where, in addition to the overall input size, one also considers a parameter,with a focus on how these two dimensions interact in problem complexity. This book presents the proceedings of the 1st InternationalWorkshopon - rameterized and Exact Computation (IWPEC 2004,http://www. iwpec. org), which took place in Bergen, Norway, on September 14-16, 2004. The workshop was organized as part of ALGO 2004. There were seven previous workshops on the theory and applications of parameterized complexity. The ?rst was - ganized at the Institute for the Mathematical Sciences in Chennai, India, in September, 2000. The second was held at Dagstuhl Castle, Germany, in July, 2001. In December, 2002, a workshop on parameterized complexity was held in conjunction with the FST-TCS meeting in Kanpur, India. A second Dagstuhl workshop on parameterized complexity was held in July, 2003.Another wo- shoponthesubjectwasheldinOttawa,Canada,inAugust,2003,inconjunction with the WADS 2003 meeting. There have also been two Barbados workshops on applications of parameterized complexity. In response to the IWPEC 2004 call for papers, 47 papers were submitted, and from these the programcommittee selected 25 for presentation at the wo- shop. Inaddition,invitedlectureswereacceptedbythedistinguishedresearchers Michael Langston and Gerhard Woeginger.

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.

The refereed proceedings of the 8th International Workshop on Algorithms and Data Structures, WADS 2003, held in Ottawa, Ontario, Canada, in July/August 2003. The 40 revised full papers presented together with 4 invited papers were carefully reviewed and selected from 126 submissions. A broad variety of current aspects in algorithmics and data structures is addressed.

The papers in this volume were presented at the Seventh Workshop on Al- rithms and Data Structures (WADS 2001). The workshop took place August 8-10, 2001 in Providence, Rhode Island, USA. The workshop alternates with the Scandinavian Workshop on Algorithms Theory (SWAT), continuing the t- dition of SWAT and WADS starting with SWAT '88 and WADS '89. In response to the call for papers, 89 papers were submitted. From these submissions, the program committee selected 40 papers for presentation at the workshop. In addition invited plenary lectures were given by the following - stinguished researchers: Mikhail J. Atallah, F. Thomson Leighton, and Mihalis Yannakakis. On behalf of the program committee, we would like to express our apprec- tion to the invited speakers and to all the authors who submitted papers. August 2001 Frank Dehne J.. org-Rudiger .. Sack Roberto Tamassia Organization Conference Chair Roberto Tamassia (Brown) Program Committee Chairs Frank Dehne (Carleton) J.. org-Rudiger .. Sack (Carleton) Roberto Tamassia (Brown) Program Committee Alberto Apostolico (Purdue, Padova) Giuseppe Liotta (Perugia) Timothy Chan (Waterloo) Ernst W. Mayr (Munc .. hen) Bruno Codenotti (IMC) Joseph S.B. Mitchell (SUNY) Giuseppe Di Battista (Roma Tre) Stefan N.. aher (Trier) Shlomi Dolev (Ben-Gurion) Takao Nishizeki (Tohoku) Martin Farach-Colton Viktor K. Prasanna (USC) (Rutgers, Google) Enrico Puppo (Genova) Pierre Fraigniaud (LRI) Jose Rolim (Geneva) Harold N. Gabow (Colorado) Jack Snoeyink (UNC) Sally A. Goldman (Washington) Ioannis G. Tollis (UTD) Michael T.

The papers in this volume were presented at the Sixth Workshop on Algorithms and Data Structures (WADS ''99). The workshop took place August 11 - 14, 1999, in Vancouver, Canada. The workshop alternates with the Scandinavian Workshop on Algorithms Theory (SWAT), continuing the tradition of SWAT and WADS starting with SWAT''88 and WADS''89. In response to the program committee''s call for papers, 71 papers were submitted. From these submissions, the program committee selected 32 papers for presentation at the workshop. In addition to these submitted papers, the program committee invited the following researchers to give plenary lectures at the workshop: C. Leiserson, N. Magnenat-Thalmann, M. Snir, U. Vazarani, and 1. Vitter. On behalf of the program committee, we would like to express our appreciation to the six plenary lecturers who accepted our invitation to speak, to all the authors who submitted papers to W ADS''99, and to the Pacific Institute for Mathematical Sciences for their sponsorship. Finally, we would like to express our gratitude to all the people who reviewed papers at the request of the program committee. August 1999 F. Dehne A. Gupta J.-R. Sack R. Tamassia VI Conference Chair: A. Gupta Program Committee Chairs: F. Dehne, A. Gupta, J.-R. Sack, R. Tamassia Program Committee: A. Andersson, A. Apostolico, G. Ausiello, G. Bilardi, K. Clarkson, R. Cleve, M. Cosnard, L. Devroye, P. Dymond, M. Farach-Colton, P. Fraigniaud, M. Goodrich, A.

This book contains the papers presented at the 1989 Workshop on Algorithms and Data Structures, which succeeds the 1988 Scandinavian Workshop on Algorithm Theory. It presents current research in various areas of algorithms, computational geometry, geometric searching, VLSI placement and routing, graph algorithms, parallel algorithms, distributed algorithms, databases, and text searching.

This volume contains papers presented at the Third International Conference on Computing and Information, ICCI '91, held at Carleton University in Ottawa, Canada, May 27-29, 1991. The conference was organized by the School of Computer Science at Carleton University, and was sponsored by the Natural Sciences and Engineering Research Council of Canada (NSERC) and Carleton University. ICCI '91 was an international forum for the presentation of original results in research, development, and applications in computing and information processing. The conference was aimed at both practitioners and theoreticians, and was organized into five streams: - Algorithms and complexity, - Databases and information systems, - Parallel processing and systems, - Distributed computing and systems, - Expert systems, artificial intelligence. This volume contains three invited papers, by E.C.R. Hehner, R.L. Probert, and S.J. Smith, and 71 selected papers.

This volume presents the proceedings of the Second Workshop on Algorithms and Data Structures (WADS '91), held at Carleton University in Ottawa. The workshop was organized by the School of Computer Science at Carleton University. The workshop alternates with the Scandinavian Workshop on Algorithm Theory (SWAT), continuing the tradition of SWAT '88 (LNCS, Vol. 318), WADS '89 (LNCS, Vol. 382), and SWAT '90 (LNCS, Vol. 447). From 107 papers submitted, 37 were selected for presentation at the workshop. In addition, there were 5 invited presentations.

The papers in this volume were presented at the ThirdWorkshop on Algorithmsand Data Structures (WADS '93), heldin Montreal, Canada, August 1993.The volume opens with five invited presentations: "Computingthe all-pairs longest chains in the plane" by M.J. Atallahand D.Z. Chen, "Towards a better understanding of purepacket routing" by A. Borodin, "Tolerating faults in meshesand other networks" (abstract) by R. Cole, "A generalizationof binary search" by R.M. Karp, and "Groups and algebraiccomplexity" (abstract) by A.C. Yao. The volume continueswith 52 regular presentations selected from 165 submissions,each of which was evaluated by at least three programcommittee members, many of whom called upon additionalreviewers.

This volume constitutes the proceedings of the Fourth International Workshop on Algorithms and Data Structures, WADS '95, held in Kingston, Canada in August 1995.The book presents 40 full refereed papers selected from a total of 121 submissions together with invited papers by Preparata and Bilardi, Sharir, Toussaint, and Vitanyi and Li. The book addresses various aspects of algorithms, data structures, computational geometry, scheduling, computational graph theory, and searching.

This book constitutes the refereed proceedings of the 5th International Workshop on Algorithms and Data Structures, WADS'97, held in Nova Scotia, Halifax, Canada, in August 1997.The 37 revised full papers presented were carefully selected from a total of 81 submissions. Also included are four abstracts and one full contribution corresponding to the invited talks. Among the topics covered are data structures and algorithmic aspects in a variety of areas like computational geometry, graph theory, networking, load balancing, optimization, approximation, sorting, pattern matching, etc.

The papers in this volume were presented at the Sixth Workshop on Algorithms and Data Structures (WADS '99). The workshop took place August 11 - 14, 1999, in Vancouver, Canada. The workshop alternates with the Scandinavian Workshop on Algorithms Theory (SWAT), continuing the tradition of SWAT and WADS starting with SWAT'88 and WADS'89. In response to the program committee's call for papers, 71 papers were submitted. From these submissions, the program committee selected 32 papers for presentation at the workshop. In addition to these submitted papers, the program committee invited the following researchers to give plenary lectures at the workshop: C. Leiserson, N. Magnenat-Thalmann, M. Snir, U. Vazarani, and 1. Vitter. On behalf of the program committee, we would like to express our appreciation to the six plenary lecturers who accepted our invitation to speak, to all the authors who submitted papers to W ADS'99, and to the Pacific Institute for Mathematical Sciences for their sponsorship. Finally, we would like to express our gratitude to all the people who reviewed papers at the request of the program committee. August 1999 F. Dehne A. Gupta J.-R. Sack R. Tamassia VI Conference Chair: A. Gupta Program Committee Chairs: F. Dehne, A. Gupta, J.-R. Sack, R. Tamassia Program Committee: A. Andersson, A. Apostolico, G. Ausiello, G. Bilardi, K. Clarkson, R. Cleve, M. Cosnard, L. Devroye, P. Dymond, M. Farach-Colton, P. Fraigniaud, M. Goodrich, A.

The papers in this volume were presented at the 10th Workshop on Algorithms and Data Structures (WADS 2005). The workshop took place August 15 - 17, 2007, at Dalhousie University, Halifax, Canada. The workshop alternates with the Scandinavian Workshop on Algorithm Theory (SWAT), continuing the t- dition of SWAT and WADS starting with SWAT 1988 and WADS 1989. From 142 submissions, the Program Committee selected 54 papers for presentation at the workshop. In addition, invited lectures were given by the following dist- guished researchers: Je? Erickson (University of Illinois at Urbana-Champaign) and Mike Langston (University of Tennessee). On behalf of the Program Committee, we would like to express our sincere appreciation to the many persons whose e?ort contributed to making WADS 2007 a success. These include the invited speakers, members of the Steering and ProgramCommittees, the authorswho submitted papers, andthe manyreferees who assisted the Program Committee. We are indebted to Gerardo Reynaga for installing and modifying the submission software, maintaining the submission server and interacting with authors as well as for helping with the preparation of the program.

The papers in this volume were presented at the 10th Workshop on Algorithms and Data Structures (WADS 2005). The workshop took place August 15 - 17, 2007, at Dalhousie University, Halifax, Canada. The workshop alternates with the Scandinavian Workshop on Algorithm Theory (SWAT), continuing the t- dition of SWAT and WADS starting with SWAT 1988 and WADS 1989. From 142 submissions, the Program Committee selected 54 papers for presentation at the workshop. In addition, invited lectures were given by the following dist- guished researchers: Je? Erickson (University of Illinois at Urbana-Champaign) and Mike Langston (University of Tennessee). On behalf of the Program Committee, we would like to express our sincere appreciation to the many persons whose e?ort contributed to making WADS 2007 a success. These include the invited speakers, members of the Steering and ProgramCommittees, the authorswho submitted papers, andthe manyreferees who assisted the Program Committee. We are indebted to Gerardo Reynaga for installing and modifying the submission software, maintaining the submission server and interacting with authors as well as for helping with the preparation of the program.

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 12th Algorithms and Data Structures Symposium, WADS 2011, held in New York, NY, USA, in August 2011. 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 59 revised full papers presented in this volume were carefully reviewed and selected from 141 submissions. The papers present original research on the theory and application of algorithms and data structures in all areas, including combinatorics, computational geometry, databases, graphics, parallel and distributed computing.

This book constitutes the refereed proceedings of the 12th Algorithms and Data Structures Symposium, WADS 2011, held in New York, NY, USA, in August 2011. 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 59 revised full papers presented in this volume were carefully reviewed and selected from 141 submissions. The papers present original research on the theory and application of algorithms and data structures in all areas, including combinatorics, computational geometry, databases, graphics, parallel and distributed computing.

This book constitutes the refereed proceedings of the 13th Algorithms and Data Structures Symposium, WADS 2013, held in London, ON, Canada, August 2013. 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 44 revised full papers presented in this volume were carefully reviewed and selected from 139 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.

This book constitutes the refereed proceedings of the 14th Algorithms and Data Structures Symposium, WADS 2015, held in Victoria, BC, Canada, August 2015. The 54 revised full papers presented in this volume were carefully reviewed and selected from 148 submissions. The Algorithms and Data Structures Symposium - WADS (formerly Workshop on Algorithms And Data Structures), which alternates with the Scandinavian Workshop on Algorithm Theory, is intended as a forum for researchers in the area of design and analysis of algorithms and data structures. WADS includes papers presenting original research on algorithms and data structures in all areas, including bioinformatics, combinatorics, computational geometry, databases, graphics, and parallel and distributed computing.

This book constitutes the refereed proceedings of the 14th Algorithms and Data Structures Symposium, WADS 2015, held in Victoria, BC, Canada, August 2015. The 54 revised full papers presented in this volume were carefully reviewed and selected from 148 submissions. The Algorithms and Data Structures Symposium - WADS (formerly Workshop on Algorithms And Data Structures), which alternates with the Scandinavian Workshop on Algorithm Theory, is intended as a forum for researchers in the area of design and analysis of algorithms and data structures. WADS includes papers presenting original research on algorithms and data structures in all areas, including bioinformatics, combinatorics, computational geometry, databases, graphics, and parallel and distributed computing.

Thecentralchallengeoftheoreticalcomputerscienceistodeploymathematicsin waysthatservethecreationofusefulalgorithms. Inrecentyearstherehasbeena growinginterest in the two-dimensionalframework of parameterizedcomplexity, where, in addition to the overall input size, one also considers a parameter,with a focus on how these two dimensions interact in problem complexity. This book presents the proceedings of the 1st InternationalWorkshopon - rameterized and Exact Computation (IWPEC 2004,http://www. iwpec. org), which took place in Bergen, Norway, on September 14-16, 2004. The workshop was organized as part of ALGO 2004. There were seven previous workshops on the theory and applications of parameterized complexity. The ?rst was - ganized at the Institute for the Mathematical Sciences in Chennai, India, in September, 2000. The second was held at Dagstuhl Castle, Germany, in July, 2001. In December, 2002, a workshop on parameterized complexity was held in conjunction with the FST-TCS meeting in Kanpur, India. A second Dagstuhl workshop on parameterized complexity was held in July, 2003.Another wo- shoponthesubjectwasheldinOttawa,Canada,inAugust,2003,inconjunction with the WADS 2003 meeting. There have also been two Barbados workshops on applications of parameterized complexity. In response to the IWPEC 2004 call for papers, 47 papers were submitted, and from these the programcommittee selected 25 for presentation at the wo- shop. Inaddition,invitedlectureswereacceptedbythedistinguishedresearchers Michael Langston and Gerhard Woeginger.

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.

The refereed proceedings of the 8th International Workshop on Algorithms and Data Structures, WADS 2003, held in Ottawa, Ontario, Canada, in July/August 2003. The 40 revised full papers presented together with 4 invited papers were carefully reviewed and selected from 126 submissions. A broad variety of current aspects in algorithmics and data structures is addressed.

The papers in this volume were presented at the Seventh Workshop on Al- rithms and Data Structures (WADS 2001). The workshop took place August 8-10, 2001 in Providence, Rhode Island, USA. The workshop alternates with the Scandinavian Workshop on Algorithms Theory (SWAT), continuing the t- dition of SWAT and WADS starting with SWAT '88 and WADS '89. In response to the call for papers, 89 papers were submitted. From these submissions, the program committee selected 40 papers for presentation at the workshop. In addition invited plenary lectures were given by the following - stinguished researchers: Mikhail J. Atallah, F. Thomson Leighton, and Mihalis Yannakakis. On behalf of the program committee, we would like to express our apprec- tion to the invited speakers and to all the authors who submitted papers. August 2001 Frank Dehne J.. org-Rudiger .. Sack Roberto Tamassia Organization Conference Chair Roberto Tamassia (Brown) Program Committee Chairs Frank Dehne (Carleton) J.. org-Rudiger .. Sack (Carleton) Roberto Tamassia (Brown) Program Committee Alberto Apostolico (Purdue, Padova) Giuseppe Liotta (Perugia) Timothy Chan (Waterloo) Ernst W. Mayr (Munc .. hen) Bruno Codenotti (IMC) Joseph S.B. Mitchell (SUNY) Giuseppe Di Battista (Roma Tre) Stefan N.. aher (Trier) Shlomi Dolev (Ben-Gurion) Takao Nishizeki (Tohoku) Martin Farach-Colton Viktor K. Prasanna (USC) (Rutgers, Google) Enrico Puppo (Genova) Pierre Fraigniaud (LRI) Jose Rolim (Geneva) Harold N. Gabow (Colorado) Jack Snoeyink (UNC) Sally A. Goldman (Washington) Ioannis G. Tollis (UTD) Michael T.

The papers in this volume were presented at the Sixth Workshop on Algorithms and Data Structures (WADS ''99). The workshop took place August 11 - 14, 1999, in Vancouver, Canada. The workshop alternates with the Scandinavian Workshop on Algorithms Theory (SWAT), continuing the tradition of SWAT and WADS starting with SWAT''88 and WADS''89. In response to the program committee''s call for papers, 71 papers were submitted. From these submissions, the program committee selected 32 papers for presentation at the workshop. In addition to these submitted papers, the program committee invited the following researchers to give plenary lectures at the workshop: C. Leiserson, N. Magnenat-Thalmann, M. Snir, U. Vazarani, and 1. Vitter. On behalf of the program committee, we would like to express our appreciation to the six plenary lecturers who accepted our invitation to speak, to all the authors who submitted papers to W ADS''99, and to the Pacific Institute for Mathematical Sciences for their sponsorship. Finally, we would like to express our gratitude to all the people who reviewed papers at the request of the program committee. August 1999 F. Dehne A. Gupta J.-R. Sack R. Tamassia VI Conference Chair: A. Gupta Program Committee Chairs: F. Dehne, A. Gupta, J.-R. Sack, R. Tamassia Program Committee: A. Andersson, A. Apostolico, G. Ausiello, G. Bilardi, K. Clarkson, R. Cleve, M. Cosnard, L. Devroye, P. Dymond, M. Farach-Colton, P. Fraigniaud, M. Goodrich, A.

This book contains the papers presented at the 1989 Workshop on Algorithms and Data Structures, which succeeds the 1988 Scandinavian Workshop on Algorithm Theory. It presents current research in various areas of algorithms, computational geometry, geometric searching, VLSI placement and routing, graph algorithms, parallel algorithms, distributed algorithms, databases, and text searching.

This volume contains papers presented at the Third International Conference on Computing and Information, ICCI '91, held at Carleton University in Ottawa, Canada, May 27-29, 1991. The conference was organized by the School of Computer Science at Carleton University, and was sponsored by the Natural Sciences and Engineering Research Council of Canada (NSERC) and Carleton University. ICCI '91 was an international forum for the presentation of original results in research, development, and applications in computing and information processing. The conference was aimed at both practitioners and theoreticians, and was organized into five streams: - Algorithms and complexity, - Databases and information systems, - Parallel processing and systems, - Distributed computing and systems, - Expert systems, artificial intelligence. This volume contains three invited papers, by E.C.R. Hehner, R.L. Probert, and S.J. Smith, and 71 selected papers.

This volume presents the proceedings of the Second Workshop on Algorithms and Data Structures (WADS '91), held at Carleton University in Ottawa. The workshop was organized by the School of Computer Science at Carleton University. The workshop alternates with the Scandinavian Workshop on Algorithm Theory (SWAT), continuing the tradition of SWAT '88 (LNCS, Vol. 318), WADS '89 (LNCS, Vol. 382), and SWAT '90 (LNCS, Vol. 447). From 107 papers submitted, 37 were selected for presentation at the workshop. In addition, there were 5 invited presentations.

The papers in this volume were presented at the ThirdWorkshop on Algorithmsand Data Structures (WADS '93), heldin Montreal, Canada, August 1993.The volume opens with five invited presentations: "Computingthe all-pairs longest chains in the plane" by M.J. Atallahand D.Z. Chen, "Towards a better understanding of purepacket routing" by A. Borodin, "Tolerating faults in meshesand other networks" (abstract) by R. Cole, "A generalizationof binary search" by R.M. Karp, and "Groups and algebraiccomplexity" (abstract) by A.C. Yao. The volume continueswith 52 regular presentations selected from 165 submissions,each of which was evaluated by at least three programcommittee members, many of whom called upon additionalreviewers.

This volume constitutes the proceedings of the Fourth International Workshop on Algorithms and Data Structures, WADS '95, held in Kingston, Canada in August 1995.The book presents 40 full refereed papers selected from a total of 121 submissions together with invited papers by Preparata and Bilardi, Sharir, Toussaint, and Vitanyi and Li. The book addresses various aspects of algorithms, data structures, computational geometry, scheduling, computational graph theory, and searching.

This book constitutes the refereed proceedings of the 5th International Workshop on Algorithms and Data Structures, WADS'97, held in Nova Scotia, Halifax, Canada, in August 1997.The 37 revised full papers presented were carefully selected from a total of 81 submissions. Also included are four abstracts and one full contribution corresponding to the invited talks. Among the topics covered are data structures and algorithmic aspects in a variety of areas like computational geometry, graph theory, networking, load balancing, optimization, approximation, sorting, pattern matching, etc.

The papers in this volume were presented at the Sixth Workshop on Algorithms and Data Structures (WADS '99). The workshop took place August 11 - 14, 1999, in Vancouver, Canada. The workshop alternates with the Scandinavian Workshop on Algorithms Theory (SWAT), continuing the tradition of SWAT and WADS starting with SWAT'88 and WADS'89. In response to the program committee's call for papers, 71 papers were submitted. From these submissions, the program committee selected 32 papers for presentation at the workshop. In addition to these submitted papers, the program committee invited the following researchers to give plenary lectures at the workshop: C. Leiserson, N. Magnenat-Thalmann, M. Snir, U. Vazarani, and 1. Vitter. On behalf of the program committee, we would like to express our appreciation to the six plenary lecturers who accepted our invitation to speak, to all the authors who submitted papers to W ADS'99, and to the Pacific Institute for Mathematical Sciences for their sponsorship. Finally, we would like to express our gratitude to all the people who reviewed papers at the request of the program committee. August 1999 F. Dehne A. Gupta J.-R. Sack R. Tamassia VI Conference Chair: A. Gupta Program Committee Chairs: F. Dehne, A. Gupta, J.-R. Sack, R. Tamassia Program Committee: A. Andersson, A. Apostolico, G. Ausiello, G. Bilardi, K. Clarkson, R. Cleve, M. Cosnard, L. Devroye, P. Dymond, M. Farach-Colton, P. Fraigniaud, M. Goodrich, A.

The papers in this volume were presented at the 10th Workshop on Algorithms and Data Structures (WADS 2005). The workshop took place August 15 - 17, 2007, at Dalhousie University, Halifax, Canada. The workshop alternates with the Scandinavian Workshop on Algorithm Theory (SWAT), continuing the t- dition of SWAT and WADS starting with SWAT 1988 and WADS 1989. From 142 submissions, the Program Committee selected 54 papers for presentation at the workshop. In addition, invited lectures were given by the following dist- guished researchers: Je? Erickson (University of Illinois at Urbana-Champaign) and Mike Langston (University of Tennessee). On behalf of the Program Committee, we would like to express our sincere appreciation to the many persons whose e?ort contributed to making WADS 2007 a success. These include the invited speakers, members of the Steering and ProgramCommittees, the authorswho submitted papers, andthe manyreferees who assisted the Program Committee. We are indebted to Gerardo Reynaga for installing and modifying the submission software, maintaining the submission server and interacting with authors as well as for helping with the preparation of the program.

The papers in this volume were presented at the 10th Workshop on Algorithms and Data Structures (WADS 2005). The workshop took place August 15 - 17, 2007, at Dalhousie University, Halifax, Canada. The workshop alternates with the Scandinavian Workshop on Algorithm Theory (SWAT), continuing the t- dition of SWAT and WADS starting with SWAT 1988 and WADS 1989. From 142 submissions, the Program Committee selected 54 papers for presentation at the workshop. In addition, invited lectures were given by the following dist- guished researchers: Je? Erickson (University of Illinois at Urbana-Champaign) and Mike Langston (University of Tennessee). On behalf of the Program Committee, we would like to express our sincere appreciation to the many persons whose e?ort contributed to making WADS 2007 a success. These include the invited speakers, members of the Steering and ProgramCommittees, the authorswho submitted papers, andthe manyreferees who assisted the Program Committee. We are indebted to Gerardo Reynaga for installing and modifying the submission software, maintaining the submission server and interacting with authors as well as for helping with the preparation of the program.

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 12th Algorithms and Data Structures Symposium, WADS 2011, held in New York, NY, USA, in August 2011. 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 59 revised full papers presented in this volume were carefully reviewed and selected from 141 submissions. The papers present original research on the theory and application of algorithms and data structures in all areas, including combinatorics, computational geometry, databases, graphics, parallel and distributed computing.

This book constitutes the refereed proceedings of the 12th Algorithms and Data Structures Symposium, WADS 2011, held in New York, NY, USA, in August 2011. 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 59 revised full papers presented in this volume were carefully reviewed and selected from 141 submissions. The papers present original research on the theory and application of algorithms and data structures in all areas, including combinatorics, computational geometry, databases, graphics, parallel and distributed computing.

This book constitutes the refereed proceedings of the 13th Algorithms and Data Structures Symposium, WADS 2013, held in London, ON, Canada, August 2013. 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 44 revised full papers presented in this volume were carefully reviewed and selected from 139 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.