# Computing the Atom Graph of a Graph and the Union Join Graph of a Hypergraph
## 4 Computing the Atom Graph
### Algorithm AG-Max-Weight
Thus, we can deduce from properties of \(\alpha\)-acyclic hypergraphs (proved from the definition of \(\alpha\)-acyclicity) properties of atom graphs, and conversely, we can deduce from properties of atom graphs (proved from properties of the minimal separators of the underlying graph) properties of general \(\alpha\)-acyclic hypergraphs. This double approach helps to increase knowledge in both domains of atom graphs and \(\alpha\)-acyclic hypergraphs, as some properties are easier to see in one of these domains than in the other one. Let us consider the case of a disconnected \(\alpha\)-acyclic hypergraph \(H\). A join tree of \(H\) is obtained from the disjoint union of join trees of its connected components by adding \"empty edges\", i.e., edges associated with the empty set, to make it into a tree, and the union join graph of \(H\) is obtained from the disjoint union of the union join graphs of its connected components by adding all edges (which are empty edges) between these union join graphs. Alternatively, if we omit the empty edges, a join tree becomes a forest called _join forest_ in [27], whose connected components are the join trees of its connected components, and the union join graph becomes the union of its join forests, whose connected components are the union join graphs of its connected components. These two alternatives also exist in the graph and minimal separator approach, which correspond to two different definitions of separators in a disconnected graph. According to the definition of separators given in this paper, as the empty set is not a separator and the edges of an atom tree represent the minimal separators, an atom tree naturally extends to an atom forest of a (not necessarily connected) graph, which is the join forest of its atom hypergraph, and its atom graph (Definition 3) is the union of these join forests. According to an alternative definition of separators, which is given, for instance, in [2], a set \(S\) is an \(ab\)-separator of \(G\) if \(a\) and \(b\) are in different connected components of \(G(V\setminus S)\), whether \(G\) is connected or not. It follows that the empty set is the unique minimal \(ab\)-separator of \(G\) if \(a\) and \(b\) are in different connected components of \(G\). Thus, according to this alternative definition, an atom tree of a (not necessarily connected) graph is a join tree of its atom hypergraph and its atom graph (Definition 3 again) is the union join graph of its atom hypergraph. In both alternatives, the results for a connected graph naturally extend to a (non necessarily connected) graph using the appropriate definition of separators, as well as to (not necessarily connected) \(\alpha\)-acyclic hypergraphs, as will be seen in Section 6. ## 6 Computing the Union Join Graph

Algorithms and complexity results of Section 4 extend to the computation of the union join graph of an \(\alpha\)-acyclic hypergraph. They immediately extend to a connected \(\alpha\)-acyclic clutter \(H\), since, in that case, \(H\) is the atom hypergraph of \(2 SEC(H)\) by Characterization 11. The algorithms still hold for any \(\alpha\)-acyclic hypergraph, since the proofs of their correctnessdo. It is also the case for the complexity bounds in function of parameters \(n\), \(p\), \(s\), and \(s_{\triangle}(T)\), whose definitions naturally extend to \(\alpha\)-acyclic hypergraphs as follows. **Notation 4**. : _For each \(\alpha\)-acyclic hypergraph \(H=(V,\mathcal{E})\), \(n=|V|\), \(m\) is the number of edges of \(2 SEC(H)\), \(\overline{m}\) is the number of edges of its complement, \(p=|\mathcal{E}|\), \(s=\Sigma_{X\in\mathcal{E}}|X|\), and for each join tree \(T=(\mathcal{E},E_{T})\) of \(H\)\(s_{\triangle}(T)=\Sigma_{XY\in E_{T}}|X\triangle Y|\)._

We recall that \(\omega\) is a real number, such that \(O(n^{\omega})\) is the best known time complexity of matrix multiplication. The subset relation of a join tree is defined as that of an atom tree (see Definition 4). **Theorem 5**.