Intersection Graphs of Subtrees
An alternative characterization of chordal graphs, due to Gavril (1974), involves trees and their subtrees.
From a collection of subtrees of a tree, one can define a subtree graph, which is an intersection graph that has one vertex per subtree and an edge connecting any two subtrees that overlap in one or more nodes of the tree. Gavril showed that the subtree graphs are exactly the chordal graphs.
A representation of a chordal graph as an intersection of subtrees forms a tree decomposition of the graph, with treewidth equal to one less than the size of the largest clique in the graph; the tree decomposition of any graph G can be viewed in this way as a representation of G as a subgraph of a chordal graph. The tree decomposition of a graph is also the junction tree of the junction tree algorithm.
Read more about this topic: Chordal Graph
Famous quotes containing the word intersection:
“You can always tell a Midwestern couple in Europe because they will be standing in the middle of a busy intersection looking at a wind-blown map and arguing over which way is west. European cities, with their wandering streets and undisciplined alleys, drive Midwesterners practically insane.”
—Bill Bryson (b. 1951)