| 1989 | k-Nearest-Neighbor Voronoi Diagrams for Sets of Convex Polygons, Line Segments and Points. | Thomas Roos |
| 1989 | Beyond Steiner's Problem: A VLSI Oriented Generalization. | Gabriele Reich, Peter Widmayer |
| 1989 | WEighted Parallel Triangulation of Simple Polygons. | Knut Menzel, Burkhard Monien |
| 1989 | Disjoint Paths in the Hypercube. | Seshu Madhavapeddy, Ivan Hal Sudborough |
| 1989 | The Complexity of Graph Problems for Succinctly Represented Graphs. | Antoni Lozano, Jos L. Balczar |
| 1989 | Finding Squares and Rectangles in Sets of Points. | Marc J. van Kreveld, Mark de Berg |
| 1989 | Combinatorial Properties of Abstract Voronoi Diagrams. | Rolf Klein |
| 1989 | Paging Binary Trees with External Balancing. | Andreas Henrich, Hans-Werner Six, Peter Widmayer |
| 1989 | Filtering Hyperedge-Replacement Through Compatible Properties. | Annegret Habel, Hans-Jrg Kreowski |
| 1989 | Toward a Complete Representation of Graphoids in Graphs (Abridged Version). | Robert Y. Geva, Azaria Paz |
| 1989 | Implementing Data Structures on a Hypercube Multiprocessor, and Applications in Parallel Computational Geometry. | Frank K. H. A. Dehne, Andrew Rau-Chaplin |
| 1989 | t/s-Diagnosable Systems: A Characterization and Diagnosis Algorithm. | Anindya Das, Krishnaiyan Thulasiraman, Vinod K. Agarwal, K. B. Lakshmanan |
| 1989 | Time Bound for Broadcasting in Bounded Degree Graphs. | Renato M. Capocelli, Luisa Gargano, Ugo Vaccaro |
| 1989 | A Parser for Context Free Plex Grammars. | Horst Bunke, B. Haller |
| 1989 | On the Complexity of Optimal Drawings of Graphs. | Franz-Josef Brandenburg |
| 1989 | Improved Self-Reduction Algorithms for Graphs with Bounded Treewidth. | Hans L. Bodlaender |
| 1989 | Graph Rewriting Systems with Priorities. | Michel Billaud, Pierre Lafon, Yves Mtivier, ric Sopena |
| 1989 | An | Richard Anderson, Simon Kahan, Martine D. F. Schlag |
| 1988 | Epsilon-Nets for Halfplanes. | Gerhard J. Woeginger |
| 1988 | Bandwidth and Profile Minimization. | Manfred Wiegers, Burkhard Monien |
| 1988 | Serializable Graphs. | K. Vidyasankar |
| 1988 | An Efficient Parallel Algorithm for the All Pairs Shortest Path Problem. | Tadao Takaoka |
| 1988 | Colouring Perfect Planar Graphs in Parallel. | Iain A. Stewart |
| 1988 | A Graph-Based Decomposition Approach for Recursive Query Processing. | Dietmar Seipel |
| 1988 | A Simple Systolic Method to Find all Bridges of an Undirected Graph. | Manfred Schimmler, Heiko Schrder |