Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
A chordal graph H H is a triangulation of a graph G G if H H is obtained by adding edges to G G . If no proper subgraph of H H is a triangulation of G G we call H H a minimal triangulation of G 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.
minimal triangulations co-comparability graphs at-free claw-free graphs bandwidth proper interval graphs interval graphs partition refinement