ChordalGraph -- a chordal graph

Description

This type represents a chordal graph G, together with a perfect elimination ordering.

An ordering of the vertices is a perfect elimination ordering if for each vertex $v$ the vertices $N(v)$ form a clique, where $N(v)$ consists of the adjacent nodes that occur after $v$ in the ordering. A graph is chordal if and only if it has a perfect elimination ordering. For notational convenience, ChordalGraph orients the edges of the graph according to such ordering.

The constructor of this type is chordalGraph. Chordal graphs can be visualized with displayGraph.

Several combinatorial problems can be solved efficiently on chordal graphs. In particular, chromaticNumber, cliqueNumber.

Functions and methods returning an object of class ChordalGraph :

chordalGraph(Digraph) -- see chordalGraph -- chordal completion of a graph
chordalGraph(Graph) -- see chordalGraph -- chordal completion of a graph
chordalGraph(Graph,List) -- see chordalGraph -- chordal completion of a graph
chordalGraph(ElimTree) -- see ElimTree -- the elimination tree of a chordal graph

Methods that use an object of class ChordalGraph :

chromaticNumber(ChordalGraph)
cliqueNumber(ChordalGraph)
inducedSubgraph(ChordalGraph)
isChordal(ChordalGraph)
isPerfect(ChordalGraph)
net(ChordalGraph)
elimTree(ChordalGraph) -- see elimTree -- elimination tree of a chordal graph
treewidth(ChordalGraph) -- see treewidth -- treewidth of a graph

For the programmer

The object ChordalGraph is a type, with ancestor classes Digraph < HashTable < Thing.