# Computing the Atom Graph of a Graph and the Union Join Graph of a Hypergraph
## 4 Computing the Atom Graph  
We know that, given a connected graph \(G\), an atom tree of \(G\) (and therefore the atoms of \(G\)) can be computed in linear time if \(G\) is chordal and in \(O(min(n^{\omega}\log n,nm,n(n+\overline{m})))\) time otherwise. To compute the set of edges of the atom graph of \(G\), a naive algorithm consists of computing for each pair \(\{A,B\}\) of atoms of \(G\) the connected components of \(G(V\setminus(A\cap B))\) and determining whether \(A\setminus B\) and \(B\setminus A\) are in different components, which can be performed in \(O(m)\) time for each pair \(\{A,B\}\) and therefore in \(O(n^{2}m)\) time globally. We will improve upon this to obtain a time that is no worse than that of computing an atom tree. Our first algorithm starts with an atom tree and the inclusion relation between the separators represented by the edges, and adds all the extra edges required to construct the atom graph. Our second algorithm starts with the weighted intersection graph of the atoms and repeatedly determines the edges of weight \(k\), which belong to the atom graph in decreasing order of \(k\). Both algorithms run in \(O(n^{2})\) time given these inputs. When only the graph is given as input, we obtain a complexity of \(O(min(n^{\omega}\log n,nm,n(n+\overline{m})))\) time, as will be detailed in this section. We introduce the following parameters, which will be used in this section and in Section 6: \(p\) denotes the number of atoms of \(G\), \(s\) the sum of their sizes, and for each atom tree \(T\) of \(G\), \(s_{\triangle}(T)\) denotes the sum of the sizes of the symmetrical differences \(X\triangle Y=(X\setminus Y)\cup(Y\setminus X)\) for each edge \(XY\) of \(T\). **Notation 2**: _For each connected graph \(G\), \(p=|\mathcal{A}(G)|\), \(s=\Sigma_{X\in\mathcal{A}(G)}|X|\), and for each atom tree, \(T=(\mathcal{A}(G),E_{T})\) of \(G\)\(s_{\triangle}(T)=\Sigma_{XY\in E_{T}}|X\triangle Y|\)._  
Note that \(p\leq n\) since \(G\) has at most \(n\) atoms, and that \(s\leq n+m\) since the sum of the sizes of the atoms of \(G\) is bounded by \(n+m\) by Property 6. The parameters \(p\), \(s\), and \(s_{\triangle}(T)\) are introduced for two reasons. First, they will be used to extend the complexity results of this section to the context of \(\alpha\)-acyclic hypergraphs in Section 6 with appropriate extensions of the definitions of these parameters. Second, it can lead to a better complexity for graph classes for which these parameters have specific bounds. As will be detailed in Section 4.1, we will also need the inclusion relation \(sub\) on the minimal separators represented by the edges of an atom tree. **Definition 4**. : _Let \(T\) be an atom tree of a connected graph. We call subset relation of \(T\) the relation sub in the set \(E_{T}\) of edges of \(T\) defined by : \(\forall\,XY,X^{\prime}Y^{\prime}\in E_{T}\,sub(XY,X^{\prime}Y^{\prime})\Leftrightarrow X \cap Y\subseteq X^{\prime}\cap Y^{\prime}\)._  
We will show in Sections 4.1 and 4.2 the following complexity result:  
**Theorem 1**. : _The atom graph of a connected graph \(G\) can be computed : (a) in \(O(n^{2})\) time from either an atom tree of \(G\) and its subset relation or the weighted intersection graph of the atoms of \(G\), (b) in \(O(min(n^{\omega},nm,n(n+\overline{m^{+}})))\) time from an atom tree of \(G\), (c) in \(O(min(n^{\omega},nm))\) time from the set of atoms of \(G\), (d) in \(O(min(n^{\omega}\log n,nm,n(n+\overline{m})))\) time from \(G\), where \(m^{+}\) denotes the number of edges of \(\overline{G^{+}}\) (\(G^{+}\) is defined in Notation 1)._  
For a chordal graph \(H\), the atom graph can thus be computed in \(O(min(n^{\omega},nm,n(n+\overline{m})))\) time, since, in that case, \(G^{+}=G\), and an atom tree (clique tree) of \(G\) can be computed in linear time. Other approaches are possible but with no improvement of the time complexity.