Vertical decomposition of a lattice using clique separators Anne Berry, Romain Pogorelcnik, Alain Sigayret LIMOS UMR CNRS 6158?? Ensemble Scientifique des Cézeaux Université Blaise Pascal, F-63 173 Aubière, France. berry@isima.fr, romain.pogorelcnik@isima.fr, sigayret@isima.fr Abstract. A concept (or Galois) lattice is built on a binary relation; this relation can be represented by a bipartite graph. We explain how we can use the graph tool of clique minimal separator decomposition to decom- pose some bipartite graphs into subgraphs in linear time; each subgraph corresponds to a subrelation. We show that the lattices of these subrela- tions easily yield the lattice of the global relation. We also illustrate how this decomposition is a tool to help displaying the lattice. Keywords: lattice decomposition, clique separator decomposition, lat- tice drawing 1 Introduction In many algorithms dealing with hard problems, a divide-and-conquer approach is helpful in practical applications. Computing the set of concepts associated with a given context (or the set of maximal rectangles associated with a binary relation) is time-consuming, as there may be an exponential number of concepts. It would be interesting to decompose the lattice into smaller sublattices. What we propose here is to decompose the relation into smaller subrelations, compute the lattice of each subrelation, and then use these lattices to reconstruct the lattice of the global relation. For this, we use a graph decomposition, called ”clique separator decomposi- tion”, introduced by Tarjan [9], and refined afterwards (see [3] for an extensive introduction to this decomposition). The general principal is roughly the follow- ing: repeatedly find a set of vertices which are pairwise adjacent (called a clique) and whose removal disconnects the graph (called a separator), then copy this clique separator into the different connected components obtained. When the de- composition is completed, a set of subgraphs is obtained, inconveniently called ’atoms’: each subgraph is a maximal subgraph containing no clique separator. ?? Research partially supported by the French Agency for Research under the DEFIS program TODO, ANR-09-EMER-010. In a previous work [2], we used graph algorithms on the complement of the bipartite graph associated with the relation. In this paper, we will apply this decomposition directly to the bipartite graph itself. It turns out upon investigation that the subgraphs obtained divide not only the graph, but in a very similar fashion divide the matrix of the relation, the set of concepts and the lattice. When the relation has a clique separator of size two, the lattice, as we will explain further on, is divided along a vertical axis by an atom and a co-atom which correspond to the two vertices of the separator. Thus not only can the concepts be computed on the subrelations, but the Hasse diagram of the lattice can be drawn better, as no edge need cross this vertical line. Moreover, in a bipartite graph, this decomposition can be implemented with a better worse-case time complexity than in the general case, as the clique sep- arators can be of size one (in this case they are called articulation points) or of size two. In both cases, the entire decomposition can be computed in linear time, i.e. in the size of the relation, thanks to the works of [6] and [3]. Although some graphs do not have a clique separator, when there is one, the decomposition is thus a useful and non-expensive pre-processing step. The paper is organized as follows: we will first give some more preliminaries in Section 2. In Section 3, we explain how a bipartite graph is decomposed. In Section 4, we show how to reconstruct the global lattice from the concepts ob- tained on the subrelations. In Section 5, we discuss using vertical decomposition as a tool for layout help. Finally, in Section 6, we conclude with some general remarks. 2 Preliminaries We will first recall essential definitions and properties. All the graphs will be undirected and finite. For a graph G = (V, E), V is the vertex set and E is the edge set. For xy ∈ E, x 6= y, x and y are said to be adjacent; we say that x sees y. A graph is connected if, for every pair {x, y} of vertices, there is a path from x to y. When a graph is not connected, the maximal connected subgraphs are called the connected components. For C ⊂ V , G(C) denotes the subgraph induced by C. In a graph G = (V, E), the neighborhood of a vertex x ∈ V is the set NG (x) = {y ∈ V, x 6= y|xy ∈ E}. NG (x) is denoted N (x) when there is no ambiguity. A clique is set of vertices which induces a complete graph, i.e. with all possible edges. A bipartite graph G = (X + Y, E), where + stands for disjoint union, is built on two vertex sets, X and Y , with no edge between vertices of X and no edge between vertices of Y . A maximal biclique of a bipartite graph G = (X + Y, E) is a subgraph G(X 0 + Y 0 ) with all possible edges between the vertices of X 0 and the vertices of Y 0 . A relation R ⊆ O × A on a set O of objects and a set A of attributes is associated with a bipartite graph G=(O + A, E), which we will denote Bip(R); thus, for x ∈ O and y ∈ A, (x, y) is in R iff xy is an edge of G. The maximal rectangles of the relation correspond exactly to the maximal bicliques (maximal complete bipartite subgraphs) of Bip(R) and to the elements (the concepts) of concept lattice L(R) associated with context (O, A, R). If O1 × A1 and O2 × A2 are concepts of L(R) then O1 × A1  O2 × A2 iff O1 ⊆ O2 iff A1 ⊇ A2 ; the corresponding bicliques on vertex sets O1 + A1 and O2 + A2 of Bip(R) are comparable the same way. An atom (resp. co-atom) of L(R) is a concept covering the minimum element (resp. covered by the maximum element). In the bipartite graph Bip(R), the neighborhoods are defined as follows: for x ∈ O, N (x) = R(x) = {y ∈ A|(x, y) ∈ R}, and for x ∈ A, N (x) = R−1 (x) = {y ∈ O|(y, x) ∈ R}. A separator in a connected graph is a set of vertices, the removal of which disconnects the graph. A clique separator is a separator which is a clique. Clique separator decomposition [9] of a graph G = (V, E) is a process which repeat- edly finds a clique separator S and copies it into the connected components of G(V − S). When only minimal separators are used (see [3] for extensive general definitions), the decomposition is unique and the subgraphs obtained in the end are exactly the maximal subgraphs containing no clique separator [8], [3]. In a bipartite graph, the clique minimal separators are of size one or two. A separator of size one is called a articulation point. A clique separator S = {x, y} of size two is minimal if there are two components C1 and C2 of G(V − S) such that x and y both have at least one neighbor in C1 as well as in C2 . 3 Decomposing the bipartite graph and the relation In the rest of the paper, we will use the bipartite graph Bip(R) defined by a rela- tion R ⊆ O × A. Figure 1 shows an example of a relation with the corresponding bipartite graph. Fig. 1. A relation and the corresponding bipartite graph In this section, we will first discuss connectivity issues, then illustrate and give our process to decompose the bipartite graph. 3.1 Decomposing the bipartite graph into connected components When the bipartite graph Bip(R) is not connected, our process can be applied separately (or in parallel) to each connected component. The lattice obtained is characteristic: when the top and bottom elements are removed from the Hasse diagram, the resulting diagram is a set of disjoint lattices, with a one-to-one correspondence between the connected components of Bip(R) and the lattices obtained. Figure 2 shows such a disconnected bipartite graph, its relation, and the corresponding lattice. Note that trivially, if a connected component has only one vertex, this means that the corresponding row or column of the relation is empty: such a component corresponds to a lattice with only one element. In the rest of the paper, we will consider only relations whose bipartite graph is connected. Fig. 2. A disconnected bipartite graph, its relation, and the corresponding character- istic lattice. 3.2 Illustrating the two decomposition steps In order to make the process we use as clear as possible, we will first describe what happens when one decomposition step is applied for each of the two de- compositions involved (using clique separators of size one or of size two). It is important to understand, however, that to ensure a good (linear) time complexity, each of the two decompositions is computed globally in a single linear-time pass. Step with an articulation point The removal of an articulation point {x} in a connected bipartite graph G results in components C1 , ..., Ck , which correspond to a partition V = C1 + ... + Ck + {x} of Bip(R). After a decomposition step using {x}, x is preserved, with its local neighborhood, in each component, so that G is replaced by k subgraphs G(C1 ∪ {x}), ..., G(Ck ∪ {x}). Example 1. In the input graph of Figure 3, vertex 1 defines an articulation point that induces two connected components {2, 3, a, b, c} and {4, d, e}. The decom- position step results into subgraphs G({1, 2, 3, a, b, c}) and G({1, 4, d, e}). Fig. 3. Decomposition by articulation point {1}. Step with a separator of size two When the removal of a clique minimal separator {x, y} in a connected bi- partite graph G results into components C1 ,..., Ck , corresponding to a partition V = C1 +...+Ck +{x, y}. The decomposition step replaces G with G(C1 ∪{x, y}), ..., G(Ck ∪ {x, y}). Example 2. In the input graph of Figure 4, {2, b} is a clique minimal separa- tor of size two that induces two connected components {1, 2, 3, a, b, c, f } and {2, 5, 6, b, g, h}. Fig. 4. Decomposition by clique separator {2,b} 3.3 Ordering the steps A clique minimal separator of size two may include an articulation point. Thus it is important to complete the decomposition by the articulation points first, and then go on to decompose the obtained subgraphs using their clique separators of size two. Example 3. In the input graph of Figure 5, {2} is an articulation point included in clique minimal separator {2, b}. The decomposition will begin with {2}, in- ducing components {2, i} and {1, 2, 3, 5, 6, a, b, c, f, g, h}. As there remains no articulation point in these resulting components, the second component will be then decomposed by {2, b} into {1, 2, 3, a, b, c, f } and {2, 5, 6, b, g, h}. Fig. 5. Articulation point {2} is processed before clique separator {2,b} After the bipartite graph decomposition is completed, we will obtain sub- graphs with no remaining clique minimal separator, and the corresponding sub- relations with their associated lattices. Example 4. Figure 6 shows that the input graph of Figure 1 is decomposable into four bipartite subgraphs: G1 = G({1, 2, i}), G2 = G({2, 5, 6, b, g, h}), G3 = G({1, 2, 3, a, b, c, f }) and G4 = G({1, 4, d, e}). Note that in the general case all subgraphs obtained have at least two vertices, since at least one vertex of a separator is copied into a component which has at least one vertex. Fig. 6. Complete decomposition of a bipartite graph 3.4 The global decomposition process To obtain the entire decomposition of a connected bipartite graph, we will thus first decompose the graph using all articulation points, and then decompose each of the subgraphs obtained using all its clique separators of size 2. The articulation points (clique minimal separators of size one) can be found by a simple depth-first search [6], as well as the corresponding decomposition of the graph (called decomposition into biconnected components). The search for clique separators of size two corresponds to a more complicated algorithm, described in [5]: all separators of size 2 are obtained, whether they are cliques or not. Once this list of separators is obtained, it is easy to check which are joined by an edge. The desired decomposition can then be obtained easily. In both cases, the set of clique separators is output. Both algorithms run in linear time, so the global complexity is in O(|R|) to obtain both the set of subgraphs and the set of clique separators of the original graph. 3.5 Sub-patterns defined in the matrix When the clique separators involved do not overlap and each defines exactly two connected components, this decomposition of the bipartite graph partitions the graph and the underlying relation. This results in a significant pattern of their binary matrix. As the components obtained are pairwise disconnected, the matrix can be reorganized in such a way that zeroes are gathered into blocks. Two components may appear as consecutive blocks, linked by a row corresponding to the articulation point that has been used to split them, or linked by one cell giving the edge between the two vertices of a size two clique minimal separator. In the general case, this pattern can occur in only some parts of the matrix, and different patterns can be defined according to the different separators which the user chooses to represent. Example 5. The first of the two matrices below corresponds to our running ex- ample from Figure 1 and has been reorganized, following the decomposition, which results in the second matrix. Notice how {1} is an articulation point, so row 1 is shared by blocs 231×bacf and 14×de; and how {2, b} is a clique separa- tor of size two, so cell [2, b] is the intersection of blocs 562 × ghb and 231 × bacf . [2, i] is not integrated into the pattern, because separator {2, b} of Bip(R) defines 3 connected components: {2, 5, 6, b, g, h}, {i} and {1, 3, 4, a, c, d, e, f }. We will now describe a process to organize the lines and columns of the ma- trix with such patterns. We will construct a meta-graph (introduced in [7] as the ’atom graph’), whose vertices represent the subgraphs obtained by our decompo- sition, and where there is an edge between two such vertices if the two subgraphs which are the endpoints have a non-empty intersection which is a clique minimal separator separating the corresponding two subgraphs in the original bipartite graph. In this meta-graph, choose a chordless path; the succession of subgraphs along this path will yield a succession of rectangles in the matrix which corre- spond to a pattern. Example 6. Figure 7 gives the meta-graph for our running example from Figure 1. Chordless path ({2, 5, 6, b, g, h}, {1, 2, 3, a, b, c, }, {1, 4, d, e}) was chosen for the patterning. Another possible chordless path would be ({2, i}, {1, 2, 3, a, b, c, }, {1, 4, d, e}). Finding a chordless path in a graph can be done in linear time; the meta-graph has less than min(|A|, |O|) elements, so finding such a path costs less than (min(|A|, |O|))2 . Fig. 7. Meta-graph for graph from Figure 1 3.6 Decomposing the lattice We will now examine how the set of concepts is modified and partitioned into the subgraphs obtained. As clique minimal separators are copied in all the com- ponents induced, most of the concepts will be preserved by the decomposition. Furthermore, only initial concepts including a vertex of a clique minimal sepa- rator may be affected by the decomposition. Definition 1. We will say that a maximal biclique is a star maximal biclique if it contains either exactly one object or exactly one attribute. This single object or attribute will be called the center of the star. Lemma 1. A star maximal biclique {x} ∪ N (x) of Bip(R) is an atomic concept of L(R) (atom or co-atom), unless x is universal in Bip(R). More precisely, {x} × N (x) is a atom if x ∈ O and N (x) 6= A, or N (x) × {x} is a co-atom if x ∈ A and N (x) 6= O. Proof. Let {x} ∪ N (x) be a star maximal biclique of Bip(R). As a maximal biclique, it corresponds to a concept of L(R). Suppose the star has x ∈ O as center . As a star, it contains no other element of O; as a biclique, it includes all N (x) ⊆ A, and no other element of A by maximality. The corresponding concept is {x} × N (x) which is obviously the first concept from bottom to top including x. As the biclique is maximal, and as x is not universal, this concept cannot be the bottom of L(R) but only an atom. A similar proof holds for x ∈ A and co-atomicity. We will now give the property which describes how the maximal bicliques are dispatched or modified by the decomposition. In the next Section, we will give a general theorem and its proof, from which these properties can be deduced. Property 1. Let G = (X + Y, E) be a bipartite graph, let S be a clique minimal separator of G which decomposes G into subgraphs G1 , ..., Gk . Then: 1. ∀x ∈ S, {x} ∪ NG (x) is a star maximal biclique of G. 2. ∀x ∈ S, {x} ∪ NG (x) is not a maximal biclique of any Gi . 3. ∀x ∈ S, {x} ∪ NGi (x) is a biclique of Gi , but it is maximal in Gi iff it is not strictly contained in any other biclique of Gi . 4. All the maximal bicliques of G which are not star bicliques with any x ∈ S as a center are partitioned into the corresponding subgraphs. With the help of Lemma 1, this property may be translated in terms of lattices. Given a relation R, its associated graph G, its lattice L(R), and a decomposition step of G into some Gi s by articulation point {x}: If x ∈ O (resp. ∈ A) is an articulation point of G, {x}×NG (x) (resp. NG (x)× {x}) is a concept of L(R). After the decomposition step, in each subgraph Gi of G, either this concept becomes {x}×NGi (x), or this concept disappears from Gi ; this latter case occurs when there is in Gi some x0 ∈ O, the introducer of which appears after the introducer of x in L(R), from bottom to top (resp. from top to bottom if x, x0 ∈ A). Every other concept will appear unchanged in exactly one lattice associated with a subgraph Gi . The same holds for each vertex of a size two clique minimal separator. Example 7. Figure 8 illustrates a decomposition step with articulation point {1} using the graph from Figure 3. Concept {1, 4} × {d, e} disappears from the first component {1, 2, 3, a, b, c}, but remains in the second component {1, 4, d, e}. Fig. 8. Example of lattice decomposition using articulation point {1}. Example 8. Figure 9 illustrates a decomposition step with clique separator {2, b} using the graph from Figure 4. Concept {2}×N (2) is duplicated into components {2, 5, 6, b, g, h} and {1, 2, 3, a, b, c, f }; concept N (b) × {b} will appear as {2, 6} × {b} in the first component, but not in the second one, as {2, 3, b} is a biclique included in maximal biclique {2, 3, b, f } of G. Remark 1. The smaller lattices obtained can not be called sublattices of the initial lattice as some of their elements may not be the same: for example, in Figure 9, {2} × {b, c, f } is an element of the third smaller lattice L(G3 ) but is not an element of the initial lattice L(G). 4 Reconstructing the lattice We will now explain how, given the subgraphs obtained by clique decomposi- tion, as well as the corresponding subrelations and subsets of concepts, we can reconstruct the set of concepts of the global input bipartite graph. We will then go on to explain how to obtain the Hasse diagram of the reconstructed lattice. Fig. 9. Example of lattice decomposition using clique separator {2, b}. 4.1 Reconstructing the set of concepts We will use the following Theorem, which describes the concepts of the global lattice. Theorem 1. Let G = (X + Y, E) be a bipartite graph, let Σ = {s1 , ...sh } be the set of all the vertices which belong to a clique separator of G, let G1 , ...Gk be the set of subgraphs obtained by the complete corresponding clique separator decomposition. Then: 1. For every s ∈ Σ, {s} ∪ NG (s) is a star maximal biclique of G. 2. Any maximal biclique of a subgraph Gi which is not a star with a vertex of Σ as center is also a maximal biclique of G. 3. There are no other maximal bicliques in G: ∀s ∈ Σ, no other star maximal biclique of Gi with center s is a star maximal biclique of G, and these are the only maximal bicliques of some graph Gi which are not also maximal bicliques in G. Proof. 1. For every s ∈ Σ, {s} ∪ NG (s) is a star maximal biclique of G: Case 1: s is an articulation point, let Gi , Gj be two graphs which s belongs to; s must be adjacent to some vertex yi in Gi and to some vertex yj in Gj . Suppose {s} ∪ NG (s) is not a maximal biclique: there must be a vertex z in G which sees yi and yj , but then {s} cannot separate yi from yj , a contradiction. Case 2: s is not an articulation point, let s0 be a vertex of S such that {s, s0 } is a clique separator of G, separating Gi from Gj . s must as above see some vertex yi in Gi and some vertex yj in Gj . Suppose {s} ∪ NG (s) is not maximal: there must be some vertex w in G which sees all of NG (s), but w must see yi and yj , so {s, s0 } cannot separate Gi from Gj . 2. Let B be a non-star maximal biclique of Gi , containing o1 , o2 ∈ O and a1 , a2 ∈ A. Suppose B is not maximal in G: there must be a vertex y in G − B which augments B. Let y be in Gj , wlog y ∈ A: y must see o1 and o2 . Since Gi is a maximal subgraph with no clique separator, Gi + {y} must have a clique separator. Therefore N (y) must be a clique separator of this subgraph, but this is impossible, since y sees two non-adjacent vertices of Gi . 3. Any star maximal biclique B of Gi whose center is not in Σ is also a star maximal biclique of G: suppose we can augment B in G. Case 1: v sees an extra vertex w; Gi + {w} contains as above a clique sepa- rator, which is impossible since N (w) = v and v 6∈ S. Case 2: A vertex z of Gj is adjacent to all of N (v): again, G + {z} contains a clique separator, so N (z) is a clique separator, but that is impossible since N (z) contains at least two non-adjacent vertices. 4. For s ∈ Σ, no star maximal biclique of Gi is a star maximal biclique of G: let B be a star maximal biclique of Gi , with s ∈ Σ as center. s ∈ Σ, so s belongs to some clique separator which separates Gi from some graph Gj . s must see a vertex yj in Gj , so B + {yj } is a larger star including B: B cannot be maximal in G. Example 9. We illustrate Theorem 1 using graph G from Figure 6, whose decom- position yields subgraphs G1 , ..., G4 , with G1 = G({1, 2, i}), G2 = G({2, 5, 6, b, g, h}), G3 = G({1, 2, 3, a, b, c, f }) and G4 = G({1, 4, d, e}). Finally, Σ = {1, 2, b}. The corresponding lattices are shown in Figure 10, and their concepts are presented in the table below. In this table, braces have been omitted; symbol ⇒ represents a concept of the considered subgraph Gi which is identical to a concept of G (there can be only one ⇒ per row); the other concepts of the subgraphs will not be preserved in G while recomposing. L(G) L(G1 ) L(G2 ) L(G3 ) L(G4 ) star max. biclique of G ? 1 × acde 1 × ac yes 2 × bcf hi 2 × i 2 × bh 2 × bcf yes 3 × abf ⇒ 14 × de ⇒ 5 × gh ⇒ 6 × bg ⇒ 13 × a ⇒ 236 × b 26 × b yes 12 × c ⇒ 23 × bf ⇒ 56 × g ⇒ 25 × h ⇒ Fig. 10. Reconstruction of a lattice According to Theorem 1, the steps to reconstruct the maximal concepts of the global lattice from the concepts of the smaller lattices are: 1. Compute Σ, the set of attributes and objects involved in a clique minimal separator. (In our example, Σ = {1, 2, b}.) 2. Compute the maximal star bicliques for all the elements of Σ. (In our exam- ple, we will compute star maximal bicliques 1 × acde, 2 × bcf hi and 26 × b.) 3. For each smaller lattice, remove from the set of concepts the atoms or co- atoms corresponding to elements of Σ; maintain all the other concepts as concepts of the global lattice. (In our example, for L(G3 ), we will remove 1×ac and 2×bcf , and maintain 3×abf, 13×a, 12×c and 23×bf as concepts of L(G).) Step 1 requires O(|R|) time. Step 2 can be done while computing the smaller lattices; Step 3 costs constant time per concept. Thus the overall complexity of the reconstruction is in O(|R|) time. 4.2 Reconstructing the edges of the Hasse diagram According to Theorem 1, the maximal bicliques which are not star maximal bicliques with a vertex of Σ as center are preserved; therefore, the corresponding edges between the elements of the lattice are also preserved. In the process described below, we will refer to labels in the lattice as being the ’reduced’ labels, such as the ones used in our lattice figures throuhout this paper. To define the edges of the Hasse diagram of lattice L(G), we will, for each smaller lattice L(Gi ): – find each atom (or co-atom) which corresponds to an element σ of Σ (such as 2 or b for L(G3 ) in our example). – If σ shares its label with some non-elements of Σ, remove all elements of Σ from the label. (In our example for L(G3 ), bf becomes f ). If σ does not share its label with some non-elements of Σ, remove the atom or co-atom. (In our example for L(G3 ), remove element 2). – Maintain the remaining edges as edges of L(G). – Compute the neighborhood in L(G) of each atom or co-atom which corre- sponds to an element of Σ. All this can be done in polynomial time: there are at most |A| + |O| vertices in Σ, and the corresponding edges can be added in O((|A| + |O|)2 |R|). 5 Vertical decomposition as a layout tool When there is a size two clique separator in the bipartite graph which divides the graph into two components, the concepts which are not involved in the separator can be displayed on the two sides of the separator, thus helping to minimize the number of line crossings in the Hasse diagram. (a) (b) Fig. 11. (a) Lattice constructed by Concept Explorer using the minimal intersection layout option (8 crossings). (b) Lattice re-drawn using the information on clique sep- arators (5 crossings). To illustrate this, we have used our running example with ’Concept Explorer’ [1], which is a very nice and user-friendly tool for handling lattices. Notice how- ever how clique separator {1, d} is better displayed when put at the right ex- tremity. Figure 11 shows the lattice as proposed by Concept Explorer, and then re- drawn with insight on the clique separators of the bipartite graph. The same technique of course also applies when there is a succession of such clique separators. Let us add that if moreover both lattices are planar, as discussed in [4], merg- ing the two lattices obtained using the clique separator as central will preserve planarity. 6 Conclusion and perspectives We have used a graph method, clique minimal separator decomposition, to pro- vide simple tools which can help reduce the time spent computing the elements of a lattice, as well as improve the drawing of its Hasse diagram. When there is no clique separator in the bipartite graph, it could be inter- esting to investigate restricting the relation to a subgraph or partial subgraph which does have one. We leave open the question of characterizing, without computing the relation, the lattices whose underlying bipartite graph has a clique minimal separator. Acknowledgments The authors sincerely thank all the referees for their useful suggestions and questions. References 1. Concept Explorer. Downloadable at http://sourceforge.net/projects/conexp/, ver- sion 1.3 (Java), 20/12/2009. 2. Berry A., Sigayret A.: Representing a concept lattice by a graph. Discrete Applied Mathematics, 144(1-2):27–42, 2004. 3. Berry A., Pogorelcnik R., Simonet G.: An introduction to clique minimal separator decomposition. Algorithms, 3(2):197–215, 2010. 4. Eschen E.M., Pinet N., Sigayret A.: Consecutive-ones: handling lattice planarity efficiently. CLA’07, Montpellier (Fr), 2007. 5. Hopcroft J. E., Tarjan R. E.: Dividing a graph into triconnected components. SIAM J. Comput., 2(3):135–158, 1973. 6. Hopcroft J. E., Tarjan R. E.: Efficient algorithms for graph manipulation [H] (Algorithm 447). Commun. ACM, 16(6):372–378, 1973. 7. Kaba B., Pinet N., Lelandais G., Sigayret A., Berry A.: Clustering gene expression data using graph separators. In Silico Biology, 7(4-5):433–52, 2007. 8. Leimer H.-G.: Optimal decomposition by clique separators. Discrete Mathematics, 113(1-3):99–123, 1993. 9. Tarjan R. E.: Decomposition by clique separators. Discrete Mathematics, 55(2):221–232, 1985.