Efficient Graph Representations

Representations of graphs of various types, very often of geometric flavour, are studied both for practical applications or motivation and for nice theoretical and algorithmic graph properties. Many such classes allow elegant characterizations and for several of them, basic optimization problems (such as maximum clique, maximum independent set, chromatic number, etc.) can be solved in polynomial time. In some cases, the latter is known only when a representation (which itself may be hard to find) is given. This book presents a fantastic encyclopedia of graph classes defined via representations, their properties, relations and algorithms. The range is so overwhelming that a short review cannot even list them. Let us just mention that the reader will find here thorough information about basic intersection defined classes (interval or chordal graphs), about many of their generalizations (strongly chordal graphs, AT-free graphs, chordal bipartite graphs and many more), about inclusion and visibility representations of different types, or about more recently introduced classes such as interval filament graphs. Presenting efficient algorithms requires the description of some useful techniques and the reader will learn, for instance, about join and separator decompositions and the concept of clique-width. Though the title may not indicate this, many NP-hardness results are also quoted. It is only natural that a book of this extent cannot be fully self-contained. However, the bibliography is very extensive and the “Survey of results on graph classes” on the last twenty pages is so well organized, that everyone can find easy directions to material containing full proofs when necessary. Many research problems and exercises make this book suitable both for researchers in the area and for graduate students. It is recommended to anyone interested in algorithmic graph theory.

Book details




User login