Graph-Theoretic Concepts in Computer Science

1. Front Matter

   PDF

2. NC-algorithms for graphs with small treewidth

   • Hans L. Bodlaender

   Pages 1-10

3. Graph-theoretic properties compatible with graph derivations

   • Annegret Habel

   Pages 11-29

4. The monadic second-order logic of graphs : Definable sets of finite graphs

   • Bruno Courcelle

   Pages 30-53

5. On systems of equations defining infinite graphs

   • Michel Bauderon

   Pages 54-73

6. Fault tolerant networks of specified diameter

   • H. Meijer, R. Dawes

   Pages 74-86

7. DFS tree construction: Algorithms and characterizations

   • Ephraim Korach, Zvi Ostfeld

   Pages 87-106

8. Serializable graphs

   • K. Vidyasankar

   Pages 107-121

9. Transitive closure algorithms for very large databases

   • Joachim Biskup, Holger Stiefeling

   Pages 122-147

10. A graph-based decomposition approach for recursive query processing

    • Dietmar Seipel

    Pages 148-165

11. Construction of deterministic transition graphs from dynamic integrity constraints

    • Udo W. Lipeck, Dasu Feng

    Pages 166-179

12. (Time × space)-efficient implementations of hlerarchical conceptual models

    • Nicola Santoro

    Pages 180-189

13. Dominance in the presence of obstacles

    • Mark T. de Berg, Mark H. Overmars

    Pages 190-201

14. Separating a polyhedron by one translation from a set of obstacles

    • Otto Nurmi, Jörg-R. Sack

    Pages 202-212

15. Linear time algorithms for testing approximate congruence in the plane

    • Sebastian Iwanowski

    Pages 213-228

16. Moving regular k-gons in contact

    • Stephan Abramowski, Bruno Lang, Heinrich Müller

    Pages 229-242

17. Epsilon-nets for halfplanes

    • Gerhart Woeginger

    Pages 243-252

18. Greedy triangulation can be efficiently implemented in the average case

    • Andrzej Lingas

    Pages 253-261

19. A simple systolic method to find all bridges of an undirected graph

    • Manfred Schimmler, Heiko Schröder

    Pages 262-267

20. Colouring perfect planar graphs in parallel

    • Iain A. Stewart

    Pages 268-275

This volume presents the proceedings of the 14th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '88), held from June 15 to 17, 1988 in Amsterdam, The Netherlands. It contains 31 papers on new or current developments in the area of graph-based algorithms. The topics covered include e.g. structural graph theory, parallel graph algorithms, graph-based modeling (in database theory and VLSI), computational geometry and applied graph theory. The book contains the revised versions of all the papers presented at the workshop. The revisions are based on comments and suggestions received by the authors during and after the workshop.

• Computer
• Graph
• Graph theory
• Sim
• Triangulation
• algorithm
• algorithms
• computational geometry
• logic
• modeling
• topology
• combinatorics
• algorithm analysis and problem complexity
• data structures

Policies and ethics