Volume 16, Number 1, July 1996

Special Issue on Graph Drawing

• 
  Giuseppe Di Battista, Roberto Tamassia: Guest Editors' Introduction to the Special Issue on Graph Drwaing. 1-3
• 
  Goos Kant: Drawing Planar Graphs Using the Canonical Ordering. 4-32
• 
  Michael Jünger, Petra Mutzel: Maximum Planar Subgraphs and Nice Embeddings: Practical Layout Tools. 33-59
• 
  Peter Eades, Sue Whitesides: The Realization Problem for Euclidean Minimum Spanning Trees in NP-Hard. 60-82
• 
  Prosenjit Bose, William Lenhart, Giuseppe Liotta: Characterizing Proximity Trees. 83-110
• 
  János Pach, Farhad Shahrokhi, Mario Szegedy: Applications of the Crossing Number. 111-117
• 
  Farhad Shahrokhi, László A. Székely, Ondrej Sýkora, Imrich Vrto: Drawings of Graphs on Surfaces with Few Crossings. 118-131

Volume 16, Number 2, August 1996

• 
  Xiaotie Deng, Christos H. Papadimitriou: Competitive Distributed Decision-Making. 133-150
• 
  J. Ian Munro, Venkatesh Raman: Fast Stable In-Place Sorting with O (n) Data Moves. 151-160
• 
  Shou-Hsuan Stephen Huang, Hongfei Liu, Rakesh M. Verma: A New Combinatorial Approach to Optimal Embeddings of Rectangles. 161-180
• 
  Mark H. Nodine, Michael T. Goodrich, Jeffrey Scott Vitter: Blocking for External Graph Searching. 181-214
• 
  David M. Choy, Ronald Fagin, Larry J. Stockmeyer: Efficiently Extendible Mappings for Balanced Data Distribution. 215-232
• 
  Kurt Mehlhorn, Petra Mutzel: On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm. 233-242

Volume 16, Number 3, September 1996

• 
  Sivaprakasam Sunder, Xin He: An NC Algorithm for Finding a Minimum Weighted Completion Time Schedule on Series Parallel Graphs. 243-262
• 
  Dora Giammarresi, Giuseppe F. Italiano: Decremental 2- and 3-Connectivity on Planar Graphs. 263-287
• 
  Costas S. Iliopoulos, D. W. G. Moore, Kunsoo Park: Covering a String. 288-297
• 
  Andris Ambainis: Communication Complexity in a 3-Computer Model. 298-301
• 
  Lusheng Wang, Tao Jiang, Eugene L. Lawler: Approximation Algorithms for Tree Alignment with a Given Phylogeny. 302-315
• 
  Masato Edahiro: Equispreading Tree in Manhattan Distance. 316-338
• 
  Jun-ya Takahashi, Hitoshi Suzuki, Takao Nishizeki: Shortest Noncrossing Paths in Plane Graphs. 339-357

Volume 16, Number 4/5, October/November 1996

Special Issue Randomized and Derandomized Algorithms

• 
  Michael Luby: Introduction to Special Issue on Randomized and Derandomized Algorithms. 359-366
• 
  David Zuckerman: Simulating BPP Using a General Weak Random Source. 367-391
• 
  Mark Jerrum, Umesh V. Vazirani: A Mildly Exponential Approximation Algorithm for the Permanent. 392-401
• 
  Milena Mihail, Peter Winkler: On the Number of Eulerian Orientations of a Graph. 402-414
• 
  Michael Luby, Boban Velickovic: On Deterministic Approximation of DNF. 415-433
• 
  Noga Alon, Moni Naor: Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions. 434-449
• 
  Ketan Mulmuley: Randomized Geometric Algorithms and Pseudorandom Generators. 450-463
• 
  Raimund Seidel, Cecilia R. Aragon: Randomized Search Trees. 464-497
• 
  Jirí Matousek, Micha Sharir, Emo Welzl: A Subexponential Bound for Linear Programming. 498-516
• 
  Richard M. Karp, Michael Luby, Friedhelm Meyer auf der Heide: Efficient PRAM Simulation on a Distributed Memory Machine. 517-542
• 
  Helmut Alt, Leonidas J. Guibas, Kurt Mehlhorn, Richard M. Karp, Avi Wigderson: A Method for Obtaining Randomized Algorithms with Small Tail Probabilities. 543-547

Volume 16, Number 6, December 1996

• 
  Michele Flammini, Giorgio Gambosi, Sandro Salomone: Interval Routing Schemes. 549-568
• 
  Richard Cole, Michael T. Goodrich, Colm Ó'Dúnlaing: A Nearly Optimal Deterministic Parallel Voroni Diagram Algorithm. 569-617
• 
  David Avis: Generating Rooted Triangulations Without Repetitions. 618-632
• 
  Donald B. Johnson, Panagiotis Takis Metaxas: Optimal Algorithms for the Single and Multiple Vertex Updating Problems of a Minimum Spanning Tree. 633-648
• 
  Mark Allen Weiss: Shellsort with a Constant Number of Increments. 649-654