## Graph-Theoretic Concepts in Computer Science: 20th International Workshop. WG '94, Herrsching, Germany, June 16 - 18, 1994. ProceedingsThis volume presents the proceedings of the 20th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '94), held in Herrsching, Germany in June 1994. The volume contains 32 thoroughly revised papers selected from 66 submissions and provides an up-to-date snapshot of the research performed in the field. The topics addressed are graph grammars, treewidth, special graph classes, algorithms on graphs, broadcasting and architecture, planar graphs and related problems, and special graph problems. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Domino Treewidth | 1 |

A Lower Bound for Treewidth and Its Consequences | 14 |

R Garbe | 36 |

Copyright | |

19 other sections not shown

### Common terms and phrases

ADHP adjacent assume biconnected graph binary tree Boolean branching programs broadcast chordal graphs chordless cycle class of graphs clique color complete graph complexity components Computer Science connected enumeration construction contains convex drawing convex planar Corollary corresponding crossing number cycle decomposition defined Definition degree denote duplicated expression eNCE graph grammars encoding exists factoring function given graph G graph isomorphism graph rewriting Horn formula hyperedge hypergraph induced subgraph inert fugitive Informatik input integer isomorphism layered graph Lemma Let G linear lower bound matching maximal maximum minimal node reduction nonterminal nonterminal nodes NP-complete number of vertices obtain optimal ordered tree pair path graphs permutation planar graph polynomial prefix graph problem without bases Proc processors productions Proof recursively result root search number searchers sequence solved st-dag step strong V-structures subdag subexpression subset Theorem tournament tree-decomposition treewidth triconnected triple upper bound variables vertex ranking weight width