Michael Data

A chordal graph is one where for each cycle of length greater than three, there is a chord connecting unconnected nodes of the cycle. It can be converted into a Bayesian network.

If the graph is chordal and represents a minimal I-map, the distribution it represents can be decomposed into product form. These graphs can be represented as DAG Bayesian Networks or as undirected Markov Networks.

Test for Chordality

Graph triangulation algorithm a.k.a. Fill-In algorithm. (Tarjan and Yannakakis 1984)


Fill-In Algorithm

Given a graph G

  1. Compute an ordering of the nodes from 1 to |V|
  2. From n = |V| to 1, connect all the parents of node n

If no edges were added, the graph was already chordal. However, the graph may have been chordal even if edges were added.