This book constitutes the refereed proceedings of the 10th International Workshop on Algorithms and Data Structures, WADS 2007, held in Halifax, Canada, in August 2005. The 54 revised full papers presented together with 2 invited papers were carefully reviewed and selected from 142 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. 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. Session 1 Finding Small Holes: A Brief Foray into Computational Topology 1 Jeff Erickson Session 2A Approximate Range Searching: The Absolute Model 2 Guilherme D. da Fonseca Orthogonal Range Searching in Linear and Almost-Linear Space 15 Yakov Nekrich Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere 27 Kengo Terasawa and Yuzuru Tanaka Session 2B A 4/3-Approximation Algorithm for Minimum 3-Edge-Connectivity 39 Prabhakar Gubbala and Balaji Raghavachari Approximating the Maximum Sharing Problem 52 Amitabh Chaudhary, Danny Z. Chen, Rudolf Fleischer, Xiaobo S. Hu, Jian Li, Michael T. Niemier, Zhiyi Xie, and Hong Zhu The Stackelberg Minimum Spanning Tree Game 64 Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwena Joret, Stefan Langerman, Ilan Newman, and Oren Weimann Session 3A Edges and Switches, Tunnels and Bridges 77 David Eppstein, Marc van Kreveld, Elena Mumford, and Bettina Speckmann How to Draw a Clustered Tree 89 Giuseppe Di Battista, Guido Drovandi, and Fabrizio Frati Drawing Colored Graphs on Colored Points 102 Melanie Badent, Emilio Di Giacomo, and Giuseppe Liotta Session 3B Discrepancy-Sensitive Dynamic Fractional Cascading, Dominated Maxima Searching, and 2-d Nearest Neighbors in Any Minkowski Metric 114 Mikhail J. Atallah, Marina Blanton, Michael T. Goodrich, and Stanislas Polu Priority Queues Resilient to Memory Faults 127 Illaa Gr nlund J rgensen, Gabriel Moruz, arid Thomas M lhave Simple and Space-Efficient Minimal Perfect Hash Functions 139 Fabiano C. Botelho, Rasmus Pagh, and Nivio Ziviani Session 4A A Linear Time Approximation Scheme for Steiner Tree Among Obstacles in the Plane 151 Matthias M ller-Hannemann and Siamak Tazari A Pseudopolynomial Time O(log n)-Approximation Algorithm for Art Problems 163 Ajay Deshpande, Taejung Kim, Erik D. Demaine, and Sanjay E. Sarma Optimization for First Order Delaunay Triangulations 175 Mark van Kreveld, Maarten L ffler, and Rodrigo I. Silveira Session 4B Constant Factor Approximations for the Hotlink Assignment 188 Tobias Jacobs Approximation Algorithms for the Sex-Equal Stable Marriage 201 Kazuo Iwama, Shuichi Miyazaki, and Hiroki Yanagisawa A Stab at Approximating Minimum Subadditive Join 214 Staal A. Vinterbo Session 5 Algorithmic Challenges for Systems-Level Correlational Analysis: A Tale of Two Datasets 226 Michael A. Langston Session 6A Flooding Countries and Destroying Dams 227 Rodrigo I. Silveira and Ren an Oostrum I/O-Efficient Flow Modeling on Fat Terrains 239 Mark de Berg, Otfried Cheong, Herman Haverkort, Jung Gun Lim, and Laura Toma Computing the Visibility Map of Fat Objects 251 Mark de Berg and Chris Gray Session 6B Independent Sets in Bounded-Degree Hypergraphs 263 Alagnlis M. Halld rsson and Elena Losievskaja Steiner Tree in Planar Graphs: An O(n log n) Approximation Scheme with Singly-Exponential Dependence on Epsilon 275 Glencora Borradaile, Philip N. Klein, and Claire Mathieu Computing a Minimum-Depth Planar Graph Embedding in O(n4) Time 287 Patrizio Angelini, Giuseppe Di Battista, and Maurizio Patrignani Session 7A On a Family of Strong Geometric Spanners That Admit Local Routing Strategies 300 Prosenjit Bose, Paz Carmi, Mathieu Couture, Michiel Smid, and Daming Xu Spanners for Geometric Intersection Graphs 312 Martin F rer and Shiva Prasad Kasiviswanathan On Generalized Diamond Spanners 325 Prosenjit Bose, Aaron Lee, and Michiel Smid Session 7B The k-Resource Problem on Uniform and on Uniformly Decomposable Metric Spaces 337 Marcin Bienkowski and Jaroslaw Kutylowski On the Robustness of Graham's Algorithm for Online Scheduling 349 Michael Gatto and Peter Widmayer Improved Results for a Memory Allocation Problem 362 Leah Epstein and Rob van Stee Session 8A Computational and Structural Advantages of Circular Boundary Representation 374 Oswin Aichholzer, Franz Aurenhammer, Thomas Hackl, Bert J ttler, Margot Oberneder, and Zbynek ir Alpha-Beta Witness Complexes 386 Dominique Attali, Herbert Edelsbrunner, John Harer, and Yuriy Mileyko Cauchy's Theorem and Edge Lengths of Convex Polyhedra 398 Therese Biedl, Anna Lubiw, and Michael Spriggs Session 8B Fixed-Parameter Tractability for Non-Crossing Spanning Trees 410 Magn s M. Halld rsson, Christian Knauer, Andreas Spillner, and Takeshi Tokuyama Improved Algorithms for the Feedback Vertex Set Problems 422 Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, and Yngve Villanger Kernelization Algorithms for d-Hitting Set Problems 434 Faisal N. Abu-Khzam Session 9A Largest Bounding Box, Smallest Diameter, arid Related Problems on Imprecise Points 446 Maarten L ffler and Marc van Kreveld Maximizing Maximal Angles for Plane Straight-Line Graphs 458 Oswin Aichholzer, Thomas Hackl, Michael Hoffmann, Clemens Huemer, Attila P r, Francisco Santos, Bettina Speckmann, and Birgit Vogtenhuber Cuttings for Disks and Axis-Aligned Rectangles 470 Eynat Rafalin, Diane L. Souvaine, and Csaba D. T th Session 9B Kernelization and Complexity Results for Connectivity Augmentation Problems 483 Jiong Guo and Johannes Uhlmann An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem 495 Jianer Chen, Yang Liu, and Songjian Lu Branch and Recharge: Exact Algorithms for Generalized Domination 507 Mylor V. Fomin, Petr A. Golovach, Jan Kratochvil, Dieter Kratsch, and Mathieu Liedloff Session 10A On Computing the Centroid of the Vertices of an Arrangement and Related Problems 519 Deepak Ajwani, Saurabh Ray, Raimund Seidel, and Hans Raj Tiwary Optimal Algorithms for the Weighted p-Center Problems on the Real Line for Small p 529 Binay Bhattacharya and Qiaosheng Shi Session 10B Faster Approximation of Distances in Graphs 541 Piotr Berman and Shiva Prasad Kasiviswanathan Approximate Shortest Paths Guided by a Small Index 553 J rg Derungs, Riko Jacob, and Peter Widmayer Session 11A Initializing Sensor Networks of Non-uniform Density in the Weak Sensor Model 565 Martin Farach-Colton and Miguel A. Mosteiro Computing Best Coverage Path in the Presence of Obstacles in a Sensor Field 577 Senjuti Basu Roy, Gautam Das, and Sajal Das 35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality 589 Lukasz Kowalik and Marcin Mucha On Euclidean Vehicle Routing with Allocation 601 Jan Remy, Reto Sp hel, and Andreas Wei Session 11B Optimal Lightweight Construction of Suffix Arrays for Constant Alphabets 613 Ge Nong and Sen Zhang Range Non-overlapping Indexing and Successive List Indexing 625 Orgad Keller, Tsvi Kopelowitz, and Moshe Lewenstein Space-Efficient Straggler Identification in Round-Trip Data Streams Via Newton's Identities and Invertible Bloom Filters 637 David Eppstein and Michael T. Goodrich Dynamic TCP Acknowledgment with Sliding Window 649 Hisashi Koga Author Index 661