# The Clique-Width of Minimal Series-Parallel Digraphs
## 3 Directed Clique-Width of Minimal Series-Parallel Digraphs (MSP DAGs)
Furthermore, by the definition of \(t_{\alpha}\) without any relabeling and the assumptions for \(t_{\alpha_{1}}\) and \(t_{\alpha_{2}}\), in \(G[\alpha]\) all non-isolated sources are labeled by 1, all non-isolated sinks are labeled by 2, all vertices being neither sources nor sinks are labeled by 3, and all isolated vertices are labeled by 4. Hence, the expression \(t_{\alpha}=t_{1,\alpha}\oplus t_{2,\alpha}\) constructs digraph \(G[\alpha]\) using at most 6 labels. * Suppose that \(\alpha\) is an \(S\)-node. In this case, we define \(t_{\alpha}=t_{1,\alpha}\oplus t_{2,\alpha}\), where \[t^{\prime} = \alpha_{4,2}(t_{2,\alpha_{1}}\oplus\rho_{4\to 2}(t_{2, \alpha_{2}}))\] \[t^{\prime\prime} = \alpha_{5,2}(\rho_{2\to 5}(t_{1,\alpha_{1}})\oplus t^{ \prime})\] Figure 3:0 Figure 3:1 Figure 3:2 Figure 3(d)-g illustrate the construction of \(G[\alpha]\) from the two digraphs shown in Figure 3(a,b) following the expressions \(t^{\prime},t^{\prime\prime},t^{\prime\prime\prime},t_{1,\alpha}\), and \(t_{2,\alpha}\). For the correctness, we observe that \(t^{\prime}\) defines the arcs from \(t_{2,\alpha_{1}}\) to \(t_{2,\alpha_{2}}\), i.e. the arcs between the isolated vertices of \(G[\alpha_{1}]\) to the isolated vertices of \(G[\alpha_{2}]\) using a relabeling from 4 to 2 for those of \(G[\alpha_{2}]\), since they become non-isolated sinks of \(G[\alpha]\). Next \(t^{\prime\prime}\) defines the arcs from \(t_{1,\alpha_{1}}\) to \(t_{2,\alpha_{2}}\), i.e. the arcs between the non-isolated sinks of \(G[\alpha_{1}]\) and the isolated vertices of \(G[\alpha_{2}]\) are inserted using a relabeling from 2 to auxiliary label 5 for the non-isolated sinks of \(G[\alpha_{1}]\). Further \(t^{\prime\prime\prime}\) defines the arcs from \(t_{1,\alpha_{1}}\) and \(t_{2,\alpha_{1}}\) to \(t_{1,\alpha_{2}}\), i.e. the arcs from the non-isolated sinks of \(G[\alpha_{1}]\) and the isolated vertices of \(G[\alpha_{1}]\) to the non-isolated sources of \(G[\alpha_{2}]\) using a relabeling from 1 to auxiliary label 6 for the non-isolated sources of \(G[\alpha_{2}]\). Finally in \(t_{1,\alpha}\) the relabeling from 4 to 1 ensures that the isolated vertices of \(G[\alpha_{1}]\) are labeled by 1 since they are non-isolated sources in \(G[\alpha]\) and the auxiliary labels 5 and 6 are both changed to 3 since the non-isolated sinks of \(G[\alpha_{1}]\) and the non-isolated sources of \(G[\alpha_{2}]\) are neither sources nor sinks in \(G[\alpha]\). Expression \(t_{2,\alpha}\) is empty, since \(G[\alpha]\) does not contain isolated vertices. Hence, the expression \(t_{\alpha}=t_{1,\alpha}\oplus t_{2,\alpha}\) constructs digraph \(G[\alpha]\) using at most 6 labels. By traversing \(T(G)\) in post-order we can calculate a directed clique-width 6-expression \(t_{\alpha}\) for every node \(\alpha\) of \(T(G)\) by the expressions given above. Since the \(r\) root of \(T(G)\) represents to whole digraph \(G\) we know that \(G\) can be constructed by directed clique-width 6-expression \(t_{r}\) and thus has directed clique-width at most 6. The construction of an MSP DAG by a directed clique-width 6-expression described in the proof of Theorem 1 can be translated into a pseudo code shown in Algorithm 1. Our algorithm associates with every node \(\alpha\) of \(T(G)\) two expressions \(t_{1}(\alpha)\) and \(t_{2}(\alpha)\), where \(t_{1}(\alpha)\) represents the construction of the subgraph induced by the non-isolated vertices of \(G[\alpha]\) and \(t_{2}(\alpha)\) represents the construction of the subgraph induced by the isolated vertices  
Figure 3:3 Illustration of construction in the proof of Theorem 1. The indices of the vertices represent their clique-width label. (**a**) The subgraph \(G[\alpha_{1}]\), (**b**) the subgraph \(G[\alpha_{2}]\), (**c**) \(G[\alpha]=G[\alpha_{1}]PG[\alpha_{2}]\), (**d**) digraph defined by expression \(t^{\prime}\), (**e**) digraph defined by expression \(t^{\prime\prime}\), (**f**) digraph defined by expression \(t^{\prime\prime\prime}\), (**g**) \(G[\alpha]=G[\alpha_{1}]SG[\alpha_{2}]\). of \(G[\alpha]\).