# Computing the Atom Graph of a Graph and the Union Join Graph of a Hypergraph
## 4 Computing the Atom Graph
### Algorithm Forest Join
: _Figure 3 shows an atom tree \(T\) of the graph \(G\) from Figure 1 and an execution of the algorithm Forest Join on \(T\) and its subset relation. It shows the forest \(T(\mathcal{A}_{S})-E_{S})\) for \(S=\{1\}\), where the edges of the atom graph associated with \(S\) are represented by dotted lines. For each clique minimal separator \(S\) different from \(\{1\}\), as \(\mathcal{A}_{S}\) is of size \(2\), \(AG(G)\) has a unique edge associated with \(S\), which is also an edge of \(T\). So, \(AG(G)\) is obtained from \(T\) by adding the edges associated with \(\{1\}\) that are not already present in \(T\)._  
**Theorem 2**. : _Given an atom tree of a connected graph \(G\) and its subset relation, the algorithm Forest Join computes the atom graph of \(G\) in \(O(p^{2})\) time, and therefore in \(O(n^{2})\) time._  
Figure 3: An execution of the algorithm Forest Join. **Proof. ** The correctness follows from Characterization 9. Let us prove the time complexity. As the algorithm Components runs in \(O(p)\) time and is called less than \(p\) times, it globally costs \(O(p^{2})\) time. As an edge \(XY\) is added to \(E^{\prime}\) at most once (when processing the first edge of \(T\) associated with \(X\cap Y\)), the number of edge additions to \(E^{\prime}\) is bounded by \(p^{2}\). Hence, the algorithm Forest Join runs in \(O(p^{2})\) time, and therefore in \(O(n^{2})\) time since \(G\) has at most \(n\) atoms (\(p\leq n\)). To evaluate the time complexity of computing the atom graph of \(G\) from an atom tree \(T\) of \(G\) using the algorithm Forest Join, we need the time complexity of computing the subset relation of \(T\). **Proposition 1**. : _Given an atom tree of a connected graph, its subset relation can be computed in \(O(min(n^{\omega},ps))\) time, and therefore in \(O(min(n^{\omega},nm))\) time._  
**Proof. ** It follows from the proof of Property 7 that the sets \(X\cap Y\) for each edge of \(T\) can be computed in \(O(s)\) time. and that the sum of their sizes is bounded by \(s\). As the inclusion of \(X\cap Y\) in \(X^{\prime}\cap Y^{\prime}\) or not can be determined in \(O(|X\cap Y|)\) time, the subset relation can be computed in \(O(s+ps)\) time, i.e., in \(O(ps)\) time. Alternatively, as \(sub(XY,X^{\prime}Y^{\prime})\) is equivalent to \(|X\cap Y|=|(X\cap Y)\cap(X^{\prime}\cap Y^{\prime})|\), it can be evaluated in \(O(1)\) time, and therefore in \(O(p^{2})\) time globally, provided that the values of \(|X\cap Y|\) and \(|(X\cap Y)\cap(X^{\prime}\cap Y^{\prime})|\) have been pre-computed. The values of \(X\cap Y\) and \(|X\cap Y|\) for each edge \(XY\) of \(T\) can be computed in \(O(s)\) time, and the values of \(|(X\cap Y)\cap(X^{\prime}\cap Y^{\prime})|\) in \(O((n+p)^{\omega})\) time, since they are the elements of the product of the transposition of \(M\) by \(M\), where \(M\) is the \(n\times(p-1)\) incidence matrix of the (possibly non-simple) hypergraph whose vertex set is \(V\) and whose hyperedges are the sets \(X\cap Y\) for each edge \(XY\) of \(T\). Hence, this alternative complexity is in \(O(p^{2}+s+(n+p)^{\omega})\) time, i.e., in \(O((n+p)^{\omega})\) time, since \(p^{2}\leq(n+p)^{2}\), \(s\leq np\leq(n+p)^{2}\) and \(2\leq\omega\). We obtain a complexity in \(O(min((n+p)^{\omega},ps))\) time, i.e., in \(O(min(n^{\omega},ps))\) time, since \(p\leq n\) and therefore in \(O(min(n^{\omega},nm))\) time, since \(s\leq n+m\) by Property 6. It follows that the atom graph can be computed from an atom tree in \(O(min(n^{\omega},nm))\) time. We will now discuss using the 2-pairs of the graph \(G^{+}\) defined in Notation 1 to obtain an alternative complexity in \(O(n(n+\overline{m^{+}}))\) time, where \(\overline{m^{+}}\) is the number of edges of the complement of \(G^{+}\), through the following lemma. Lemma 1: _Let \(T\) be atom tree of a connected graph. Then, \(s_{\triangle}(T)\leq n+t\), where \(t\) is the number of 2-pairs of \(G^{+}\)._  
Proof: We consider a rooted directed tree \(T_{r}=(\mathcal{A}(G),U)\) obtained from \(T\) by choosing an arbitrary root.