Treewidth

Abstract

This thesis focuses on problems related to treewidth and pathwidth of graphs. Many problems are difficult to solve for graphs in general. The treewidth of a graph is a good indication whether one can obtain a solution within reasonable time. A necessary ingredient is a treedecomposition of the graph with small width. Equivalently, one needs an embedding of the graph into a chordal graph with a smallest possible clique number. In Chapter 2 we start, by giving the definitions. Chapters 3, 4, 5 and 6 deal with problems related to the structure of graphs with bounded treewidth. In Chapter 3 we solve the following problem (stemming from phylogeny). Let G be a graph of which the vertices are colored with 3 colors such that adjacent vertices have a different color. The problem is to find a chordal embedding of the graph which keeps the property that adjacent vertices are colored differently. In Chapter 4 we enumerate biconnected partial 2-trees. In Chapter 5, we show that the treewidth of random graphs with a linear number of edges have treewidth which is also linear in the number of points. This motivates us to look for the treewidth of graphs with a certain underlying structure. We discuss some of these topics in Chapter 7, 8 and 9. In Chapter 6 we show that one can test superperfection for graphs of bounded treewidth in linear time. In Chapter 7 we show that one can approximate, or compute exactly, the treewidth of complements of chordal graphs, splitgraphs, convex graphs and permutation graphs. For cocomparability graphs we give an algorithm that finds a pathdecomposition which is quadratic in the treewidth of the graph. Chapter 8 shows that the treewidth of chordal bipartite graphs can be computed in polynomial time. In Chapter 9 we show a similar result for permutation graphs and we generalize to cocomparability graphs of bounded dimension. As a corollary, we show that treewidth and pathwidth are the same for cocomparability graphs. In Chapter 9 we deal with the problem of approximating the treewidth of graphs in general. In Chapter 11 and 12 we give algorithms that check whether the pathwidth of a graph is at most k. These algorithms can be implemented to run in O(n log n) time.