# chordalGraph -- chordal completion of a graph

## Synopsis

• Usage:
chordalGraph(G)
chordalGraph(G,ordering)
• Inputs:
• G, an instance of the type Graph,
• ordering, a list, (optional)
• Outputs:
• an instance of the type ChordalGraph, chordal graph that contains G as a subgraph

## Description

This method finds a simple chordal completion of a given graph G. A chordal completion is a supergraph of G that is chordal. If a vertex ordering is given, it completes the graph using this ordering; otherwise it finds one using a minimum degree ordering heuristic.

 i1 : G = wheelGraph(6) o1 = Graph{0 => {1, 2, 3, 4, 5}} 1 => {0, 2, 5} 2 => {0, 1, 3} 3 => {0, 2, 4} 4 => {0, 3, 5} 5 => {0, 1, 4} o1 : Graph i2 : chordalGraph G o2 = ChordalGraph{1 => {2, 0, 5} } 2 => {0, 3, 5} 0 => {3, 4, 5} 3 => {4, 5} 4 => {5} 5 => {} o2 : ChordalGraph
 i3 : G = graph(toList(0..9),{ {0,{6,7}},{1,{4,9}},{2,{3,5}},{3,{7,8}}, {4,{5,8}},{5,{8}},{6,{8,9}},{7,{8}},{8,{9}} }); i4 : chordalGraph G o4 = ChordalGraph{0 => {6, 7} } 1 => {4, 9} 2 => {3, 5} 3 => {5, 7, 8} 4 => {5, 8, 9} 5 => {7, 8, 9} 6 => {7, 8, 9} 7 => {8, 9} 8 => {9} 9 => {} o4 : ChordalGraph

## Caveat

If the input is a digraph, it must be topologically ordered; no check is made.