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.[1] More precisely,
n
m
\langleN,E,<\rangle
(n,m)\inE
n<m
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.[2]
Given an ordered graph, its induced graph is another ordered graph obtained by joining some pairs of nodes that are both parents of another node. In particular, nodes are considered in turn according to the ordering, from last to first. For each node, if two of its parents are not joined by an edge, that edge is added. In other words, when considering node
n
m
l
(m,l)
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.
Node
a
b
c
a
a
Node
b
d
c
c
b
b
c
d
Considering
d
Processing nodes in order matters, as the introduced edges may create new parents, which are then relevant to the introduction of new edges. The following example shows that a different ordering produces a different induced graph of the same original graph. The ordering is the same as above but
b
c
As in the previous case, both
b
c
a
c
b
b
d
b
c
d