# Computing the Atom Graph of a Graph and the Union Join Graph of a Hypergraph
## 4 Computing the Atom Graph
### Algorithm AG-Max-Weight
Hence, the algorithm runs in \(O(w_{max}+n^{2})\) time. **Corollary 1**. : _Given the weighted intersection graph of the atoms of a connected graph \(G\), the algorithm AG-max-weight computes the atom graph of \(G\) in \(O(n+p^{2})\) time and therefore in \(O(n^{2})\) time._

To evaluate the time complexity of computing the atom graph of \(G\) from the set of atoms of \(G\) using the algorithm AG-max-weight, we need the time complexity of computing the the weighted intersection graph of the atoms of \(G\). **Proposition 2**. : _Given the set of atoms of a connected graph \(G\), the weighted intersection graph of the atoms of \(G\) can be computed in \(O(min(n^{\omega},ps))\) time and therefore in \(O(min(n^{\omega},nm))\) time._

Proof. : As \(|X\cap Y|\) can be computed in \(O(|Y|)\) time, computing \(|X\cap Y|\) for each pair \(\{X,Y\}\) of atoms of \(G\) is in \(O(ps)\) time. Alternatively, these values can be computed in \(O((n+p)^{\omega})\) time, since they are the elements of the product of the transposition of \(M\) by \(M\), where \(M\) is the \(n\times p\) incidence matrix of the hypergraph \((V,\mathcal{A}(G))\) (which will be called the atom hypergraph of \(G\) in Section 5), i.e., in \(O(n^{\omega})\) time since \(p\leq n\). We obtain a time complexity in \(O(min(n^{\omega},ps))\) and therefore in \(O(min(n^{\omega},nm))\), since \(s\leq n+m\) by Property 6. It follows that the atom graph can be computed from the set of atoms in \(O(min(n^{\omega},nm))\) time. ## 5 Atom Hypergraph

In this section, we define the atom hypergraph of a graph and relate it to the more general notion of \(\alpha\)-acyclic hypergraph. Figure 4: An execution of the algorithm AG-max-weight (the edge labels that are equal to \(1\) are omitted). **Definition 5**. : _Let \(G=(V,E)\) be a graph. The atom hypergraph of \(G\) is the hypergraph \(H_{A}(G)=(V,\mathcal{A}(G))\)._

Thus, the atom trees of a connected graph are the join trees of its atom hypergraph. We recall that, for each hypergraph \(H\), \(2 SEC(H)\) is the graph whose vertex set is the vertex set of \(H\) and whose edges are the pairs of vertices that are contained in a hyperedge of \(H\)

**Characterization 11**. : _An hypergraph is the atom hypergraph of a connected graph if and only if it is a connected \(\alpha\)-acyclic clutter, and in that case, it is the atom hypergraph of the graph \(2 SEC(H)\), which is a connected chordal graph._

Proof. : The atom hypergraph of a connected graph \(G\) is connected (since \(G\) is and each edge of \(G\) is contained in an atom of \(G\)), \(\alpha\)-acyclic (since \(G\) has an atom tree) and a clutter (by definition of atoms). Conversely, if \(H\) is a connected \(\alpha\)-acyclic clutter, then by Property 8, it is the atom hypergraph of the graph \(2 SEC(H)\), which is chordal, and which is connected, since \(H\) is. Note that, if \(H\) is the atom hypergraph of \(G\), then \(2 SEC(H)\) is the graph \(G^{+}\) defined in Notation 1. Thus, we refind that \(G^{+}\) is chordal and has the same atoms as \(G\) (Property 3). **Definition 6**. : _The union join graph of an \(\alpha\)-acyclic hypergraph \(H\), denoted by \(UJ(H)\), is the union of its join trees._

As the atom graph of a connected graph \(G\) is the union of its atom trees by Characterizations 6, we have the following property. **Property 10**. : _The atom graph of a connected graph is the union join graph of its atom hypergraph._

As a generalization of Characterizations 8, the union join graph of an \(\alpha\)-acyclic hypergraph \(H\) can be computed from a join tree of \(H\) by the following operation \(tuj\), where \(tuj\) stands for \"to union join\". **Definition 7**. : _For each join tree \(T=(\mathcal{E},E_{T})\) of a hypergraph, \(tuj(T)\) is the graph whose node set is \(\mathcal{E}\) and whose edges are the pairs \(\{X,Y\}\) of \(\mathcal{E}\), such that there is an edge \(X^{\prime}Y^{\prime}\) of \(P_{T}(X,Y)\), such that \(X\cap Y=X^{\prime}\cap Y^{\prime}\) (or equivalently \(X^{\prime}\cap Y^{\prime}\subseteq X\cap Y\))._

**Characterization 12**.