Chordal graph

In graph theory, a graph is called triangulated or chordal if it satisfies one of the following equivalent conditions:

• Each induced circuit is a triangle. A circle is induced there when no further edges in the original graph exist between its corners.
• Every minimal separator from two vertices a and b is a clique.
• Each induced subgraph contains a simplicial corner (Rose, 1970), ie, a corner of which form a clique neighbors.
• G is cut graph of a set of subtrees of a tree ( Gavril, 1974).

Properties

In triangulated graph allows the calculation of the parameters, , and - for arbitrary graphs is a NP- equivalent problem - perform in linear time. The characterization over simplicial corners allows Chordalitätstest in linear time. As a perfect elimination order is called here a sequence of nodes of the graph so that for every graph with the (up by eliminating the node ) node-set limited: is simplicial in. Everyone ( with respect to the selected order ) "smallest" node in thus forms a clique with its neighbors.

Triangulated graphs are not to be confused with the ( maximal planar ) triangle graph. Triangle graph, not all triangulated, how one can think of a graph, which consists of a cycle of length, in the interior and exterior of each another node is adjacent to all nodes of the circle. Conversely, triangulated graphs not necessarily be triangular graph, such as a non-planar full graph shows.