Tolerance Graphs, Cambridge Studies in Advanced Mathematics 89

Geometric representations of graphs are intensively studied for their practical motivation, but also for the wealth of interesting and elegant properties. And many generally hard optimization problems become tractable when restricted to these classes of graphs. The stress on computational tractability and applications in bioinformatics make research in this area immensely popular. Graph theorists look for generalizations of classical tractable classes of structures, and for more than 20 years the notion of tolerance graphs has been around. The time seemed ripe to the authors for publishing a survey of related results and topics, and I can only agree. The first author has published a successful book in the area before (Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980), and the book under review is written in similar fresh and well readable style. It covers a lot of material on various variants of tolerance graphs, interval probe graphs and other generalizations of interval graphs, comparability invariants and algorithmic aspects of these. But if the reader is time constrained, selected topics can easily be isolated since many of the chapters can be read (almost) independently on others. Another advantage of the book lies in the decision of the authors to include most of the proofs, thus making the text self-contained as much as possible. The book can be used as a textbook for a specialized graduate course in combinatorics and graph theory as well as a source of many open research problems gathered in the last section. Very much recommended to researchers and Ph.D. students working in this area.

Book details
Author:  Publisher: 
GBP 40