Triangulation of a graph

Triangulation of a graph --- триангуляция графа.

Given a graph [math]\displaystyle{ G }[/math], triangulation of [math]\displaystyle{ G }[/math] is a graph [math]\displaystyle{ H }[/math] with the same set of vertices such that [math]\displaystyle{ G }[/math] is a subgraph of [math]\displaystyle{ H }[/math] and such that [math]\displaystyle{ H }[/math] is triangulated. One says that [math]\displaystyle{ G }[/math] is triangulated into [math]\displaystyle{ H }[/math].

There are two problems which have drawn much attention because of a large number of applications: MINIMUM FILL-IN problem and TREEWIDTH problem. The first problem is to triangulate a graph so that the number of added edges is minimum and the second one is to triangulate a graph so that the maximum clique size in the triangulated graph is minimum. These problems are both NP-hard.

See also

• Minimal triangulation,
• Planar triangulation.