# Computing the Atom Graph of a Graph and the Union Join Graph of a Hypergraph
## 1 Introduction  
Decomposition by clique minimal separators (into subgraphs called _atoms_) was introduced by [PERSON] [1] in 1985 as a useful hole- and antihole-preserving decomposition. It turns out that this decomposition is unique when clique _minimal_ separators are used [2]. This decomposition has given rise to recent interest, both in the general case [3; 4; 5; 2] and for special graph classes [6; 7; 8; 9; 10; 11]. Applications have arisen in the fields of databases [12], text mining [13], and biology [14; 15]. [PERSON] et al. [4] introduced the concept of _atom tree_, which organizes the atoms of the clique minimal separator decomposition into a tree as a generalization of the clique tree for chordal graphs: the nodes are the atoms, and the edges correspond to the clique minimal separators of the graph. However, as is the case for the clique tree, the atom tree is not uniquely defined. This can be a problem, for instance, with the promising use of an atom tree as a visualization tool. In this paper, we focus on the _atom graph_, whose vertices are the atoms and whose edges are those of all possible atom trees. The notion of atom graph was introduced in 2007 in [15], in the context of visualizing biological clusters. An efficient construction algorithm was proposed in 2010 in [16]. In the case of chordal graphs, atoms are the maximal cliques, and atom trees are clique trees. A related graph that has been extensively studied in this context is the _clique graph_ (see, e.g., [17; 18]), which is the intersection graph of the maximal cliques. The _weighted clique graph_ of a chordal graph has been used to construct a clique tree of this graph [19; 20], its clique trees being the maximum weight spanning trees of its weighted clique graph. Thus, the atom graph of a chordal graph is a subgraph of its clique graph. In the context of efficiently constructing a clique tree, in 1991, [PERSON] and [PERSON] [19] studied the familyof all possible clique trees, an object very close to the atom graph of a chordal graph. In 1995, [PERSON] et al. [21] used the weighted atom graph of a chordal graph but misguidedly called this object the 'clique graph'. In 2012 in [22], this object is further studied and called the'reduced clique graph'. Our first goal in this paper is to propose efficient algorithms to compute the atom graph, both in the general case and in the case of chordal graphs. Given a graph, all known algorithms for computing the decomposition into atoms first compute a minimal triangulation of the graph [2; 3; 4], with the exception of some special graph classes [6; 7]. A minimal triangulation can be computed in \(O(min(n^{\omega}\log n,nm,n(n+\overline{m})))\) time, where \(n\) is the number of vertices of \(G\), \(m\) is the number of its edges, \(\overline{m}\) is the number of edges of the complement of \(G\), and \(\omega\), also denoted by \(\alpha\) in the literature, is a real number such that \(O(n^{\omega})\) is the best known time complexity for matrix multiplication, whose current value is 2,3728596 [4; 23; 24]. From this minimal triangulation, an atom tree can be computed in \(O(min(n^{\omega},nm,n(n+t)))\) time [2; 4; 5], where \(t\) is the number of two pairs of the minimal triangulation, and thus \(t\leq\overline{m}\). As a result, an atom tree can be computed in \(O(min(n^{\omega}\log n,nm,n(n+\overline{m})))\) time. To compute the atom graph efficiently, we present two different approaches. One takes as input an atom tree as well as the inclusion relation between the separators represented by its edges, and the other takes as input the weighted intersection graph of the atoms. In both cases, we provide an \(O(n^{2})\) algorithm to compute the atom graph from the input. Our global complexity when taking the graph itself as input comes to \(O(min(n^{\omega}\log n,nm,n(n+\overline{m})))\) time.