# Computing the Atom Graph of a Graph and the Union Join Graph of a Hypergraph
## 2 Preliminaries
: _Let \(A\) and \(B\) be distinct atoms of a graph \(G\). Then, \(G(A\setminus B)\) is connected and \(A\cap B\subseteq N_{G}(A\setminus B)\)._  
Proof. : By Property 2, \(A\cap B\) is a clique of \(G\). \(A\setminus B\) is connected since otherwise \(A\cap B\) would be a clique separator of \(G(A)\). Similarly, \(A\cap B\subseteq N_{G}(A\setminus B)\), since otherwise, \(A\cap N_{G}(A\setminus B)\) would be a clique \(ab\)-separator of \(G(A)\) for any \(a\) in \(A\setminus B\) (which is non-empty by definition of atoms) and any \(b\) in \((A\cap B)\setminus N_{G}(A\setminus B)\). **Property 6**. : _The sum of the sizes of the atoms of a graph is bounded by \(n+m\)._  
Proof. : It is sufficient to prove it in the case of a connected graph \(G\). Let \(T\) be an atom tree of \(G\), and let us show by induction on \(|\mathcal{A}|\) that, for each connected subset \(\mathcal{A}\) of nodes of \(T\), \(\Sigma_{X\in\mathcal{A}}|X|\leq n_{\mathcal{A}}+m_{\mathcal{A}}\), where \(n\mathcal{A}\) and \(m\mathcal{A}\) are the numbers of vertices and edges of the subgraph of \(G\) induced by \(V_{\mathcal{A}}=\cup_{X\in\mathcal{A}}X\). It trivially holds if \(|\mathcal{A}|=1\). We assume that it holds if \(|\mathcal{A}|=k\). Let us show that it holds if \(|\mathcal{A}|=k+1\). Let \(X_{1}\) be a leaf of \(T(\mathcal{A})\), let \(X_{2}\) be the neighbor of \(X_{1}\) in \(T(\mathcal{A})\), let \(S=X_{1}\cap X_{2}\), and let \(\mathcal{A}_{2}=\mathcal{A}\setminus\{X_{1}\}\). By induction, hypothesis \(\Sigma_{X\in\mathcal{A}_{2}}|X|\leq n_{\mathcal{A}_{2}}+m_{\mathcal{A}_{2}}\). As \(T\) is an atom tree of \(G\), \(V_{\mathcal{A}}\) is the disjoint union of \(X_{1}\setminus S\) and \(V_{\mathcal{A}_{2}}\), so \(n_{\mathcal{A}}=|X_{1}\setminus S|+n_{\mathcal{A}_{2}}\). By Property 5, \(S\subseteq N_{G}(X_{1}\setminus S)\), so \(m_{\mathcal{A}}\geq|S|+m_{\mathcal{A}_{2}}\). It follows that \(\Sigma_{X\in\mathcal{A}}|X|=|X_{1}|+\Sigma_{X\in\mathcal{A}_{2}}|X|\leq(|X_{ 1}\setminus S|+|S|)+(n_{\mathcal{A}_{2}}+m_{\mathcal{A}_{2}})=(|X_{1}\setminus S |+n_{\mathcal{A}_{2}})+(|S|+m_{\mathcal{A}_{2}})\leq n_{\mathcal{A}}+m_{ \mathcal{A}}\). **Property 7**. : _The sum of the sizes of the sets \(X\cap Y\) for each edge \(XY\) of an atom tree \(T\) of a connected graph is bounded by \(n+m\), and these sets can be computed from \(T\) in \(O(m)\) time._  
Proof. : Let \(T=(\mathcal{A}(G),E_{T})\) be an atom tree of \(G\). We consider a rooted directed tree \(T_{r}=(\mathcal{A}(G),U)\) obtained from \(T\) by choosing an arbitrary root. Thus, \(\Sigma_{XY\in E_{T}}|X\cap Y|=\Sigma_{(X,Y)\in U}|X\cap Y|\leq\Sigma_{(X,Y) \in U}|Y|\leq\Sigma_{Y\in\mathcal{A}(G)}|Y|\leq n+m\) by Property 6. These sets can be computed by searching \(T\) and computing \(X\cap Y\) in \(O(|Y|)\) time when reaching \(Y\) from its neighbor \(X\), and therefore in \(O(m)\) time.by Property 6. \(\alpha\)_-acyclic hypergraphs._ A _simple hypergraph_, or _hypergraph_ for short, is a structure \(H=(V,\mathcal{E})\), where \(V\) is its vertex set and \(\mathcal{E}\) is a set of non-empty subsets of \(V\), called the _hyperedges_ of \(H\), whose union is equal to \(V\). A hypergraph is a _clutter_ if the elements of \(\mathcal{E}\) are pairwise non-inclusive. Its _line graph_, denoted by \(L(H)\), is the intersection graph of \(\mathcal{E}\). Its _2-section graph_, denoted by \(2 SEC(H)\), is the graph whose vertex set is \(V\) and whose edges are the pairs of \(V\) that are contained in a hyperedge of \(H\). \(H\) is _connected_ if \(L(H)\) is connected, or equivalently, if \(2 SEC(H)\) is connected. We denote by \(p\) the number of hyperedges of a hypergraph. Let \((v_{1},\ldots,v_{n})\) be an ordering of \(V\), and let \((X_{1},\ldots,X_{p})\) be an ordering of \(\mathcal{E}\). The _incidence matrix_ of \(H\) w.r.t. these orderings is the \(n\times p\) matrix \(M=(m_{i,j})\), such that, for each \(i\in[1,n]\) and each \(j\in[1,p]\), \(m_{i,j}=1\) if \(v_{i}\in X_{j}\) and 0 otherwise.