Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs

A chordal graph H is a triangulation of a graph G if H is obtained by adding edges to G. If no proper subgraph of H is a triangulation of G we call H a minimal triangulation of G. We introduce a new LexBFS-like breadth-first-search algorithm min-LexBFS. We show that variants of min-LexBFS yield linear-time algorithms for computing minimal triangulations of AT-free claw-free graphs and co-comparability graphs. These triangulation algorithms are used to improve approximation algorithms for the bandwidth of AT-free claw-free and co-comparability graphs. We present a certifying recognition algorithm for proper interval graphs.