15. WG 1989: Castle Rolduc, The Netherlands

Distribution and Graphs

• Seshu Madhavapeddy, Ivan Hal Sudborough:
  Disjoint Paths in the Hypercube. 3-18
  
• Renato M. Capocelli, Luisa Gargano, Ugo Vaccaro:
  Time Bound for Broadcasting in Bounded Degree Graphs. 19-33
  
• Anindya Das, Krishnaiyan Thulasiraman, Vinod K. Agarwal, K. B. Lakshmanan:
  t/s-Diagnosable Systems: A Characterization and Diagnosis Algorithm. 34-45
  

Application Modeling with Graphs

• Robert Y. Geva, Azaria Paz:
  Toward a Complete Representation of Graphoids in Graphs (Abridged Version). 46-62
  
• Detlev Ruland:
  CADULA - A Graph-Based Model for Monitoring CAD-Processes. 63-72
  

Graph Grammars: Theory and Application

• Walter Vogler:
  On Hyperedge Replacement and BNLC Graph Grammars. 78-93
  
• Michel Billaud, Pierre Lafon, Yves Métivier, Eric Sopena:
  Graph Rewriting Systems with Priorities. 94-106
  
• Annegret Habel, Hans-Jörg Kreowski:
  Filtering Hyperedge-Replacement Through Compatible Properties. 107-120
  
• Hans Jürgen Schneider:
  Describing Distributed Systems by Categorical Graph Grammars. 121-135
  
• Horst Bunke, B. Haller:
  A Parser for Context Free Plex Grammars. 136-150
  
• Andy Schürr:
  Introduction to PROGRESS, an Attribute Graph Grammar Based Specification Language. 151-165
  

Graph Embeddings

• Franz-Josef Brandenburg:
  On the Complexity of Optimal Drawings of Graphs. 166-180
  
• Maciej M. Syslo:
  Bounds to the Page Number of Partially Ordered Sets. 181-195
  
• Gabriele Reich, Peter Widmayer:
  Beyond Steiner's Problem: A VLSI Oriented Generalization. 196-210
  

Algorithmis Graph Theory

• Ingo Schiermeyer:
  A Fast Sequential and Parallel Algorithm for the Computation of the k-Closure of a Graph. 211-217
  
• Ewald Speckenmeyer:
  On Feedback Problems in Diagraphs. 218-231
  
• Hans L. Bodlaender:
  Improved Self-Reduction Algorithms for Graphs with Bounded Treewidth. 232-244
  
• Klaus Simon:
  Finding a Minimal Transitive Reduction in a Strongly Connected Digraph within Linear Time. 245-259
  

Graphs and Data Structures

• Andreas Henrich, Hans-Werner Six, Peter Widmayer:
  Paging Binary Trees with External Balancing. 260-276
  
• Antoni Lozano, José L. Balcázar:
  The Complexity of Graph Problems fore Succinctly Represented Graphs. 277-286
  

Graphs and Computational Geometry

• Richard Anderson, Simon Kahan, Martine D. F. Schlag:
  An O(n log n) Algorithm for 1-D Tile Compaction. 287-301
  
• Knuth Menzel, Burkhard Monien:
  WEighted Parallel Triangulation of Simple Polygons. 302-315
  
• Frank K. H. A. Dehne, Andrew Rau-Chaplin:
  Implementing Data Structures on a Hypercube Multiprocessor, and Applications in Parallel Computational Geometry. 316-329
  
• Thomas Roos:
  k-Nearest-Neighbor Voronoi Diagrams for Sets of Convex Polygons, Line Segments and Points. 330-340
  
• Marc J. van Kreveld, Mark de Berg:
  Finding Squares and Rectangles in Sets of Points. 341-355
  
• Rolf Klein:
  Combinatorial Properties of Abstract Voronoi Diagrams. 356-369