Many interesting new special graph classes and algorithms dealing with them have been introduced in recent years. Therefore, as the authors write in the preface to this volume, "it is probably useful to have a new survey that attempts to describe the world of special graph classes with an emphasis on the algorithmic point of view." They fully succeed in their intentions with this well-organized handbook. More than 200 graph classes are surveyed, and their definitions, basic properties, and characterizations are given.
Chapter 1 introduces basic graph and hypergraph concepts and properties, chordal graphs as an example of a class that is a generalization of trees with different characterizations and many important applications, the concept of partial order, and modular decomposition. Chapter 2 includes the concepts of perfection, properties of perfect graphs and perfect graph theorems, sharpening perfection, generalized perfection, and related concepts. Chapter 3 is concerned with the chordality condition, cycles and chords in bipartite graphs, subclasses and variants of perfect graphs, bridged graphs, and isometric cycles. Chapter 4 is devoted to models and interactions. Line graphs, interval graphs and their generalizations, and other important concepts, such as visibility, are discussed. Many intersting examples of vertex and edge orderings are considered in chapter 5. Chapter 6 gives a complete account of posets. Partial orders and their graphs, poset dimension, containment graphs, series-parallel posets, interval orders, arborescence orders and threshold orders, and comparability graphs with other restrictions are surveyed.
Chapter 7 presents those graph classes having definitions or characterizations in terms of finite or infinite collection of forbidden subgraphs. Chapter 8 presents hypergraphs, some acyclicity types, classes with dual hypertree characterizations, perfect graphs and normal hypergraphs, and interval hypergraphs. Chapter 9 deals with the correspondence between many properties of graphs, bipartite graphs, hypergraphs, and matrices. Distance in graphs is one of the most important topics in algorithmic graph theory, and has led to many important results on graphs and connections to other fields, such as metric spaces. Distance properties are exhaustively considered in chapter 10.
Chapter 11 is devoted to algebraic compositions and recursive definitions. Series-parallel graphs and recursively defined perfect graphs are considered. Methods of decomposition are discussed in chapter 12, beginning with modular decomposition. Homogeneous, split, and other decomposition; minimal separators; and small and balanced operators are also considered. The many results on threshold graphs and related concepts, such as the threshold dimension, constant-bounded Dilworth number, degree sequences, and matroidal and matrogenic graphs, are surveyed in chapter 13. The last chapter is concerned with the strong perfect graph conjecture - the conjecture that states that the only perfect graphs are those graphs containing no odd holes and no antiholes as induced subgraphs.
Appendix A contains information about the time complexity of recognition problems. Appendix B is devoted to containment relationships between classes. The bibliography, at 42 pages and containing 1098 references, is exhaustive. It is one of the most valuable parts of the book. There is also a detailed subject index.
This volume will be extremely valuable for researchers as well as nonspecialists wanting to learn and work in the general area of the theory of graphs and their applications. Moreover, because of its extensive bibliography, it is also an excellent starting point for a literature search.