Approximating the treewidth of AT-free graphs
Using the specific structure of the minimal separators of AT-free graphs, we give a polynomial time algorithm that computes a triangulation whose width is no more than twice the treewidth of the input graph.
treewidth at-free graphs graph algorithms