ABSTRACT
Desirable Properties Equivalent to α-Acyclicity . . . . . . . . . . . . . . . . . . . . . . . 767 29.3.7 Dually Chordal Graphs, Maximum Neighborhood Orderings, and
Hypertrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 770 29.3.8 Bipartite Graphs, Hypertrees, and Maximum
Neighborhood Orderings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 773 29.3.9 Further Matrix Notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 775
29.4 Totally Balanced Hypergraphs and Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 776 29.4.1 Totally Balanced Hypergraphs versus β-Acyclic Hypergraphs . . . . . . . . 776 29.4.2 Totally Balanced Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 778
29.5 Strongly Chordal and Chordal Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 779 29.5.1 Strongly Chordal Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 779
29.5.1.1 Elimination Orderings of Strongly Chordal Graphs . . . . . . 779 29.5.1.2 Γ-Free Matrices and Strongly Chordal Graphs . . . . . . . . . . . 782 29.5.1.3 Strongly Chordal Graphs as Sun-Free Chordal Graphs . . . 783
29.5.2 Chordal Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 786 29.6 Tree Structure Decomposition of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 788
29.6.1 Cographs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 788 29.6.2 Optimization on Cographs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 790 29.6.3 Basic Module Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 791 29.6.4 Modular Decomposition of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793 29.6.5 Clique Separator Decomposition of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 794
29.7 Distance-Hereditary Graphs, Subclasses, and γ-Acyclicity . . . . . . . . . . . . . . . . . . . . . . 794 29.7.1 Distance-Hereditary Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 794 29.7.2 Minimum Cardinality Steiner Tree Problem in Distance-Hereditary
Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 799
29.7.3 Important Subclasses of Distance-Hereditary Graphs . . . . . . . . . . . . . . . . . 801 29.7.3.1 Ptolemaic Graphs and Bipartite Distance-Hereditary
Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 801 29.7.3.2 Block Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 802 29.7.3.3 γ-Acyclic Hypergraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 802
29.8 Treewidth and Clique-Width of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 803 29.8.1 Treewidth of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 803 29.8.2 Clique-Width of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 805
29.9 Complexity of Some Problems on Tree-Structured Graph Classes . . . . . . . . . . . . . . 807 29.10 Metric Tree-Like Structures in Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 808
29.10.1 Tree-Breadth, Tree-Length, and Tree-Stretch of Graphs . . . . . . . . . . . . . . 808 29.10.2 Hyperbolicity of Graphs and Embedding Into Trees . . . . . . . . . . . . . . . . . . 810
The aim of this chapter is to present various aspects of tree structure in graphs and hypergraphs and its algorithmic implications together with some important graph classes having nice and useful tree structure. In particular, we describe the hypergraph background and the tree structure of chordal graphs (introduced in Chapter 28) and some graph classes which are closely related to chordal graphs such as chordal bipartite graphs, dually chordal graphs, and strongly chordal graphs as well as important subclasses.
