Graph-Theoretic Concepts in Computer Science: International Workshop WG '87, Kloster Banz/Staffelstein, FRG, June 29 - July 1, 1987. Proceedings (Lecture Notes in Computer Science)

Annotation This book reflects the scientific program of the annual workshop on Graph-theoretic Concepts in Computer Science in 1987. The purpose of this conference is to be the "missing link" between theory and application of graphs in as many branches of computer science as a conference scheduled for three days without parallel sessions can permit. So the organizers of WG '87 addressed a selected group of people with a strong interest in theory and practice. The proceedings include latest results on "classical" graph-theoretic problems (including formal language theory applied to graphs) and how to apply those results to practical problems, e.g. data bases, layout of graph operating systems, software engineering, chemistry, and modelling with graphs Distributed parallelism of graph transformations....Pages 1-19 A PrT-net representation of graph grammars....Pages 20-31 Pretty patterns produced by hyperedge replacement....Pages 32-45 Graph languages defined by systems of forbidden structures: A survey....Pages 46-58 A sweepcircle algorithm for Voronoi diagrams....Pages 59-69 Competitive location in the L 1 and L inf metrics....Pages 70-83 Priority search trees in secondary memory (extended abstract)....Pages 84-93 On the analysis of grid structures for spatial objects of non-zero size....Pages 94-105 Maintenance of transitive closures and transitive reductions of graphs....Pages 106-120 Upward drawings of acyclic digraphs....Pages 121-133 Approximate counting, uniform generation and rapidly mixing markov chains extended abstract....Pages 134-148 On chaotic behaviour of some np-complete problems....Pages 149-161 External labeling and algorithms for hierarchic networks....Pages 162-170 Designing gamma-acyclic database schemes using decomposition and augmentation techniques....Pages 171-185 Graph-theoretical tools and their use in a practical distributed operating system design case....Pages 186-205 Development of several reachability algorithms for directed graphs....Pages 206-218 On integration mechanisms within a graph-based software development environment....Pages 219-229 Restructuring aspect graphs into aspect- and cell-equivalence classes for use in computer vision....Pages 230-241 Automatic crystal chemical classification of silicates using direction-labeled graphs....Pages 242-254