Ordered graph
Encyclopedia
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 joined to it and precede it in the ordering. More precisely,
is a parent of 
in the ordered graph 
if 
and 
. 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.
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
, if both 
and 
are parents of it and are not joined by an edge, the edge 
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.
Node
is considered first. Its parents are 
and 
, as they are both joined to 
and both precede 
in the ordering. Since they are not joined by an edge, one is added.
Node
is considered second. While this node only has 
as a parent in the original graph, it also has 
as a parent in the partially built induced graph. Indeed, 
is joined to 
and also precede 
in the ordering. As a result, an edge joining 
and 
is added.
Considering
does not produce any change, as this node has no parents.
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
and 
are swapped.
As in the previous case, both
and 
are parents of 
. Therefore, an edge between them is added. According to the new order, the second node that is considered is 
. This node has only one parent (
). Therefore, no new edge is added. The third considered node is 
. Its only parent is 
. Indeed, 
and 
are not joined this time. As a result, no new edge is introduced. Since 
has no parent as well, the final induced graph is the one above. This induced graph differs from the one produced by the previous ordering.
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
with a total order
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
over its nodes.
In an ordered graph, the parents of a node are the nodes that are joined to it and precede it in the ordering. More precisely,
is a parent of in the ordered graph if and . 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.
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
, if both and are parents of it and are not joined by an edge, the edge is added to the graph. Since the parents of a node are always connected with each other, the induced graph is always chordalChordal graph
In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...
.
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.
 |
 |
 |
| The original graph. | Edge added considering the parents of  |
Edge added considering the parents of  |
Node
is considered first. Its parents are and , as they are both joined to and both precede in the ordering. Since they are not joined by an edge, one is added.Node
is considered second. While this node only has as a parent in the original graph, it also has as a parent in the partially built induced graph. Indeed, is joined to and also precede in the ordering. As a result, an edge joining and is added.Considering
does not produce any change, as this node has no parents.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
and are swapped.  |
 |
Same graph, but the order of  and  is swapped |
Graph after considering  |
As in the previous case, both
and are parents of . Therefore, an edge between them is added. According to the new order, the second node that is considered is . This node has only one parent (). Therefore, no new edge is added. The third considered node is . Its only parent is . Indeed, and are not joined this time. As a result, no new edge is introduced. Since has no parent as well, the final induced graph is the one above. This induced graph differs from the one produced by the previous ordering.