Efficient graph representations (Q1396949): Difference between revisions

The monograph deals with graphs in special classes, their representations, properties and algorithms. To process a graph algorithmically it must be stored in a computer. Different classes of graphs allow different representations, and for some classes several representations exist. Thereby the number of bits used to encode a graph does not only depend on its size and the number of graphs of the same size in the class, but also on structural properties of these graphs. With respect to graph classes this book relates to [\textit{A. Brandstädt}, \textit{V. B. Le} and \textit{J. P. Spinrad}, Graph classes: a survey (SIAM Monographs on Discrete Mathematics and Applications 3, Philadelphia, PA) (1999; Zbl 0919.05001)]. The monograph is organised in 16 chapters: (1) Introduction (background on graphs and algorithms), (2) Implicit representation, (3) Intersection and containment representations (covering chordal graphs, comparability graphs, interval graphs, permutation graphs and other classes), (4) Real numbers in graph representations (Warren's theorem), (5) Classes which use global information (chordal comparability graphs and weakly chordal graphs are considered here), (6) Visibility graphs, (7) Intersection of graph classes (such as weakly chordal comparability graphs or AT-free coAT-free graphs), (8) Graph classes defined by forbidden subgraphs (for example cographs, triangle-free graphs and claw-free graphs), (9) Chordal bipartite graphs, (10) Matrices (with various forbidden submatrices), (11) Decomposition (e.g.\ modular decomposition and split decomposition; also clique-width, clique separators, skew partition and 2-join), (12) Elimination schemes (distance hereditary graphs and strongly chordal graphs appear here), (13) Recognition algorithms, (14) Robust algorithms for optimization problems (sometimes faster than recognition), (15) Characterization and construction (for chordal, unit interval and unit circular arc graphs), and (16) Applications. Each chapter comes with lots of helpful exercises. A glossary and an exhaustive list of 495 references complete this book which presents scattered results on graph classes in the uniform framework of representations. Several typographical errors (should certainly have been sorted out in the editing process) do not distort the presentation too much. Overall, this monograph is recommended to everyone working in the field.