Overview of trees in graph theory

The most basic way in which graphs are related to trees is through the block cut tree of the graph, which can be formed by any connected component. The most basic tree related property of a graph is the nature of its biconnected components. A tree is simply a graph whose biconnected components are all trivial. A cactus tree has the simplest biconnected components, and a clique tree or a block graph has the largest biconnected components. A pseudoforest is a cactus tree with only one biconnected component in each connected component.

• The block cut tree of a graph
• The modular decomposition tree of a graph

The other aspect of a graph is the modular decomposition. Given any cograph we can form a cotree which roughly describes the structure of the cograph, as the cograph can be constructed by unions and complements. The modular decomposition is a generalization of this process to general graphs, and produces perhaps the most interesting information about the graph besides the block cut tree of the graph. Well these two structures describe the vertices of the graph, the spanning trees describe sets of edges of the graph. There are two types of trees: directed and undirected trees. Well the undirected trees are already graphs, the directed trees have a comparability which produces its own class of graphs.

• Tree graphs
• Comparability graphs of trees

The comparability graphs of trees are precisely the trivially perfect graphs. The trivially perfect graphs are the unique class of graphs that are isomorphic to preorders in a manner that preserves in adjacency. In this way, the trivially perfect graph can be recovered from the forest preorder by its order comparability. This demonstrates that tree graphs and structures seem to be the most directly related to order theory. Structures that are related to order theory tend to forbid certain cycles, and the comparability graphs and co-comparability for example are both perfect graphs so they forbid odd cycles. Another way to take a graph and produce an order is to select a root and form an ordered tree from that. In this way, both tree graphs and comparability graphs of trees can be converted to preorders of different sorts.