# Computing the Atom Graph of a Graph and the Union Join Graph of a Hypergraph
## 4 Computing the Atom Graph
### Algorithm Forest Join
Thus, \(\Sigma_{XY\in E_{T}}|X\triangle Y|=\Sigma_{(X,Y)\in U}|X\triangle Y|\). \(\Sigma_{(X,Y)\in U}|Y\setminus X|\leq n\), since each vertex \(x\) of \(G\) belongs to \(Y\setminus X\) for at most one edge of \(T_{r}\), namely the edge \((X,Y)\), such that \(Y\) is the root of the subtree of \(T_{r}\) induced by the nodes containing \(x\). Hence, it is sufficient to show that \(\Sigma_{(X,Y)\in U}|X\setminus Y|\leq t\). It is shown in [4] that, if \(G\) is chordal, then this sum is bounded by the number of 2-pairs of \(G\). So, it is bounded by \(t\) since \(G^{+}\) is chordal and by Property 4\(T\) is also an atom tree of \(G^{+}\). Theorem 3: _The atom graph of a connected graph \(G\) can be computed from an atom tree \(T\) of \(G\) in \(O(p(n+s_{\triangle}(T)))\) time, and therefore in \(O(n(n+\overline{m^{+}}))\) time, where \(\overline{m^{+}}\) is the number of edges of the complement of \(G^{+}\)._  
Proof: We consider the variant of the algorithm Forest Join, where the subset relation \(sub\) is not given as an input, and \"\(sub(AB,XY)\)\" and \"\(sub(XY,AB)\)\" in the algorithm Components are replaced as follows. Condition \(sub(XY,AB)\) can be replaced by \(|A\cap B|=|X\cap Y|\), since, in the algorithm, \(XY\) satisfies \(sub(AB,XY)\). The values of \(|X\cap Y|\) for each edge \(XY\) of \(T\) can be pre-computed in \(O(np)\) time. Let \(S=A\cap B\). As \(S\) is a subset of \(X\) in the algorithm, and condition \(sub(AB,XY)\) is equivalent to \((X\setminus Y)\cap S=\emptyset\), which can be evaluated in \(O(|X\setminus Y|)\) time, provided that the sets \(X\cap Y\), \(X\setminus Y\) and \(Y\setminus X\) for each edge \(XY\) of \(T\) have been pre-computed, which can be done in \(O(np)\) time. Thus, we add to the time complexity of Algorithm Forest Join in \(O(p^{2})\) a pre-computation time in \(O(np)\) and \(O(s_{\triangle}(T))\) time per call to components. We obtain a time complexity in \(O(p^{2}+np+p*s_{\triangle}(T))\), and therefore in \(O(p(n+s_{\triangle}(T)))\), since \(p-1\leq s_{\triangle}(T)\) (because the nodes of \(T\) are pairwise distinct). We conclude with Lemma 1  
The 2-pairs of a chordal graph are closely related to its atom graph. **Characterization 10**. : _Let \(G\) be a connected chordal graph, and let \(\{x,y\}\) be a pair of vertices of \(G\). Then, \(xy\) is a 2-pair of \(G\) if and only if there is an edge \(KL\) of \(AG(G)\), such that \(x\in K\setminus L\) and \(y\in L\setminus K\)._  
Proof:\(\Rightarrow\): let \(S=N(x)\cap N(y)\). As \(S\) is a minimal separator of \(G\) and \(G\) is chordal, \(S\) is a clique. Let \(K\) (resp. \(L\)) be a maximal clique containing \(\{x\}\cup S\) (resp. \(\{y\}\cup S\)). \(S\subseteq K\cap L\subseteq(N(x)\cup\{x\})\cap(N(y)\cup\{y\})=N(x)\cap N(y)=S\). Hence \(S=K\cap L\), and therefore, \(KL\) is an edge of \(AG(G)\) with \(x\in K\setminus L\) and \(y\in L\setminus K\). \(\Leftarrow\): let \(S=K\cap L\). As \(KL\) is an edge of \(AG(G)\), \(S\) is a minimal \(xy\)-separator. As \(G\) is chordal \(K\) and \(L\) are cliques, so \(S\subseteq N(x)\cap N(y)\), and as \(S\) is an \(xy\)-separator \(N(x)\cap N(y)\subseteq S\). Hence, \(S=N(x)\cap N(y)\), and therefore \(xy\) is a 2-pair of \(G\). It follows that the number of 2-pairs of a connected chordal graph \(G\) is bounded by the sum of the products \(|K\setminus L|*|L\setminus K|\) for each edge \(KL\) of its atom graph. In particular, in a graph class (of non-necessarily chordal graphs) in which the values of \(|A\setminus B|\) (and \(|B\setminus A|\)) for each edge \(AB\) of the atom graph are bounded by a given constant, for instance, if the sizes of the atoms are bounded by a constant, the atom graph can be computed from an atom tree in \(O(n(n+m^{\prime}))\) time, where \(m^{\prime}\) is the number of edges of the computed atom graph. The number of 2-pairs is not equal, in general, to the sum of the products\(|K\setminus L|*|L\setminus K|\) for each edge \(KL\) of its atom graph, since a 2-pair may be associated with several edges of the atom graph.