# Computing the Atom Graph of a Graph and the Union Join Graph of a Hypergraph
## 2 Preliminaries  
The graphs considered in this paper are finite and undirected. For a graph \(G=(V,E)\), \(n=|V|\) and \(m=|E|\). For any subset \(X\) of \(V\), \(G(X)\) denotes the subgraph of \(G\) induced by \(X\). For any vertex \(v\) of \(G\), \(N_{G}(v)\) denotes the neighborhood of \(v\) in \(G\): \(N_{G}(v)=\{w\in V\mid ww\in E\}\). For any subset \(X\) of \(V\), \(N_{G}(X)\) denotes the neighborhood of \(X\) in \(G\): \(N_{G}(X)=(\cup_{v\in X}N_{G}(v))\setminus X\). We will omit the subscripts when there is no ambiguity. A _clique_ of \(G\) is a set of pairwise adjacent vertices of \(G\), and \(G\) is _complete_ if \(V\) is a clique of \(G\). The _union of two graphs_\(G_{1}=(V,E_{1})\) and \(G_{2}=(V,E_{2})\) is the graph \(G_{1}\cup G_{2}=(V,E_{1}\cup E_{2})\). \(\overline{G}\) denotes the _complement_ of \(G\), and \(\overline{m}\) denotes the number of its edges. \(\omega\) is a real number, such that \(O(n^{\omega})\) is the best known time complexity for matrix multiplication. For any set \(V\), \(\mathcal{P}(V)\) is the power set of \(V\). For any subset \(\mathcal{A}\) of \(\mathcal{P}(V)\), the _intersection graph_ of \(\mathcal{A}\) is the graph \((\mathcal{A},E)\), where \(E\) is the set of pairs of \(\mathcal{A}\) whose intersection is non-empty. For each graph \(G\), \(\mathcal{K}(G)\) denotes the set of maximal cliques of \(G\), and the _clique graph_ of \(G\) is the intersection graph of \(\mathcal{K}(G)\). If \(X\) and \(Y\) are nodes of a tree \(T\), \(P_{T}(X,Y)\) denotes the path in \(T\) between \(X\) and \(Y\). _Separation._ Let \(S\) be a subset of vertices of a connected graph \(G=(V,E)\). \(S\) is a _separator_ of \(G\) if \(G(V\setminus S)\) is disconnected. For any vertices \(a\) and \(b\) in \(V\setminus S\), \(S\) is an _ab-separator_ of \(G\) if \(a\) and \(b\) are in different connected components of \(G(V\setminus S)\). \(S\) is a _minimal ab-separator_ if it is an inclusion-minimal _ab-separator_, and a _minimal separator_ if there is some pair \(\{a,b\}\)of vertices, such that \(S\) is a minimal \(ab\)-separator. Given a minimal separator \(S\), \(C\) is a _full component_ of \(S\) if \(C\) is a connected component of \(G(V\setminus S)\) and \(N_{G}(C)=S\). \(S\) is a minimal separator if and only if \(S\) has at least 2 full components, and \(S\) is a minimal ab-separator if and only if \(a\) and \(b\) lie in 2 different full components of \(S\). Given three subsets \(S\), \(A\), and \(B\) of \(V\), \(S\) is a (minimal) \(AB\)-separator of \(G\) if it is a (minimal) \(ab\)-separator of \(G\) for each \(a\in A\) and each \(b\in B\). A _2-pair_ of a connected graph \(G\) is a pair \(\{x,y\}\) of non-adjacent vertices such that every chordless path between \(x\) and \(y\) is of length 2, i.e., every sequence of consecutively-adjacent vertices with \(x\) and \(y\) as endpoints and being minimal for these properties according to the relation of subsequence has 3 vertices, or equivalently, such that \(N(x)\cap N(y)\) is a minimal \(xy\)-separator of \(G\). The number of 2-pairs of a graph is denoted \(t\), with \(t\leq\overline{m}\). If \(G\) is disconnected, then a (minimal) (\(ab\)-)separator of \(G\) is a (minimal) (\(ab\)-)separator of one of its connected components. Thus, the set of minimal separators of a graph is the union of the sets of minimal separators of its connected components, and so it is for its set of 2-pairs. _Chordal graphs._ A graph is _chordal_ or _triangulated_ if it has no chordless cycle of length at least 4. A graph is chordal if and only if all its minimal separators are cliques [25]. A chordal graph has at most \(n\) maximal cliques, and the sum of their sizes is bounded by \(n+m\). A connected graph is chordal if and only if it has a _clique tree_[20; 26]. Definition 1: Let \(G=(V,E)\) be a connected chordal graph. A _clique tree_ of \(G\) is a tree \(T=(\mathcal{K}(G),E_{T})\), such that, for each vertex \(x\) of \(G\), the set \(\mathcal{K}_{x}\) of nodes of \(T\) containing \(x\) induces a subtree of \(T\).