Abstract:
Traditionally, efficient algorithms for computing a minimal triangulation
(i.e. embedding a graph into a triangulated graph by adding an inclusion-minimal
set of edges) required first computing a special ordering on the vertices
of the graph, called a minimal ordering. We give a new algorithm
which efficiently computes a minimal triangulation using an arbitrary ordering
on the vertices.