15. WG 1989: Castle Rolduc, The Netherlands

Manfred Nagl (Ed.): Graph-Theoretic Concepts in Computer Science, 15th International Workshop, WG '89, Castle Rolduc, The Netherlands, June 14-16, 1989, Proceedings. Lecture Notes in Computer Science 411 Springer 1990, ISBN 3-540-52292-1 BibTeX

Distribution and Graphs

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

Application Modeling with Graphs

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

Graph Grammars: Theory and Application

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

Graph Embeddings

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

Algorithmis Graph Theory

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

Graphs and Data Structures

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

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 BibTeX
Knuth Menzel, Burkhard Monien: WEighted Parallel Triangulation of Simple Polygons. 302-315 BibTeX
Frank K. H. A. Dehne, Andrew Rau-Chaplin: Implementing Data Structures on a Hypercube Multiprocessor, and Applications in Parallel Computational Geometry. 316-329 BibTeX
Thomas Roos: k-Nearest-Neighbor Voronoi Diagrams for Sets of Convex Polygons, Line Segments and Points. 330-340 BibTeX
Marc J. van Kreveld, Mark de Berg: Finding Squares and Rectangles in Sets of Points. 341-355 BibTeX
Rolf Klein: Combinatorial Properties of Abstract Voronoi Diagrams. 356-369 BibTeX