Society for Industrial and Applied Mathematics, 1999, -321 pp.
When dealing with special graph classes and algorithmic problems on them, a main source is the classical book of Golumbic, Algorithmic Graph Theory and Perfect Graphs. The book, however, appeared in 1980, and since that time many interesting new classes have been introduced. Therefore, 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.
There are many reasons for the interest in this field of research. These come from discrete mathematics as well as theoretical arid practical computer science. discrete mathematics as well as theoretical arid practical computer science.
Graphs are a good model for describing "real-world" and computer-science situations such as
— interconnection and transport networks for information exchange;
— VLSI layouts;
— computational geometry;
— graph drawing;
— scheduling and partial-order problems;
— molecular biology (DNAmappings), phylogenetic trees;
— temporal reasoning;
— synchronizing parallel processes;
— sparse systems of linear equations;
— desirable properties of relational database schemes.
The last properties are closely related to hypergraph acyclicity, Helly and tree properties of hypergraphs, and graph chordality.
For many applications, the graphs used in the models have special properties such as
— min-max (in)equalities of certain parameters;
— cycles and chords;
— separator properties;
— distance properties;
— elimination orderings of the vertex set;
— composition/decomposition properties, recursive constructions;
— intersection, containment, or overlap models or measured variants of them;
— tree structure in many variants (reflected by related hypergraphs and matrices).
To efficiently solve such basic algorithmic problems as graph coloring, maximum independent set/maximum clique, Steiner tree, and dominating set, it is extremely important to know the structural properties of the graphs under consideration. A typical and classical example is the class of chordal graphs: every cycle of length at least four has at least one chord. These graphs have many different characterizations and thus appear in almost every chapter of this survey.
There are (at least) two main groups of graph properties that are helpful for designing polynomial-time algorithms:
— Graphs that fulfill certain min-max equalities such as Konig's theorem for bipartite graphs and Dilworth's theorem for partial orders. This approach leads to perfect graphs that have many nice algorithmic consequences.
— Graphs that generalize tree properties (trees of vertices or trees of hyperedges), since many problems are easy to solve on trees. Of course the problems again become hard on these generalizations if the graphs are "too far" from trees.
Of course the survey is also restricted to the basic properties; characterizations and inclusions of a collection of graph classes that seem to be important cannot exhaustively present the current knowledge. In particular, it is not. possible to discuss the complexity of selected algorithmic graph problems on as many classes as was done in [631]; for several problems there are separate monographs on the algorithmic behavior of the problem on special graph classes; see, for instance, [706] for the traveling salesman problem. It is sometimes hard to decide whether an algorithmically oriented paper using special graphs should be included in the survey. We try to include only those papers that describe interesting structural properties of the classes. We are not able to include all of these several thousand papers and apologize for the omitted ones, which could tu out to be important. The same holds true for the papers on special graph classes not included here due to space restrictions or due to our lack of knowledge. In particular, we do not describe the worlds of directed graphs, infinite graphs, and random graphs. Good sources for more information on infinite graphs are [505, 312, 1023], and a good source for random graphs is [125].
Basic Concepts.
Perfection, Generalized Perfection, and Related Concepts.
Cycles, Chords, and Bridges.
Models and Interactions.
Vertex and Edge Orderings.
Posets.
Forbidden Subgraphs.
Hypergraphs and Graphs.
Matrices and Polyhedra.
Distance Properties.
Algebraic Compositions and Recursive Definitions.
Decompositions and Cutsets.
Threshold Graphs and Related Concepts 1.
The Strong Perfect Graph Conjecture.
When dealing with special graph classes and algorithmic problems on them, a main source is the classical book of Golumbic, Algorithmic Graph Theory and Perfect Graphs. The book, however, appeared in 1980, and since that time many interesting new classes have been introduced. Therefore, 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.
There are many reasons for the interest in this field of research. These come from discrete mathematics as well as theoretical arid practical computer science. discrete mathematics as well as theoretical arid practical computer science.
Graphs are a good model for describing "real-world" and computer-science situations such as
— interconnection and transport networks for information exchange;
— VLSI layouts;
— computational geometry;
— graph drawing;
— scheduling and partial-order problems;
— molecular biology (DNAmappings), phylogenetic trees;
— temporal reasoning;
— synchronizing parallel processes;
— sparse systems of linear equations;
— desirable properties of relational database schemes.
The last properties are closely related to hypergraph acyclicity, Helly and tree properties of hypergraphs, and graph chordality.
For many applications, the graphs used in the models have special properties such as
— min-max (in)equalities of certain parameters;
— cycles and chords;
— separator properties;
— distance properties;
— elimination orderings of the vertex set;
— composition/decomposition properties, recursive constructions;
— intersection, containment, or overlap models or measured variants of them;
— tree structure in many variants (reflected by related hypergraphs and matrices).
To efficiently solve such basic algorithmic problems as graph coloring, maximum independent set/maximum clique, Steiner tree, and dominating set, it is extremely important to know the structural properties of the graphs under consideration. A typical and classical example is the class of chordal graphs: every cycle of length at least four has at least one chord. These graphs have many different characterizations and thus appear in almost every chapter of this survey.
There are (at least) two main groups of graph properties that are helpful for designing polynomial-time algorithms:
— Graphs that fulfill certain min-max equalities such as Konig's theorem for bipartite graphs and Dilworth's theorem for partial orders. This approach leads to perfect graphs that have many nice algorithmic consequences.
— Graphs that generalize tree properties (trees of vertices or trees of hyperedges), since many problems are easy to solve on trees. Of course the problems again become hard on these generalizations if the graphs are "too far" from trees.
Of course the survey is also restricted to the basic properties; characterizations and inclusions of a collection of graph classes that seem to be important cannot exhaustively present the current knowledge. In particular, it is not. possible to discuss the complexity of selected algorithmic graph problems on as many classes as was done in [631]; for several problems there are separate monographs on the algorithmic behavior of the problem on special graph classes; see, for instance, [706] for the traveling salesman problem. It is sometimes hard to decide whether an algorithmically oriented paper using special graphs should be included in the survey. We try to include only those papers that describe interesting structural properties of the classes. We are not able to include all of these several thousand papers and apologize for the omitted ones, which could tu out to be important. The same holds true for the papers on special graph classes not included here due to space restrictions or due to our lack of knowledge. In particular, we do not describe the worlds of directed graphs, infinite graphs, and random graphs. Good sources for more information on infinite graphs are [505, 312, 1023], and a good source for random graphs is [125].
Basic Concepts.
Perfection, Generalized Perfection, and Related Concepts.
Cycles, Chords, and Bridges.
Models and Interactions.
Vertex and Edge Orderings.
Posets.
Forbidden Subgraphs.
Hypergraphs and Graphs.
Matrices and Polyhedra.
Distance Properties.
Algebraic Compositions and Recursive Definitions.
Decompositions and Cutsets.
Threshold Graphs and Related Concepts 1.
The Strong Perfect Graph Conjecture.