Interval Graph And Tree-like Decomposition

Tree-like structure is an important structure arising from nature science and mathematics. It has wide applications in many fields, such as graph algorithm, computer science, biological mathematics and so on. Tree-like decomposition is an important tool in describing the tree-likeness of graphs, so it needs to be well studied.In this paper, we first introduce interval graphs which have simple tree-like structure, and then we discuss the basic properties and equivalent descriptions of interval graphs and proper interval graphs. Second, several tree-like decomposition methods are mainly presented:We deal with tree decomposition and tree width of graphs and hypergraphs, which play a central position in graph structure; Then we propose the notion of elimination width, and get the recursive equation of tree width and elimination width respectively, so that we draw the conclusion that they are equal. Furthermore, we closely study the elimination decomposition of hypergraphs. The corresponding relations between tree decomposition and elimi-nation decomposition are discussed, and we prove them under the new definition of elimination width as well. At last, we discuss some decomposition methods of hypergraphs, including query decomposition, hypertree decomposition and so on. Moreover, the relations between tree width, query width and hypertree width of hypergraphs are shown.