Approximating treewidth and pathwidth of some classes of perfect graphs

In this paper we discuss algorithms that approximate the treewidth and pathwidth of cotriangulated graphs, permutation graphs and of cocomparability graphs. For a cotriangulated graph, of which the treewidth is at most k we show there exists an O(n^2) algorithm finding a path-decomposition with width at most 3k+4. If G[π] is a permutation graph with treewidth k, then we show that the pathwidth of G[π] is at most 2k, and we give an algorithm which constructs a path-decomposition with width at most 2k in time O(n^k). We assume that the permutation π is given. In this paper we also discuss the problem of finding an approximation for the treewidth and pathwidth of cocomparability graphs. We show that, if the treewidth of a cocomparability graph is at most k, then the pathwidth is at most O(k^2), and we give a simple algorithm finding a path-decomposition with this width. The running time of the algorithm is dominated by a coloring algorithm of the graph. Such a coloring can be found in time O(n^3).
If the treewidth is bounded by some constant, previous results (i.e. [10, 21]), show that, once the approximations are given, the exact treewidth and pathwidth can be computed in linear time for all these graphs.