# Computing the Atom Graph of a Graph and the Union Join Graph of a Hypergraph
## 2 Preliminaries
Characterization 1 ([19]): Let \(G=(V,E)\) be a connected chordal graph, let \(T\) be a clique tree of \(G\), and let \(S\subseteq V\); then, \(S\) is a minimal separator of \(G\) if and only if there is an edge \(XY\) of \(T\), such that \(S=X\cap Y\). If \(G\) is a disconnected chordal graph, we associate with \(G\) a forest whose connected components are clique trees of the connected components of \(G\). A clique tree (forest) can be computed in linear time [19]. _Atoms._ Atoms are the subgraphs obtained by applying the decomposition by clique minimal separators (see [3] for a survey). Characterization 2 ([2]): An atom of a graph \(G=(V,E)\) is an inclusion-maximal subset of \(V\) inducing a connected subgraph of \(G\) with no clique separator. We will denote the set of atoms of \(G\) by \(\mathcal{A}(G)\). Property 1: The atoms of a chordal graph are its maximal cliques. Property 2 ([2]): The intersection of two distinct atoms is a clique. Notation 1: For a graph \(G=(V,E)\), \(G^{+}\) denotes the graph whose vertex set is \(V\) and whose edges are the pairs of \(V\) that are contained in a common atom of \(G\) (this graph is denoted \(G^{*}\) in [2]). Property 3 ([2]): For a graph \(G\), \(G^{+}\) is chordal, its maximal cliques are the atoms of \(G\), and for each clique \(S\) of \(G\) and each pair \(\{a,b\}\) of \(V\setminus S\), \(S\) is a minimal ab-separator of \(G\) if and only if \(S\) is a minimal ab-separator of \(G^{+}\). It follows that a graph has at most \(n\) atoms. _Atom trees._ To represent the atoms of a graph, [4] extend the notion of clique tree of a connected chordal graph to the notion of _atom tree_ of a connected graph:  
**Definition 2** ([4]). : _Let \(G=(V,E)\) be a connected graph. An atom tree of \(G\) is a tree \(T=(\mathcal{A}(G),E_{T})\), such that, for each vertex \(x\) of \(G\), the set \(\mathcal{A}_{x}\) of nodes of \(T\) containing \(x\) induces a subtree of \(T\)._  
Note that an atom tree is not a decomposition tree of clique separator decomposition as defined in [1; 16], though this decomposition is called 'atom tree' in [16]. An atom tree of a connected graph \(G\) can be computed in \(O(min(n^{\omega}\log n,nm,n(n+\overline{m})))\) time [4; 5]. As for clique trees of chordal graphs, we can extend the definition of an atom tree to the definition of an \"atom forest\" of an arbitrary graph \(G\), whose connected components are atom trees of the connected components of \(G\). The edges of an atom tree (forest) of a graph correspond to its clique minimal separators. **Characterization 3** ([4]). : _Let \(G=(V,E)\) be a connected graph, let \(T\) be an atom tree of \(G\), and let \(S\subseteq V\); then \(S\) is a clique minimal separator of \(G\) if and only if there is an edge \(AB\) of \(T\), such that \(S=A\cap B\)._  
**Property 4**. : _For a connected graph \(G\), the atom trees of \(G\) are the clique trees of the chordal graph \(G^{+}\) (\(G^{+}\) is defined in Notation 1)._  
**Example 1**. : _Figure 1 shows a graph \(G\) and two of its atom trees. The atoms of \(G\) are \(A=\{1,2,3,4,5,6\}\), \(B=\{1,2,3,7\}\), \(C=\{1,7,8\}\), \(D=\{1,9\}\), \(E=\{1,10,11\}\), and \(F=\{10,11,12,13\}\). Denoting by \(\mathcal{A}_{x}\) the set of atoms containing \(x\) for each vertex \(x\) of \(G\), the sets \(\mathcal{A}_{x}\) containing at least \(2\) atoms are \(\mathcal{A}_{1}=\mathcal{A}(G)\setminus\{F\}\), \(\mathcal{A}_{2}=\mathcal{A}_{3}=\{A,B\}\), \(\mathcal{A}_{7}=\{B,C\}\), \(\mathcal{A}_{10}=\mathcal{A}_{11}=\{E,F\}\). Thus, \(G\) has \(15\) atom trees, which are all the trees obtained from the forest \((\mathcal{A}(G),\{AB,BC,EF\})\) by adding \(2\) edges not containing the node \(F\) (\(6\) containing the edge \(DE\), as the atom tree shown on the left, and \(9\) not containing it, as the atom tree shown on the right). Each edge \(XY\) of each atom tree is labeled with the associated clique minimal separator \(X\cap Y\) of \(G\)._  
Figure 1: A graph \(G\) and two atom trees of \(G\). The following properties will be used to compute complexity bounds. **Property 5**.