An ordered graph is a graph with a total order over its nodes.

In an ordered graph, the parents of a node are the nodes that are adjacent to it and precede it in the ordering.. The width of a node is the number of its parents, and the width of an ordered graph is the maximal width of its nodes.

The induced graph of an ordered graph is obtained by adding some edges to an ordering graph, using the method outlined below. The induced width of an ordered graph is the width of its induced graph.

is added to the graph. Since the parents of a node are always connected with each other, the induced graph is always chordal.

As an example, the induced graph of an ordered graph is calculated. The ordering is represented by the position of its nodes in the figures: a is the last node and d is the first. in the ordering. Since they are not joined by an edge, one is added.

is added.

does not produce any change, as this node has no parents.

are swapped in the order. has no parent, the final induced graph is the one above. This induced graph differs from the one produced by the previous ordering.

See also

• Directed graph

• Local consistency

References