Nathann Cohen

David Coudert

Guillaume Ducoffe

Aurélien Lancin

Applying clique-decomposition for computing Gromov hyperbolicity *

Keywords: Hyperbolicity, algorithm, graph, decomposition Hyperbolicité, algorithme, graphe, décomposition

. More precisely, we prove that the maximum hyperbolicity taken over all the atoms is at least the hyperbolicity of G minus one. We also give an algorithm to slightly modify the atoms, which is at no extra cost than computing the atoms themselves, and so that the maximum hyperbolicity taken over all the resulting graphs is exactly the hyperbolicity of G. An experimental evaluation of our methodology is provided for large collaboration networks. Finally, we deduce from our theoretical results the first linear-time algorithm to compute the hyperbolicity of an outerplanar graph.

N. Cohen, D. Coudert, G. Ducoffe, A. Lancin

Inria 1 Introduction

In this paper, we primarily aim to study graph hyperbolicity, from an algorithmic point of view. This parameter was first introduced by Gromov in the context of automatic groups [START_REF] Gromov | Hyperbolic groups[END_REF], then extended to more general metric spaces, including the shortest-path metrics of simple graphs. Hyperbolicity of unweighted graphs, and its tight relations to other metric parameters, has received growing attention over the last decades, especially due to its practical applications in approximation algorithms [START_REF] Chepoi | Notes on diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs[END_REF], routing [START_REF] Boguñá | Sustaining the Internet with hyperbolic mapping[END_REF], network security [START_REF] Jonckheere | Geometry of network security[END_REF] and bioinformatics [START_REF] Chakerian | Computational tools for evaluating phylogenetic and hierarchical clustering trees[END_REF][START_REF] Dress | Basic Phylogenetic Combinatorics[END_REF], to name a few. The reader may refer to [START_REF] Abu-Ata | Metric tree-like structures in real-life networks: an empirical study[END_REF][START_REF] Dragan | Tree-like structures in graphs: A metric point of view[END_REF] for a recent survey.

However, the computational cost of hyperbolicity has received less attention. So far, the bestknown algorithm for computing the hyperbolicity of a graph [START_REF] Fournier | Computing the gromov hyperbolicity of a discrete metric space[END_REF] is impractical for large-scale graphs such as the graph of the Autonomous Systems of the Internet, road maps, etc. This both comes from its challenging implementation, relying on fast square matrix multiplications, and its time complexity which is strictly more than cubic. While practical advances have been made, improving the computational cost on certain graph classes (see [START_REF] Cohen | Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs[END_REF][START_REF] Kennedy | On the hyperbolicity of large-scale networks[END_REF]), a recent theoretical work [START_REF] Coudert | On the recognition of C 4 -free and 1/2-hyperbolic graphs[END_REF] suggests that an algorithm for the problem with a significant speed-up for all graphs is unlikely to exist. This motivates the study of structural properties that may help to decrease the running time of the computation of hyperbolicity.

Our approach relies on divide-and-conquer techniques, especially graph decompositions. Roughly, we aim to reduce the computation of the hyperbolicity of a graph to the computation of the hyperbolicity of (some of) its subgraphs, so that we can decrease the size of the input graphs to deal with. A first step toward this direction was the result in [START_REF] Soto Gómez | Quelques propriétés topologiques des graphes et applications à internet et aux réseaux[END_REF], where the author proved that the hyperbolicity of a connected graph is the maximum hyperbolicity taken over all the subgraphs obtained either via the modular decomposition [START_REF] Gallai | Transitiv orientierbare graphen[END_REF], or with the split-decomposition [START_REF] Cunningham | Decomposition of directed graphs[END_REF].

We here address a similar question for the subgraphs obtained via the clique-decomposition, also known as atoms. This decomposition was first introduced by Tarjan in [START_REF] Tarjan | Decomposition by clique separators[END_REF], then made unique by Leimer in [START_REF] Leimer | Optimal decomposition by clique separators[END_REF]. On the theoretical side, it is already known that clique-decomposition can be applied to speed-up the computation of many graph parameters, including metric parameters that are related to hyperbolicity, such as tree-length [START_REF] Dourisboure | Tree-decompositions with bags of small diameter[END_REF]. Also, complex networks are expected to be decomposable w.r.t. clique-decomposition, especially when they are related to phylogenetical data, text-data mining, or distance data [START_REF] Berry | Efficient clique decomposition of a graph into its atom graph[END_REF][START_REF] Biha | Graph decomposition approaches for terminology graphs[END_REF][START_REF] Kaba | Clustering gene expression data using graph separators[END_REF]. This makes our approach practical for large-scale graphs.

We will prove that while the hyperbolicity of a graph cannot be deduced from the hyperbolicity of its atoms (Section 3), it yields an approximation with additive constant 1 of this parameter (Section 4). Additionally, we characterize the cases for which this small additive distortion might happen. In Section 5, we will show how each atom can be modified in order to compute exactly the hyperbolicity, and provide a complexity analysis of the procedure. Experiments in Section 7 show the benefit of our method in terms of size of the graph, when applied to some real collaboration networks.

Finally, we will see in Section 6 that our method is beneficial for the class of outerplanar graphs, as it gives a linear-time algorithm to compute the hyperbolicity of these graphs.

Definitions and notations used in this paper will be introduced in Section 2.

Definitions and notations

We essentially rely on the graph terminology of [START_REF] Bondy | Graph theory with applications[END_REF][START_REF] Diestel | Graph theory[END_REF]. All graphs considered in this paper are finite, unweighted and simple. We here only emphasize some notions related to metric graph theory. The reader may refer to [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF] for a survey about this domain. Given two vertices u, v, a uv-path of length l ≥ 0 is a sequence of vertices (u = v 0 v 1 . . . v l = v), such that {v i , v i+1 } is an edge for every i. In particular, G is connected if there exists a uv-path for all pair u, v ∈ V , and in such a case the distance d G (u, v) is defined as the minimum length of a uv-path in G. Note that it yields a discrete metric space (V, d G ), also known as the shortest-path metric space of G. We will write d instead of d G whenever G is clear from the context, and we denote by d(u, X) = min x∈X d(u, x) the distance between a vertex u and a set X of vertices.

Our proofs use the notions of subgraphs, induced subgraphs, as well as isometric subgraphs, the latter denoting a subgraph H of a graph G such that d H (u, v) = d G (u, v) for any two vertices u, v ∈ H. δ-hyperbolic graphs. Graph hyperbolicity provides tight bounds on the worst additive distortion of the distances in a (connected) graph when its vertices are embedded into a weighted tree. Several definitions exist, some of them considering graph metrics that are slightly different from the usual shortest-path metric, but they are equivalent to it up to a linear-function [START_REF] Bermudo | Gromov hyperbolic graphs[END_REF][START_REF] De | Sur les groupes hyperboliques d'après Mikhael Gromov[END_REF][START_REF] Gromov | Hyperbolic groups[END_REF]. Moreover, 0-hyperbolic graphs are exactly the connected graphs whose given metric is a tree metric, which makes hyperbolicity a tree-likeness parameter. Especially, the shortest-path metric of a graph is 0-hyperbolic if, and only if, it is a block-graph, that is a graph whose biconnected components are complete subgraphs [START_REF] Bandelt | Distance-hereditary graphs[END_REF][START_REF] Howorka | On metric properties of certain clique graphs[END_REF]. This class of graphs includes trees and cliques, and a block-graph can be recognized in linear O(n + m)-time.

Definition 1 (4-points Condition, [START_REF] Gromov | Hyperbolic groups[END_REF]). Let G be a connected graph. For every 4-tuple u, x, v, y of vertices of G, we define δ(u, v, x, y) as half of the difference between the two largest sums amongst

S 1 = d(u, v) + d(x, y), S 2 = d(u, x) + d(v, y) and S 3 = d(u, y) + d(v, x)
The hyperbolicity of G, denoted by δ(G), is equal to max u,x,v,y∈V (G) δ(u, v, x, y). Moreover, we say that G is δ-hyperbolic, for every δ ≥ δ(G).

It is straightforward, by the above definition, to compute graph hyperbolicity in θ(n 4 )-time. Currently, the best-known theoretical algorithm for the problem runs in O(n 3.69 )-time [START_REF] Fournier | Computing the gromov hyperbolicity of a discrete metric space[END_REF], and the best-known practical algorithm has O(n 4 )-time complexity [START_REF] Cohen | Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs[END_REF]. Recognizing graphs with small hyperbolicity upper-bounded by 1 2 is computationally equivalent to decide whether there is a chordless cycle of length 4 in a graph, and it can be done in O(n 3.26 )-time by using fast rectangular matrix multiplication [START_REF] Coudert | On the recognition of C 4 -free and 1/2-hyperbolic graphs[END_REF][START_REF] Gall | Faster algorithms for rectangular matrix multiplication[END_REF]. Note also that the hyperbolicity of a connected graph is the maximum hyperbolicity taken over all its biconnected components.

Atoms and clique-separators. Given a connected graph G = (V, E), we name separator a subset of vertices X ⊂ V such that the removal of X disconnects the graph. When the induced subgraph G[X] is a complete graph, then we say that X is a clique-separator. More generally, we say that X is a clique-separator of S ⊆ V if S intersects (at least) two distinct connected components of G\X, and S is then said to be separable. The clique-decomposition of a graph (see Figure 1) is the collection of all its maximal non-separable sets of vertices (we will call them atoms) [START_REF] Tarjan | Decomposition by clique separators[END_REF]. The decomposition is unique [START_REF] Leimer | Optimal decomposition by clique separators[END_REF], and it can be computed in O(nm)-time [START_REF] Leimer | Optimal decomposition by clique separators[END_REF][START_REF] Tarjan | Decomposition by clique separators[END_REF].

Notations. Let us fix some notations for the proofs. Given two subsets A, B of vertices, we say that a separator X is an (A|B)-separator if it disconnects any a ∈ A\X from any b ∈ B\X. In particular, any separator X containing A or B is an (A|B)-separator, and in such a case we call X a trivial (A|B)-separator. Finally, a clique-separator is called a clique-minimal separator if there exists some pair u, v such that it is an inclusionwise minimal, non-trivial (u|v)-clique-separator. It has to be noted, perhaps counter-intuitively, that a clique-minimal separator may be contained into another one.

Inria

Hyperbolicity and clique-separators

We analyze in this section the relationship between the hyperbolicity of a graph and a given clique-separator, leading to the approximation with additive constant of Theorem 11. It begins with an observation about (a 1 , a 2 |b 1 , b 2 ) 4-tuples and the diameter diam(X) = max u,v∈X d G (u, v) of an (A|B)-separator X.

Hyperbolicity of

(a 1 , a 2 |b 1 , b 2 ) 4-tuples X A B a 1 a 2 b 1 b 2
Figure 2: Illustration of an (A|B)-separator.

Lemma 2. Let X be a an (A|B)-separator of a connected graph G. For every

(a 1 , a 2 |b 1 , b 2 ) 4-tuple, we have δ(a 1 , a 2 , b 1 , b 2 ) ≤ diam(X).
Proof. Recall that we have:

S 1 = d(a 1 , a 2 ) + d(b 1 , b 2 ), S 2 = d(a 1 , b 1 ) + d(a 2 , b 2 ), S 3 = d(a 1 , b 2 ) + d(a 2 , b 1 ).
We can assume without loss of generality (w.l.o.g.) that S 2 ≥ S 3 . Writing d(v, X) = min x∈X d(v, x), we also know that for all i, j ∈ {1, 2}:

d(a i , b i ) ≥ d(a i , X) + d(b i , X) d(a i , a j ) ≤ d(a i , X) + diam(X) + d(a j , X)
If S 1 ≥ S 2 , we get:

S 2 = d(a 1 , b 1 ) + d(a 2 , b 2 ) ≥ d(a 1 , X) + d(b 1 , X) + d(a 2 , X) + d(b 2 , X) ≥ d(a 1 , X) + d(a 2 , X) + diam(X) + d(b 1 , X) + d(b 2 , X) + diam(X) -2 diam(X) ≥S 1 -2 diam(X) Hence we have that δ(a 1 , a 2 , b 1 , b 2 ) ≤ (S 1 -S 2 )/2 ≤ diam(X). It can be shown similarly that S 3 ≥ S 2 -2 diam(X), and when S 2 ≥ S 1 that S 1 ≥ S 2 -2 diam(X). Consequently, δ(a 1 , a 2 , b 1 , b 2 ) ≤ diam(X) in all cases. Corollary 3. Let X be a an (A|B)-clique-separator of a connected graph G. For every (a 1 , a 2 |b 1 , b 2 ) 4-tuple, we have δ(a 1 , a 2 , b 1 , b 2 ) ≤ 1.

Hyperbolicity of

(a|b 1 , b 2 , b 3 ) 4-tuples X A B a b 1 b 2 b 3 Figure 3: Illustration of an (a|b 1 , b 2 , b 3 )-separator.
Note that X being a clique, each vertex a ∈ A is at distance at least d(u, X) and at most d(u, X) + 1 from any vertex of X. We now show how this can be used with respect to the hyperbolicity.

) 4-tuple, let x ∈ X be such that d(a, x) = d(a, X). We have δ(a, b 1 , b 2 , b 3 ) ≤ δ(x, b 1 , b 2 , b 3 ) + 1/2. Proof. Let us assume w.l.o.g. that S 1 ≥ S 2 ≥ S 3 , where S 1 = d(a, b 1 ) + d(b 2 , b 3 ), S 2 = d(a, b 2 ) + d(b 1 , b 3 ) and S 3 = d(a, b 3 ) + d(b 1 , b 2 ).
We can assume that every vertex a ∈ A has been replaced by an equivalent vertex a * as defined in Lemma 4 and so, that all vertices of A have a neighbor in X. In such a situation, any

b ∈ B satisfies d(x, b) ≤ d(a, b) ≤ d(x, b) + 1. Similarly, any sum S ′ i = d(x, b i ) + d(b j , b k ), where {j, k} = {1, 2, 3} \ {i}, satisfies S ′ i ≤ S i ≤ S ′ i + 1. Thus for every i ∈ {2, 3} : δ(a, b 1 , b 2 , b 3 ) ≤(S 1 -S i )/2 ≤(S ′ 1 + 1 -S ′ i )/2 ≤(S ′ 1 -S ′ i )/2 + 1/2 Inria In particular, if S ′ 1 = max{S ′ 1 , S ′ 2 , S ′ 3 }, then we have δ(a, b 1 , b 2 , b 3 ) ≤ 1 2 by the choice of S ′ i = max{S ′ 1 , S ′ 2 , S ′ 3 }. Otherwise, we have δ(a, b 1 , b 2 , b 3 ) ≤ δ(x, b 1 , b 2 , b 3 ) + 1 2 by the choice of S ′ i = max{S ′ 2 , S ′ 3 }.

Separable sets

G 1 G 2 G 3 G 4 G 5 G 6 X
Figure 4: Illustration of separable sets.

Theorem 6. Let X be a clique-separator of a connected graph G, and let C 1 , . . . , C l be the connected components of G\X. We define

G i = G[C i ∪ X].
We have :

max{δ(G 1 ), . . . δ(G l )} ≤ δ(G) ≤ max{ 1 2 , δ(G 1 ), . . . δ(G l )} + 1/2
Proof. Note that since a complete subgraph is isometric, then every subgraph G i is isometric as well. Hence, the lower-bound follows from the four-point definition.

Let us now prove that δ(a, b, c, d) ≤ max{ The upper-bound of Theorem 6 is actually tight. It can be shown using the graph in Figure 5, constructed from a cycle C 7 of length 7 to which we add a triangle.

Hyperbolicity and clique-decomposition

In Section 3, we explained how a single clique-separator can be used to approximate hyperbolicity. However, this result cannot be used on a whole clique-decomposition as the successive approximations would add up. We thus need to find additional properties to approximate the hyperbolicity of a graph from computations on its atoms in order to prove Theorem 11.

Relating atoms and 4-tuples with large hyperbolicity

Firstly, we aim to relate to every 4-tuple a, b, c, d with a sufficiently large hyperbolicity, some atom by which all the paths between a, b, c, d go through. Our result involves basic knowledge about tree-decomposition (see [START_REF] Bodlaender | Discovering treewidth[END_REF]). We remind the reader that a tree-decomposition of a connected graph G is a tree T whose nodes are labeled by subsets of V (G) (also known as bags), and which satisfies the following properties:

• every edge of G is contained into some bag;

• for every vertex u ∈ V (G), the subgraph induced by the bags containing u is a subtree of T .

Lemma 7. Let a, b, c, d be a 4-tuple satisfying δ(a, b, c, d) ≥ 3 2 in a connected graph G. There exists an atom A such that ∀u ∈ {a, b, c, d}\A, there is a clique-separator X u ⊆ A which separates u from {a, b, c, d} \ {u}.

Proof. If the vertices a, b, c, d are contained into a common atom A, then we are done as {a, b, c, d} \ A is empty. Suppose on the contrary that there is no atom containing the 4-tuple. The authors of [START_REF] Olesen | Maximal prime subgraph decomposition of bayesian networks[END_REF] proved that there exists a tree-decomposition T G of G whose bags are exactly the atoms of G. As there is no bag containing a, b, c, d by the hypothesis, there is a unique smallest subtree T of T G containing a, b, c, d. Note that T is not reduced to a single vertex, and it has at most 4 leaves.

It can be checked that there exists a bag A in T (i.e. an atom of G) such that no connected component of T \{A} (and thus no connected component of G\A) contains more than two elements among a, b, c, d. Moreover, if a connected component C of G \ A contains exactly two elements of a, b, c, d, then N G (C) ∩ A is a clique of G separating two elements of a, b, c, d from the two others, which is impossible by Corollary 3 as we supposed δ(a, b, c, d) ≥ 3 2 . Thus, for every u ∈ {a, b, c, d}\A, the connected component C u of G\A containing u yields a clique N G (C u ) ∩ A, which separates u from {a, b, c, d} \ {u}.

As an illustration, one may notice that the central atom in Figure 6 satisfies the property of Lemma 7 with respect to the 4-tuple v 0 , v 1 , v 2 , v 3 . Indeed, none of the four vertices is contained into this atom, but each of them is simplicial and can be separated from the three others by its two neighbours.

Moreover, we note that our above result heavily relies on the tree-like structure of the atoms (e.g we use a tree-decomposition whose bags are the atoms), and that such a tree-like structure does not exist in general if separators with diameter at least 2 are involved. In fact, our results in this section cannot be extended to decompositions with separators of bounded diameter, as there exist infinitely many graphs that are completely separable with isometric separators of diameter at most 2, and whose hyperbolicity is arbitrarily large [START_REF] Koolen | Hyperbolic bridged graphs[END_REF].

Inria v 0 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 v 11 v 12 v 13 v 14 v 15

Substitution method

From Lemma 7 we can associate a specific atom to a 4-tuple of large hyperbolicity. Four applications of Lemma 5 are then sufficient to prove that the hyperbolicity of this 4-tuple and the hyperbolicity of the atom differ by at most 2. The purpose of this section is to prove that this difference is at most 1. To do this, we refine the results of Section 3.2.

Lemma 8. Let X be an (A|B)-clique-separator of a connected graph G. Given an (a|b 1 , b 2 , b 3 ) 4-tuple, write:

S 1 = d(a, b 1 ) + d(b 2 , b 3 ), S 2 = d(a, b 2 ) + d(b 1 , b 3 ), S 3 = d(a, b 3 ) + d(b 1 , b 2 ).
Assume w.l.o.g. that S 1 ≥ S 2 ≥ S 3 , and let

x 2 ∈ X be such that d(a, b 2 ) = d(a, x 2 ) + d(x 2 , b 2 ) = d(a, X) + d(x 2 , b 2 ). If δ(a, b 1 , b 2 , b 3 ) > δ(x 2 , b 1 , b 2 , b 3 ), then we have • S 1 > S 2 = S 3 . • d(a, b 1 ) = d(a, x 2 ) + d(x 2 , b 1 ).
Proof. Recall that by the substitution of Lemma 4, we can assume w.l.o.g. that for every i we have d(a,

x i ) = d(a, X) = 1, where x i is a vertex of X located on an ab i -shortest path. Now, let ε i = d(x 2 , b i ) -d(x i , b i ).
Observe that ε i ∈ {0, 1}, and that ε i = 0 if, and only if, x 2 lies on an ab i -shortest path. In particular we have ε 2 = 0.

Let us denote by S

′ i the sum d(x 2 , b i ) + d(b j , b k ),
where {j, k} = {1, 2, 3} \ {i}. We aim to exhibit a relation between S i and S ′ i , which would yield in turn a relation between the values The metric property of Lemma 8 is illustrated with Figure 7. We use it to extend Lemma 5 as follows.

δ(a, b 1 , b 2 , b 3 ) and δ(x 2 , b 1 , b 2 , b 3 ). First, we have d(a, b i ) = d(x 2 , b i ) + 1 -ε i and so, S i = d(a, b i ) + d(b j , b k ) = d(x 2 , b i ) + d(b j , b k ) + 1 -ε i =S ′ i + 1 -ε i Since we assume here that S 1 ≥ S 2 ≥ S 3 and δ(a, b 1 , b 2 , b 3 ) > 0, we have S ′ 1 ≥ S 1 -1 ≥ max{S 2 , S 3 } ≥ max{S ′ 2 , S ′ 3 }. More precisely: RR n°8535 • If S ′ 2 ≥ S ′ 3 , then δ(a, b 1 , b 2 , b 3 ) = δ(x 2 , b 1 , b 2 , b 3 ) -ε 1 /2 ≤ δ(x 2 , b 1 , b 2 , b 3 ). • If S ′ 3 > S ′ 2 , then ε 3 = 1 because S 2 ≥ S 3 , which implies S 2 = S 3 . This, in turn, implies that δ(x 2 , b 1 , b 2 , b 3 ) = (S ′ 1 -S ′ 3 )/2 = (S 1 -1 + ε 1 -S 3 )/2 = (S 1 -S 2 )/2 -(1 -ε 1 )/2 = δ(a, b 1 , b 2 , b 3 ) -(1 -ε 1 )/2 ≤ δ(a, b 1 , b 2 , b 3 ). In such a case, δ(x 2 , b 1 , b 2 , b 3 ) < δ(a, b 1 , b 2 , b 3 ) if, and only if, we have ε 1 = 0, that is x 2 lies on an ab 1 -shortest path. X A B a x 2 x 3 b 1 b 2 b 3
Lemma 9. Let a, b, c, d be a 4-tuple of a connected graph G, and two sets X a , X d ⊆ V satisfying:

• X a is a (a|b, c, d)-clique-separator; • X d is a (d|a, b, c)-clique-separator; • X a \X d lies in the same connected component of G \ X d as a, b, c.
Then there exist x a ∈ X a and

x d ∈ X d such that δ(a, b, c, d) ≤ δ(x a , b, c, x d ) + 1/2. Proof. Let u 1 , u 2 , u 3 be such that {u 1 , u 2 , u 3 } = {b, c, d}, T 1 ≥ T 2 ≥ T 3 , where T i = d(a, u i ) + d(u j , u k ) and {j, k} = {1, 2, 3} \ {i}.
We distinguish two cases:

• First, assume that there is x a ∈ X a satisfying δ(a, b, c, d) ≤ δ(x a , b, c, d). Then we are done, as Lemma 5 applied to the (d|x a , b, c)-clique separator X d yields a vertex

x d ∈ X d satisfying δ(x a , b, c, d) ≤ δ(x a , b, c, x d ) + 1 2 , hence δ(a, b, c, d) ≤ δ(x a , b, c, x d ) + 1 2 .
• Second, assume that no vertex of X a satisfies the above property. In particular, let x a ∈ X a be such that d(a, x a ) = d(a, X a ), and x a lies on an au 2 -shortest path. Note that

δ(a, b, c, d) ≤ δ(x a , b, c, d) + 1 2 by Lemma 5 and so, δ(a, b, c, d) = δ(x a , b, c, d) + 1 2
. Moreover, we deduce from Lemma 8 that T 1 > T 2 = T 3 , and x a also lies on an au 1 -shortest-path. Let

T ′ i = d(x a , u i ) + d(u j , u k ).
It thus follows that we have:

T ′ 1 = T 1 -d(a, X a ), T ′ 2 = T 2 -d(a, X a ) and T ′ 3 = T 3 -d(a, X a ) + 1. So, we have T ′ 1 ≥ T ′ 3 > T ′ 2 .
By the contrapositive of Lemma 8 applied to the 4-tuple (d|x a , b, c), and noticing that the two least sums amongst

T ′ 1 , T ′ 2 , T ′ 3 are different, there exists a vertex x d ∈ X d satisfying δ(x a , b, c, d) ≤ δ(x a , b, c, x d ). Inria Corollary 10. Let a, b, c, d be a 4-tuple of a connected graph G satisfying δ(a, b, c, d) ≥ 3/2. There exists an atom A of G such that δ(a, b, c, d) ≤ δ(G[A]) + 1
Proof. The atom A is obtained by applying Lemma 7. For every vertex u ∈ {a, b, c, d} \ A, let X u ⊆ A be a clique-separator disconnecting u from {a, b, c, d} \ u. We claim that A \ X u lies in the same connected component of G \ X u as {a, b, c, d} \ u, because otherwise X u would separate two elements of {a, b, c, d} from the two others, which by Corollary 3 implies that δ(a, b, c, d) ≤ 1, a contradiction.

One can then apply Lemmas 9 and 5 to find four vertices a

′ , b ′ , c ′ , d ′ ∈ A such that δ(a, b, c, d) ≤ δ(a ′ , b ′ , c ′ , d ′ ) + 1. Note that the sets {a, b, c, d} and {a ′ , b ′ , c ′ , d ′ } are not necessarily disjoint.

Additive approximation for hyperbolicity

Theorem 11. Let A 1 , . . . , A l be the atoms of a connected graph G. Then:

max i δ(G[A i ]) ≤ δ(G) ≤ max i δ(G[A i ]) + 1
Proof. As for Theorem 6, the lower-bound of Theorem 11 follows from the fact that the subgraphs

G i = G[A i ] are isometric subgraphs of G.
The upper-bound trivially holds when δ(G) ≤ 1. We can thus suppose that δ(G) ≥ 3/2 and so, that there exist four vertices a, b, c, d such that δ(a, b, c, d) = δ(G) ≥ 3/2. Corollary 10 then yields an atom A such that δ(G) ≤ δ(G[A]) + 1, which proves the second part of our claim.

Note that the upper-bound is reached by the graph of Figure 6, and by the 1-hyperbolic chordal graph from Figure 1 whose atoms have hyperbolicity 0.

Substitution method for an exact computation

As shown with Theorem 11, the maximum hyperbolicity taken over all the atoms may be slightly lesser than the hyperbolicity of the graph. In the two previous sections, we characterized under which situations both values might differ. We now propose to build upon clique-decomposition by replacing the atoms with substitute graphs, so that the hyperbolicity of the atoms' substitutes yields the hyperbolicity of the initial graph. This method supposes that the hyperbolicity is at least 1.

Outline of the method. We recall that a simplicial vertex is a vertex whose neighborhood induces a complete subgraph. In the spirit of Lemma 4, we add simplicial vertices to the atoms, in order to mimic the maximum (a|b 1 , b 2 , b 3 ) 4-tuples that may result from a disconnection. We first introduce our method of substitution in the simpler context of a single disconnection. We then focus on technical details related to the implementation.

Substitute graphs

Basic step: single disconnection

Given a connected graph G, let V (G) = A ∪ B such that X = A ∩ B is an (A|B)-clique separator of G. • Let G A = G[A]. For every b ∈ B \ X, we consider the set of vertices X b ⊆ X which are at distance d G (b, X) from b. For every X b , we add in G A a (simplicial) vertex s X b whose neighborhood is X b . The resulting graph is named G * A . • Let G B = G[B].
For every a ∈ A \ X, we consider the set of vertices X a ⊆ X which are at distance d G (a, X) from a. For every X a , we add in G B a (simplicial) vertex s Xa whose neighborhood is X a . The resulting graph is named

G * B .
More formally, the substitute graphs (or substitutes for short) G * A and G * B of the graphs G A and G B with respect to the (A|B)-separator X are defined as follows:

Definition 12. Given a connected graph G, let V (G) = A ∪ B such that X = A ∩ B is an (A|B)-clique separator of G. The substitute graphs G *
A , G * B are defined as:

V (G * A ) = A ∪ {s X b : ∃b ∈ B s.t. X b = arg min x∈X d(b, x)} and E(G * A ) = E(A) ∪ {{s X b , x} : x ∈ X b } V (G * B ) = B ∪ {s Xa : ∃a ∈ A s.t. X a = arg min x∈X d(a, x)} and E(G * B ) = E(B) ∪ {{s Xa , x} : x ∈ X a } Lemma 13. Let G be a connected graph satisfying δ(G) ≥ 1, and V (G) = A ∪ B such that A∩B = X, where X denotes an (A|B)-clique separator of G. We define G A = G[A], G B = G[B].
We have: We emphasize that some simple rules can be applied to reduce the size of the substitute graphs. In particular, we can remove the pendant vertices which may be added in the construction.

δ(G) = max{1, δ(G * A ), δ(G * B )}. Proof. First, we prove that δ(G) ≤ max{1, δ(G * A ), δ(G * B )}. By construction, the subgraph G A is an isometric subgraph of G * A ,
* of G * B \ B that is adjacent to {x ∈ X : d G (a, x) = d G (a, X)}; hence, δ(a, b 1 , b 2 , b 3 ) = δ(a * , b 1 , b 2 , b 3 ) ≤ δ(G * B )

Extension to the atoms

The substitution operation can be naturally extended to the whole clique-decomposition, by mimicking each step of it and applying the basic substitution operation that we describe above at each of these steps. We formalize it by first introducing the following definition of an atom tree.

Inria Definition 14 ( [6, 7, 34]). Let G be a connected graph. An atom tree of G is a labeled binary rooted tree T , satisfying the following recursive definition:

• if G is prime w.r.t. clique-decomposition, then T is reduced to a node labeled with V ;

• otherwise, the root of T is labeled with a clique-minimal separator X, and there exists a connected component C of G \ X satisfying:

-N G (C) \ C = X;
-the left child of the root is labeled with A = C ∪ X, which does not contain any clique-minimal separator;

-and the right subtree of the root is an atom tree of G \ C.

In order to prevent any confusion, the reader has to notice that an atom tree is not a treedecomposition (as defined in Section 4.1). In fact, an atom tree can be seen as the trace of some execution of the algorithm of [START_REF] Leimer | Optimal decomposition by clique separators[END_REF][START_REF] Tarjan | Decomposition by clique separators[END_REF] to compute the clique-decomposition. Indeed, it is proved in [START_REF] Leimer | Optimal decomposition by clique separators[END_REF] that in an atom tree, the leaves are in bijective correspondance with the atoms of the graph. Given a fixed atom tree, this yields a natural total ordering of the atoms by increasing depth. We now follow this ordering to construct the substitutes of the atoms from the atom tree. There are as many steps for our substitution method as there are atoms in the graph.

• Starting from H 1 = G, we disconnect the first atom A 1 by using the clique-minimal separator X 1 from the atom tree. Applying the substitution operation of Definition 12 to

A = A 1 and B = V (G) \ (A 1 \ X 1 )
, we obtain two substitute graphs: G * A1 which substitutes A 1 , and another one denoted by

H 2 = G * B . • After i -1 steps, i ∈ {2, . . . , l -1},
we constructed the substitute graphs of atoms A 1 , . . . , A i-1 , plus an additional graph H i . The graph H i contains G[ j≥i A j ], to which were added simplicial vertices during the previous steps. By using the clique-minimal separator X i from the atom tree, we disconnect the graph H i , and we apply the substitution operation of Definition 12, this time to the set A equal to C A ∪X where C A is the connected component of H i \ X which intersects A i , and to

B = V (H i ) \ (A \ X i ).
We replace H i with the two substitute graphs, one containing the atom A i and being its substitute, the other being denoted by H i+1 = G * B . • We finally stop at the l th step, and we set H l is the substitute graph of the last atom A l . Figure 8 illustrates this process. The numbers reported in Table 8i illustrate the interest of our pre-processing method for the computation of the hyperbolicity. Indeed, the graph G of Figure 8a has 28 nodes and so, 20 475 4-tuples, while the sum of the numbers of 4-tuples in the graphs G * i (Figures 8c-8h) is 1 800. We thus significantly reduce the search space. Moreover, a simple cutting rule allows us to reduce the number of 4-tuples to consider to 1 575. To do so, we first order the graphs G * i by decreasing diameters, then we iteratively compute the hyperbolicity of these graphs in this order, and we stop exploration as soon as the diameter of a graph G * j is smaller than twice the largest value of δ computed so far.

Implementation and complexity analysis

Precomputation step and updates

We first focus on some computational tasks that have to be repeatedly executed at each step of our substitution method. In this section, we provide a high-level description for an implementation of these tasks. 8a), an atom tree of the graph (Figure 8b), the substitute of the atoms of G (Figures 8c-8h), and the characteristics of these graphs (Table 8i).

Inria

Computation of the distances We heavily rely in our implementation on constant time access to the distance between some vertex (possibly added by our construction) and the vertices of some clique-minimal separator. It is thus essential that we update the distance matrix of the graph quickly when we replace atoms by their substitutes.

Lemma 15. Let G be a connected graph. We can embed in quadratic time the distance matrix of G into a data structure, supporting:

• O(1) access to the distance between a vertex contained in a clique-minimal separator and any other;

• O(1) updates when a simplicial vertex is added by our substitution method.

Proof. The gist of such a structure is Lemma 4. Let X be an (A|B)-clique separator of G, and s be a simplicial vertex added in the substitute graph of

G[B]. Let a ∈ A \ X satisfy N (s) = {x ∈ X : d G (a, x) = d G (a, X)}. Then we have for every b ∈ B, d(b, s) = d G (a, b) -d G (a, X) + 1.
It thus follows that once the substitution of a with s has been completed, we only need to remember the association of s with a and an offset, so that we can compute the distances in the substitute graphs. The offset can be computed in constant time by picking a neighbor of the simplicial vertex s, as it is the distance d(a, X) between this neighbor and the vertex a which s substitutes. Finally, since there are l = O(n) steps for our substitution method, and that no more than O(n) new simplicial vertices are added at each step, a quadratic-size array is sufficient to store all the pairs (a, d(a, X a )).

Note that the data structure of Lemma 15 does not support the computation of distances between two vertices added by our construction. We can safely ignore this drawback, as we do not need to compute such distances in our method.

Determining the vertex sets of the substitute graphs Another problem is to compute, at step i of the algorithm, the connected component containing the next atom A i to deal with. Determining the connected components of a graph is linear-time computable. However, as we detailed in Section 5.1.2, here we have to extract the component from a graph H i = G, possibly containing more edges than G due to the addition of simplicial vertices at previous steps. Thus it may result in an Ω(m)-time complexity by using the classical algorithm for this problem. Instead, we propose a method to construct the component incrementally, starting from A i and adding simplicial vertices at every step 1 ≤ j ≤ i -1.

Lemma 16. Let G be a connected graph, T be an atom tree of G, and A 1 , . . . , A l be its atoms ordered according to their depth in T . We denote by H 1 = G, H 2 , . . . , H l the sequence of l graphs that are computed by our process, each H i being decomposed into H i+1 and the substitute graph of the i th atom by applying the substitution method of Definition 12. For every (simplicial) vertex s i ∈ H i+1 \ H i , we can compute the index j such that s i belongs to the substitute graph of the j th atom, in total O(n|X i |)-time.

Proof. Let s i ∈ H i+1 \ H i be a simplicial vertex. By construction (Section 5.1.2), we have N (s i ) ⊆ X i ⊆ V (G). Therefore, if s i belongs to the substitute graph of the j th atom, j > i, then it holds that N (s i ) intersects the connected component containing A j \ X j |in the graph H j \ X j |. In such case since every vertex in the component either belongs to the atom or is simplicial and not in V (G), then it follows that s i has a neighbour in A j \ X j . Conversely, if s i ∈ V (H j ) and N (s i ) ∩ (A j \ X j ) = ∅, then s i is in the same connected component as A j \ X j in the graph H j \ X j , hence s i belongs to the substitute graph of the j th atom. So, at every step of our substitution method, if a simplicial vertex is added by our construction, we consider the minimum index j such that A j \ X j contains a neighbour of the vertex, and we update the vertex set of the substitute graph of the j th atom by adding this new vertex into it. Since only O(n) vertices are added at step i, and that their neighborhood is contained into X i , the O(n|X i |)-time complexity follows.

We now focus on some algorithmic aspects of the substitution operation (Section 5.1.1).

Applying simplification rules

In this section, we will assume that the distance matrix of the graph is given. Given the set B \X, it is straightforward to compute in O(n|X|)-time all of the subsets X

b = {x ∈ X : d G (b, x) = d G (b, X)}, for every b ∈ B \ X.
A naive implementation would then consist in adding a simplicial vertex for every b and by doing so, we would lose all the benefit of the separation in terms of size of the graphs. We now define rules in order to avoid this worst-case in some situations, in order to decrease the number of simplicial vertices to add in the substitute graphs. The goal of this section is to give hints on an efficient way to implement these rules.

Partition refinement techniques Indeed, it may happen that X b = X b ′ for some pair b, b ′ ∈ B, and in such a case we wish to add only one simplicial vertex in the substitute graph G * A . To do that efficiently, we will use the well-known partition refinement techniques (e.g. see [START_REF] Habib | Partition refinement techniques: An interesting algorithmic tool kit[END_REF][START_REF] Paige | Three partition refinement algorithms[END_REF]). Given a partition P of a set V , and a subset S ⊆ V called the pivot, the partition refinement of P w.r.t. S consists in replacing every group V i of P by the non-empty groups amongst V i ∩ S and V i ∩ S. This can be achieved in O(|S|)-time, up to the precomputation of an appropriate data structure in linear O(|V |)-time.

We deduce from this standard technique the following result:

Lemma 17. Let G be a connected graph given by its distance matrix, and X ⊆ V (G). We define the relation ≡ X over the set V (G) \ X as

u ≡ X v iff {x ∈ X : d G (u, x) = d G (u, X)} = {x ∈ X : d G (v, x) = d G (v, X)}.
The equivalence classes of ≡ X can be computed in O(n|X|)-time.

Proof. We start from the partition P = {V \ X} which we refine successively for every x ∈ X with the set {u :

u ∈ V \ X s.t. d G (u, x) = d G (u, X)}. The total cost is O( x∈X |N G X (x)|) = O(n|X|).

Complexity analysis

Finally, to determine the time complexity of our substitution method, we will use the following result:

Lemma 18 ([6]
). Let G be a connected graph, and A 1 , . . . , A l be its atoms. Then i |A i | ≤ n+m.

Corollary 19. The substitute of the atoms of a connected graph G can be computed in O(nm)time.

Proof. Let T be an atom tree of G, and A 1 , . . . , A l be the atoms of the graph. For every i, let X i be the clique-minimal separator of G labeling the father node of leaf A i in T . By Definition 14,

X i ⊆ A i .
We first precompute the distance matrix of G in O(nm)-time, then we embed it in quadratictime into the data structure of Lemma 15. Also, for every i, we initialize the vertex set of the Inria i th substitute graph with the atom A i . We then apply each step of our substitution method sequentially.

We can easily check that at step i, there are at most O(n) vertices to consider. By Lemma 17, this allows us to compute the simplicial vertices to add at this step in O(n|X i |)-time. By Lemma 16, we can then update the vertex sets of the substitute graphs with the same time complexity. Since at most O(n) vertices are added at this step, we finally update the distances in O(n)-time by Lemma 15.

Consequently, our modified clique-decomposition can be computed in

O(n i |X i |)-time, that is in O(n i |A i |) = O(nm)-time by Lemma 18.

Hyperbolicity of outerplanar graphs

Last, we deal with an algorithmic application of the substitution method of Section 5. We use it here to provide a linear-time algorithm for computing the hyperbolicity of a large class of graphs.

A planar graph is a graph drawable in the Euclidean plane so that edges may only intersect at their endpoints. It is outerplanar if it stays planar whenever one adds a universal vertex to it. Equivalently, a graph is outerplanar if it is drawable in the Euclidean plane so that edges may only intersect at their endpoints, and all the vertices lie on a common face which is called the outerface. Such a drawing is furthermore called an outerplanar embedding, and it can be computed in linear-time [START_REF] Tamassia | Planar grid embedding in linear time[END_REF]. Outerplanar graphs are a minor-closed graph class, and a graph is outerplanar if, and only if, it is K 4 -minor-free and K 2,3 -minor-free (see [START_REF] Sysło | Characterizations of outerplanar graphs[END_REF] for other characterizations).

All cycles are outerplanar graphs, and in particular all atoms of an outerplanar graph are cycles. The hyperbolicity of cycles is determined by the following formula: Lemma 20 ( [START_REF] Wu | Hyperbolicity and chordality of a graph[END_REF][START_REF] Cohen | Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs[END_REF]). Cycles of order 4p + ε ≥ 3, with p ≥ 0 and ε ∈ {0, 1, 2, 3}, are (p -1/2)hyperbolic when ε = 1, and p-hyperbolic otherwise.

We will use Lemma 20 to prove the main result of this section (e.g. Theorem 27). Our proofs heavily rely on the notion of weak dual [START_REF] Baker | Approximation algorithms for NP-complete problems on planar graphs[END_REF].

Definition 21. Let G be a biconnected outerplanar graph. The weak dual of G is a tree T G equal to the intersection graph of the atoms of G. Two adjacent nodes of T G correspond to atoms which share a single edge.

Note that a weak dual is nothing else than a tree-decomposition whose bags are the atoms of an outerplanar graph. If G is biconnected, then starting from an outerplanar embedding of the graph, we construct it by removing from the dual of the graph the universal vertex corresponding to the outerface (see Figure 10 for an example).

Outerplanar graphs with small hyperbolicity

As observed in Section 5, our substitution method for an exact computation of hyperbolicity requires the hyperbolicity of the graph to be at least 1. To overcome this drawback, we first characterize in this section outerplanar graphs that are 1 2 -hyperbolic. Note that we only consider biconnected graphs, as the hyperbolicity of a graph is the maximum hyperbolicity taken over all its biconnected components, and the biconnected components of a graph are computable in linear-time [START_REF] Tarjan | Depth-first search and linear graph algorithms[END_REF]. Proposition 22. A biconnected outerplanar graph is 12 -hyperbolic if, and only if, either it is isomorphic to C 5 , or it is chordal and it does not contain the graph of Figure 9b as a subgraph. Furthermore, these conditions can be checked in linear-time.

(a) C 4 (b) H 1 (c) H 2 (d) H 3 (e) H 4
Proof. Let G be a 1 2 -hyperbolic outerplanar biconnected graph. By Lemma 20, the graph C 5 is 1 2 -hyperbolic, and we now assume G is not isomorphic to C 5 . As every induced cycle of G is isometric, the induced cycles of G are exactly its atoms. As a result, we have by Lemma 20 that G only has induced cycles of length 3 or 5. Moreover, Wu and Zhang prove in [START_REF] Wu | Hyperbolicity and chordality of a graph[END_REF] that a 5-chordal graph is 1 2 -hyperbolic if, and only if, it does not contain any graph of Figure 9 as an isometric subgraph 1 .

By the hypothesis, G is C 4 -free and so, it does not contain the graph of Figure 9a as an isometric subgraph. Moreover, we claim that G is C 5 -free, as otherwise it would contain the graph of Figure 9d, or the graph of Figure 9e, as an isometric subgraph. Thus G has to be chordal. Also, we check that G cannot contain the graph of Figure 9c, as it is not outerplanar and being outerplanar is a hereditary property. Consequently, G is 1 2 -hyperbolic if, and only if, it is chordal and it does not contain the graph of Figure 9b as an isometric subgraph. Finally, recall that a graph is outerplanar if, and only if, it is K 4 -minor-free and K 2,3 -minorfree. Let H 1 be the graph of Figure 9b. We claim that every induced subgraph of G that is isomorphic to H 1 is isometric, as otherwise it would yield a K 2,3 -minor for G. In the same way, every subgraph of G that is isomorphic to H 1 is an induced subgraph of G, as otherwise it would yield a K 4 -minor for G. So, G is 1 2 -hyperbolic if, and only if, it is chordal and it does not contain H 1 as a subgraph. Being chordal can be checked in linear-time [START_REF] Rose | Algorithmic aspects of vertex elimination on graphs[END_REF], and a chordal outerplanar graph contains H 1 as a subgraph if, and only if, there are two adjacent vertices of degree 3 in its weak dual (see Figure 10).

Substitute graphs of cycles

As we constrain ourselves to outerplanar graphs, recall that the atoms are exactly the induced cycles of the graph. Clearly, a clique-separator contained into a cycle is either a cut-point (in which case our substitution method never adds a simplicial vertex), or it is an edge-separator (in which case our substitution method might only add a single vertex, which has to be adjacent to both endpoints of the edge). Substitute graphs of cycles thus fall into the following subclass of outerplanar graphs: Definition 23. A sunshine graph is a biconnected outerplanar graph, containing a dominating induced cycle C satisfying every vertex not in C is a simplicial vertex of degree 2.

Cycles are a subclass of such graphs, and two other examples of sunshine graphs are given in Figure 11. Moreover, we remark that an edge in a dominating cycle may be the neighborhood of at most one simplicial vertex out of the cycle, as otherwise it would yield a K 2,3 -minor for the graph. It can be noted in addition that except for the particular case of a diamond, there exists a unique dominating cycle in a sunshine graph, and every induced cycle which is not dominating is a triangle. Thus, if G is a sunshine graph and C is a dominating cycle of G, then we have by Theorem 11 that δ(C) ≤ δ(G) ≤ δ(C) + 1. This difference can actually be decreased by 1 2 as follows.

Lemma 24. Let G be a sunshine graph, and C be a dominating cycle of G. Then we have:

δ(C) ≤ δ(G) ≤ δ(C) + 1 2
Proof. By Theorem 11, we have δ(C) ≤ δ(G) ≤ δ(C) + 1. So, our aim is to prove that no 4-tuple of G has a hyperbolicity greater than δ(C)

+ 1 2 . By contradiction, let a, b, c, d be such that δ(a, b, c, d) = δ(C) + 1.
We arbitrarily orient the cycle C. For every u ∈ {a, b, c, d}\C, we denote by e u = {x u , y u } the edge of C induced by its neighbours, where x u denotes the head of the edge w.r.t. the orientation. Observe that for every u

, v ∈ {a, b, c, d} \ C, we have d(u, v) = 2 + min{d(x u , y v ), d(x v , y u )} = 1 + d(x u , x v ) = 1 + d(y u , y v ).
We then claim that there is exactly one vertex amongst a, b, c, d which belongs to the cycle C. Indeed, not all of a, b, c, d belong to C as the 4-tuple has a hyperbolicity greater than δ(C). Furthermore, at least three of them are not in C, as otherwise we would have δ(a, b, c, d) ≤ δ(C) + 1 2 by Lemmas 5 and 9. On the other hand, if none of them is in C, then we can check that δ(a, b, c, d) = δ(x a , x b , x c , x d ) ≤ δ(C), a contradiction. So, the claim is proved.

Finally, assume w.l.o.g. that a ∈ C. In such a case, we can check that δ(a, b, c, d) ≤ δ(a, x b , x c , x d ) + 1 2 ≤ δ(C) + 1 2 . A contradiction. Once the upper-bound for hyperbolicity is refined as above, the hyperbolicity of a sunshine graph can be computed in linear-time, using the following characterization.

Lemma 25. Let G be a sunshine graph, and C be a dominating cycle for G of length 4p + ε ≥ 3, with p ≥ 0 and ε ∈ {0, 1, 2, 3}. Assuming G \ C is nonempty we have:

• if ε is odd, then δ(G) = δ(C) + 1 2 ; • if ε = 2, then δ(G) = δ(C) + 1
2 if, and only if, there exist two simplicial vertices out of C which are diametrically opposed;

• finally, if ε = 0, then δ(G) = δ(C).
Proof. Recall that by the previous Lemma 25, we have δ(G) ≤ δ(C) + 1 2 . Thus we only focus on finding 4-tuples u, v, x, y of hyperbolicity (at least) this value, and we choose one, if any, maximizing |C ∩ {u, x, v, y}|. In the sequel, write S 1 = d(u, v) + d(x, y), S 2 = d(u, x) + d(v, y) and S 3 = d(u, y) + d(v, x). We will assume in addition that S 1 ≥ S 2 ≥ S 3 . Case ε odd Equivalently, we have ε ∈ {1, 3}. In such a case, we have δ(C) = p + min{0,ε-2} 2 by Lemma 20. Figure 11a exhibits a 4-tuple u, v, x, y satisfying:

S 1 = (2p + ε + 1 2 ) + (2p + min{1, ε -1}) = 4p + ε + 1 2 + min{1, ε -1} S 2 = (p + 1) + (p + ε -1 2 ) = 2p + ε + 1 2 S 3 = S 2 Hence, this 4-tuple has hyperbolicity p + min{1,ε-1} 2 = δ(C) + 1 2 .
Case ε = 2 In such a case, we have δ(C) = p by Lemma 20. We assume w.l.o.g. that u / ∈ C, and we claim that it implies v / ∈ C. Indeed, by the metric property of Lemma 8, and noticing that S 1 ≥ S 2 ≥ S 3 , the vertex v has to be at equal distance l of both neighbours of u, as otherwise u could be replaced with one of its two neighbours, contradicting the maximality of |C ∩ {u, x, v, y}|. Hence v / ∈ C is impossible, as it would yield the length of C is 2l + 1 = 4p + 2. It thus follows that v / ∈ C, and the length of C is in fact 2(l -1) + 2 = 2l, yielding l = 2p + 1. Conversely, assume that there exist two simplicial vertices u, v that are diametrically opposed in G. We choose the 4-tuple u, x, v, y as in Figure 11b, and it satisfies:

S 1 = (2p + 2) + (2p + 1) = 4p + 3 S 2 = 2(p + 1) = 2p + 2 S 3 = S 2 So, we have δ(u, v, x, y) = p + 1 2 = δ(C) + 1 2 .
Case ε = 0 Another application of Lemma 20 yields δ(C) = p. Assuming u / ∈ C, we deduce as for the previous case that v / ∈ C, and v is at equal distance l = 2p from both neighbours of u. Thus, C is partitioned by the neighborhoods of u and v, in the same way as in Figure 11b, into two paths of length l -1 = 2p -1. Furthermore, since the diameter of C is 2p, those paths are geodesics of the cycle. By the proof of Lemma 24, at least one vertex z ∈ {x, y} amongst the 4tuple has to be in C so that δ(u, v, x, y) > δ(C). As a result, by picking the geodesic containing z we get d(u, z) + d(v, z) = 2 + (l -1) = 2p + 1. So, we have min{d(u, z), d(v, z)} ≤ p, contradicting Inria the fact that δ(u, v, x, y) > δ(C), because we have by [START_REF] Soto Gómez | Quelques propriétés topologiques des graphes et applications à internet et aux réseaux[END_REF] that δ(u, v, x, y) ≤ min{d(u, z), d(v, z)}.

To sum up, we always have δ(G) = δ(C) in such a case.

Applying the substitution method in linear-time

Recall that our substitution method consists in constructing a substitute graph for every atom of the graph, then computing the hyperbolicity of every substitute graph, and finally taking the maximum over these hyperbolicity values and 1. In the case of an outerplanar graph, we provided in the previous section a characterization yielding a linear-time computation of the hyperbolicity of the substitute graphs of the atoms (e.g. Lemma 25). What now remains to prove is that the substitute graphs can also be computed in linear-time.

Lemma 26. Let G be an outerplanar biconnected graph. The substitute graphs of the atoms of G can be computed in linear-time.

Proof. First, we construct in linear-time an outerplanar embedding for G, then we construct from it the weak dual T G of G. Let C 1 , . . . , C l be the atoms of G. We root T G on an atom C 1 , which is an induced cycle. Note that (T G ; C 1 ) naturally yields an atom tree, as defined in Definition 14: starting from a rooted tree (T ; C) initialized with (T G ; C 1 ), we iterate as long as T is not empty, and at each step we disconnect all the atoms being the leaves of T sequentially. Such an ordering is enough to prove the correctness of the following algorithm.

• For every i, we initialize C * i with C i .

• We start a depth-first search from the root, and for every visited atom C i , once its subtree has been visited, we consider all its sons C j , naming e i,j the edge-separator C i ∩ C j . We add in C * i a simplicial vertex whose neighborhood is e i,j if, and only if, there is a vertex in C * j which is at equal distance to both endpoints of e i,j . This is equivalent to have either the length of C j is odd, or there is a simplicial vertex in C * j \ C j whose neighborhood is the edge diametrically opposed to e i,j in C j .

• Finally, we start a breadth-first search from the root and for every visited atom

C i = C 1 ,
we consider its parent atom, denoted by C k , naming e i,k the edge-separator that it shares with it. As before, we add in C * i a simplicial vertex whose neighborhood is e i,k if, and only if, either the length of C k is odd, or there is a simplicial vertex in C * k \ C k whose neighborhood is the edge diametrically opposed to e i,k in the atom C k .

Note that for an atom, the depth-first search here is used to compute the simplicial vertices resulting from the disconnection of its sons, whereas the breadth-first search is used to compute the single vertex resulting from its own disconnection, if any. Using an atom tree as defined above, it can be checked that the resulting C * 1 , . . . , C * l are the substitute graphs of the atoms of G.

Figure 12 shows the substitute graphs resulting from the application of the substitution method to a biconnected outerplanar graph.

We finally conclude with the following theorem.

Theorem 27. The hyperbolicity of a connected outerplanar graph is computable in linear-time.

Proof. We can safely assume G to be biconnected by [START_REF] Tarjan | Depth-first search and linear graph algorithms[END_REF]. By [START_REF] Bandelt | Distance-hereditary graphs[END_REF][START_REF] Howorka | On metric properties of certain clique graphs[END_REF], G is 0-hyperbolic if, and only if, G is a clique. If it is not, then by Proposition 22, we can check whether it is 1 2 -hyperbolic in linear-time. From now on, assume δ(G) ≥ 1. By Lemma 26, we can compute the substitute graphs of the atoms of G in linear-time. We can thus conclude by Lemma 13 (i.e. the correctness of our substitution method), as these substitute graphs are sunshine graphs and their hyperbolicity is linear-time computable by Lemma 25.

Experimental evaluation

We report in this section on experiments performed with our substitution methodology on the graphs of five collaboration networks. This way, we aim to evaluate the computation time of the substitutes on some empirical graphs, and to better understand the factors impacting their size.

Datasets

We apply the algorithm presented in Section 5 to the collaboration networks of five different scientific communities [START_REF] Leskovec | Graph evolution: Densification and shrinking diameters[END_REF], namely:

• ca-AstroPh, for the astrophysics community;

• ca-CondMat, for the condensed matter physics community;

• ca-GrQc, for the general relativity and quantum cosmology community;

• ca-HepPh, for the high energy physics-phenomenology community;

• and ca-HepTh, for the high energy physics-theory community.

In the ca-* graphs, nodes represent scientists and edges represent collaborations (i.e., coauthoring a paper). These graphs are interesting to analyze the behavior of our algorithm, and the size of their substitute graphs, because they have many cliques of various sizes. Indeed, a paper co-authored by k scientists induces a clique of size k in the graph. Furthermore, the number of co-authors per papers varies from one community to another. Therefore, we will observe different results in terms of the size of their substitute graphs, despite these graphs share many properties (see [START_REF] Leskovec | Graph evolution: Densification and shrinking diameters[END_REF]).

Inria

Empirical results

We modified the clique-decomposition algorithm of [START_REF] Berry | An introduction to clique minimal separator decomposition[END_REF], to implement the substitution method that we presented in Section 5. We used it here to compute, for every graph, the substitute of each atom of the decomposition.

Decomposition into biconnected components

We observed that all of the five graphs are composed of one largest biconnected component, that we call LBC. The component includes from 50% to 84.85% of all the vertices. This can be observed from the cumulative distribution of the size of the biconnected components in Figure 13a. The cumulative number of components is given as a percentage of the total number of biconnected components, and the size of the components as a percentage of the total number of vertices in the graph. We noticed that all the biconnected components but the LBC are small: only covering at most 1% of the vertices.

Clearly, the smallest biconnected components can be safely ignored for the computation of hyperbolicity, provided that a) their number of vertices is less than 4, or that b) their diameter is smaller than two times the hyperbolicity of the LBC, which is always the case for these graphs (see [START_REF] Cohen | Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs[END_REF]). Thus, we now focus on the clique-decomposition of the LBC, and on its resulting substitute graphs. 13a) and of the atoms in the LBC of each graph (Figure 13b).

Clique-decomposition

We plotted in Figure 13b the cumulative distribution of the size of the atoms of the LBC. The cumulative number of atoms is given as a percentage of the total number of atoms and the size of the atoms as a percentage of the total number of vertices in the LBC. Again, for all of the graphs, we observed one largest atom, that we call the LA. This atom includes from 50% to 60% of all the vertices, and all the other atoms only represent a small fraction of the overall vertices. In the worst case (ca-HepPh), all the atoms but the LA solely cover 2.65% of the vertices of the graph. Moreover, like for the smallest biconnected components and as reported in [START_REF] Cohen | Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs[END_REF], the substitute graphs of the smallest atoms can be safely ignored for the computation of hyperbolicity. As a Table 1: Characteristics of the collaboration networks. The size of the graph is given as n, the size of the LBC as n b , the size of the LA as n LA and the size of the LS as n LS . The percentage of vertices removed from the LBC to obtain the LA is given as R LA , the reduction rate is

R LS = n B -n LS n B
, and the percentage of vertices in the LBC, representing the addition of simplicial vertices, is given as Cost. Finally, the computation time of the substitution method, denoted by T ime, is given in seconds.

We reported in Table 1 as Cost the percentage of vertices in the LBC representing the addition of new simplicial vertices. We first observe the impact of the addition of new simplicial vertices on ca-CondMat which has the largest reduction rates R LS and R LA . Despite a R LA of 49.22%, ca-CondMat has almost the same reduction rate R LS as ca-HepPh and ca-GrQc |ranging from 20.55% to 20.84%|. This is the consequence of the addition of new simplicial vertices which represents 28.39% of the size of its LBC, whereas for the ca-HepPh graph it goes up to only 24.88%. A similar behavior is observed between ca-AstoPh and ca-CondMat: even though their R LA differ on 9.25%, the difference of their reduction rate R LS finally falls to 5%. This results from the addition of 4.24% less simplicial vertices in ca-AstoPh than in ca-CondMat. As an extremal case when looking at the ca-HepPh graph, the difference of 2.29% with the R LA of ca-GrQc is even compensated by the addition of 2.32% less simplicial vertices, resulting in a R LS smaller than for ca-GrQc. However, as another extremal case when comparing ca-HepTh to ca-CondMat, we notice that a large difference of 11.82% between their respective R LA is only marginally decreased by the addition of 2.21% less simplicial vertices for ca-HepTh than for ca-CondMat. The substitution method results in 9.61% more vertices for ca-HepTh than for ca-CondMat. We thus conclude that the impact of n LA and of the number of new simplicial vertices on the final size n LS differs greatly depending on the graph.

Inria

Decomposition analysis

Having noticed the heterogeneous results of our empirical section, we are now analyzing in more details the properties causing the asymmetry between the various ca-* graphs.

Clique-decomposition

We first analyzed the composition of the LA in terms of cliqueseparators. Let us denote by X LA = {X 1 , . . . , X l } the clique-minimal separators that are contained into the LA, disconnecting the atoms A LA = {A 1 , . . . , A l } from the LA, sequentially. We emphasize that there might be other atoms in the graph than the LA and those in A LA . But such atoms, if any, do not overlap the LA. Said differently, the set A LA represents the neighbourhood of the LA in the atom graph, as it is defined in [START_REF] Berry | Efficient clique decomposition of a graph into its atom graph[END_REF]. We plotted in Figure 14a the cumulative distribution of the size of the clique-separators in the LA as a percentage of the total number of clique-separators. By doing so, we observed smaller clique-separators for the ca-HepTh and ca-CondMat graphs, with a maximum size of 8 and 21, respectively, than for the three others graphs ca-GrQc, ca-AstroPh and ca-HepPh, having clique-separators of maximum size 42, 53 and 192, respectively. Also, we reported in Table 2 that the ratio R |X LA | of the number of clique-minimal separators |X LA | over the size n LA of the LA, varies from 0.39 for ca-AstroPh to 0.54 for ca-CondMat. To sum up, there are more clique-separators in ca-CondMat than in ca-AstropPh, but there are larger clique-separators in ca-AstropPh than in ca-CondMat.

To complete our measurements, we related the size of clique-separators with the proportion of vertices that are disconnected by them from the LA. We reported in Table 2 as α 1 = n Bn LA the total number of vertices separated from the LA in the LBC, as α 2 = |V (A LA \ X LA )| the number of vertices in the subset of atoms A LA which are not in the LA, and as |X LA | the number of clique-minimal separators in the LA. Finally, we computed the fraction ∆ 1 = α1-α2 n B , quantifying the percentage of vertices that are neither contained into the LA, nor in any of the atoms in A LA . We reported as ∆ 2 = R LA -∆ 1 the fraction of vertices in some atom of A LA , hence those that are directly separated from the LA.

Our results put in evidence that most of the vertices are either contained into the LA, or into some other atom intersecting the LA. Other vertices comprise around 2.88% and 7.03% of the overall vertices. Moreover, as shown with Figure 14b, where we plotted the percentage of separated vertices as a function of the size of clique-minimal separators, smaller clique-separators of size ≤ 5 are responsible for a significant part (w.r.t. ∆ 2 ) of the vertices disconnected from the LA in ca-CondMat (37.34% of vertices over 49.22%), whereas in ca-AstroPh they solely disconnect 23.67% over 39.98% of vertices. This difference is not balanced with clique-separators of larger size, even though these ones disconnect 13.43% of vertices in ca-AstroPh, while only 5.67% in ca-CondMat. A comparison of ca-CondMat with ca-HepPh yielded similar results. In contrast, for the graphs ca-GrQc and ca-HepTh, we notice that 6.71% and 4.91% more vertices, respectively, than in CondMat, are disconnected by edge-separators. But the rest of the cliqueminimal separators, of larger size, only disconnect 16.67% and 11.70% of the vertices, respectively, whereas 26.70% of them are separated in ca-CondMat. Therefore, most of the difference for the final size of the substitute graph LS comes from the number of vertices that are disconnected by clique-minimal separators of small size. We quantify the percentage of vertices that are neither contained into the LA nor in any of the atoms in A LA as ∆ 1 = α1-α2 n B ; the fraction of vertices in some atom of A LA that are directly separated from the LA is equal to ∆ 2 = R LA -∆ 1 .

Instance name

α 1 α 2 |X LA | R X LA ∆ 1 % ∆ 2 % ca-CondMat 8

Substitute construction

In order to validate our previous assumption, namely that the largest number of simplicial vertices are connected to the smallest clique-separators, we plotted in Figure 15a the cumulative number of simplicial vertices connected to the LA, normalized by the size of the LBC, as a function of the size of the clique-minimal separators. In particular, note that for each graph, such a summation is equal to the value given as Cost in Table 1. By looking only at clique-minimal separators of size two and three, the proportions of simplicial vertices for the graphs ca-CondMat, ca-GrQc, ca-HepPh, ca-AstroPh and ca-HepTh respectively, represent 65.49%, 88.63%, 76.26%, 50.16% and 88.02% respectively, of the total number of simplicial vertices connected to the LA. Thus it highlights the importance of clique-minimal separators of small size, to which a large proportion of simplicial vertices are connected to.

Let us also remark by comparing Figure 15a are connected to clique-separators of the same size. In the worst case (ca-GrQc), there are no more than 0.75% of the simplicial vertices whose degree differs from the others. Most of these simplicial vertices have degree two. Hence, the final proportion of simplicial vertices, given in Table 1 as Cost, mostly depends on the size distribution of the clique-separators in the graphs. Also, there is a worst-case variation of only 4.25% -between ca-CondMat and ca-AstroPh-in the proportion of simplicial vertices in our graphs, which allows us to make relative comparisons between them. Especially we are interested in comparing the proportion of simplicial vertices of small degree (less than four). Such a proportion represents, for ca-CondMat, ca-GrQc, ca-HepPh, ca-AstroPh and ca-HepTh respectively, a percentage of 18.59%, 24.1%, 18.97%, 12.11% and 23.04% respectively, of the simplicial vertices in total. To sum up:

• when comparing ca-AstroPh to ca-CondMat: even if the former has 2.23% more simplicial vertices with degree more than three, this is compensated by the 6.48% less simplicial vertices of degree less than four, which results in overall to 4.25% less simplicial vertices in ca-AstroPh than in ca-CondMat. The same happens when comparing ca-AstroPh to the remaining graphs. The lower number of simplicial vertices with degree less than four always compensates its larger number of simplicial vertices that are connected to clique-separators of larger size.

• when comparing ca-CondMat to ca-GrQc and ca-HepTh: the two latter graphs respectively have 5.51% and 4.45% more simplicial vertices with degree smaller than four. However, they respectively have 6.7% and 6.66% less simplicial vertices that are adjacent to cliqueseparators of size greater than three. As a result, there are 1.19% less simplicial vertices in ca-GrQc, and 2.21% less simplicial vertices in ca-HepTh, respectively, than in ca-CondMat.

• finally, when comparing ca-CondMat to ca-HepPh: we observe quite similar numbers of simplicial vertices that are connected to clique-separators of degree smaller than four. They respectively represent 18.59% and 18.97% of the simplicial vertices in total. Again, the main difference comes from the proportion of simplicial vertices with degree higher than three, with 5.91% more simplicial vertices in ca-CondMat than in ca-HepPh, resulting in 3.51% less vertices in ca-HepPh.

Our experiments on the ca-* graphs have highlighted the importance of the size of the largest atom, from which the largest substitute graph is always constructed. On the one hand in our examples, the three graphs ca-CondMat, ca-GrQc and ca-HepPh, which have the largest ratio R LA , also have the smallest ratio R LS . But on the other hand, the cost of adding new simplicial vertices to construct the LS can greatly compensate a smaller ratio R LA , as it is the case for ca-HepPh. Indeed this graph has a smaller ratio R LA than ca-GrQc, but it finally ends up with a larger ratio R LS . Finally, we observed on every graph of our experimentation that the degree distribution of the simplicial vertices follows the size distribution of the clique-separators. In particular, simplicial vertices of degree two and three always represent from 50.16% to 88.63% of the simplicial vertices in total.

Conclusion

In this work, we proved a tight relation between the hyperbolicity of a graph and the maximum hyperbolicity taken over all its atoms. Our result subsumes the one in [START_REF] Brinkmann | On the hyperbolicity of chordal graphs[END_REF], as it directly implies that chordal graphs are 1-hyperbolic. Also, it implies that two graph classes extending chordal graphs, namely 2-chordal graphs [START_REF] Mccullough | 2-chordal graphs[END_REF][START_REF] Mccullough | Minimal separators of 2-chordal graphs[END_REF] and clique-separable graphs [START_REF] Gavril | Algorithms on clique separable graphs[END_REF], have a bounded hyperbolicity.

In addition of our main result, we deduced from its proof a general substitution method, allowing us to modify the atoms at no extra-cost than the clique-decomposition; for graphs with hyperbolicity at least one, the maximum hyperbolicity taken over all the resulting graphs is exactly the hyperbolicity of the graphs, but the graphs to be considered may have a larger size than the atoms. Experiments suggest that the final size of the substitute graphs is mostly related with the number of clique-minimal separators of small size, and the disconnections resulting from them. We successfully applied this substitution method to outerplanar graphs, providing in this case a linear-time algorithm for computing the hyperbolicity. We let open whether the same can be done for other classes of graphs.

Finally, in the spirit of [START_REF] Baker | Approximation algorithms for NP-complete problems on planar graphs[END_REF], it would be of interest to take advantage of the linear-time algorithm for outerplanar graphs, in order to yield an efficient computation of the hyperbolicity of planar graphs. Part of our future work will also consist in finding other graph decompositions which are applicable to the computation of this parameter.

Inria

Figure 1 :

 1 Figure 1: Clique-decomposition of a graph into five atoms.

Lemma 4 .

 4 Let X be an (A|B)-clique-separator of a connected graph G, and let a ∈ A. If we add to G a vertex a * adjacent to {x ∈ X : d(a, x) = d(a, X)}, then for every b 1 , b 2 , b 3 ∈ B we have δ(a, b 1 , b 2 , b 3 ) = δ(a * , b 1 , b 2 , b 3 ). Proof. ∀x ∈ X, d(a, x) ∈ {d(a, X), d(a, X) + 1} holds as X is a clique. Consequently, for every b ∈ B, d(a, b) = d(a * , b) + d(a, X) -1 and replacing a with a * does not change the hyperbolicity of a, b 1 , b 2 , b 3 . Lemma 5. Let X be an (A|B)-clique-separator of a connected graph G. Given an (a|b 1 , b 2 , b 3

1 2 ,

 2 δ(G 1 ), . . . δ(G l )} + 1/2 holds for any a, b, c, d ∈ V . We consider a connected component C i maximizing |C i ∩ {a, b, c, d}|. • If |C i ∩ {a, b, c, d}| = 4 we are done as δ(a, b, c, d) ≤ δ(G i ). • If |C i ∩{a, b, c, d}| = 3 we can assume that a, b, c, d is an (a|b 1 , b 2 , b 3 ) 4-tuple, for the choices of B = C i ∪ X and A = V \ C i . By Lemma 5 it follows that δ(a, b, c, d) ≤ δ(G i ) + 1/2.

Figure 5 :

 5 Figure 5: X is an (A|B)-clique-separator: we have δ(G) = 3/2, while δ(G[B]) = 1, and δ(G[A]) = 0.

Figure 6 :

 6 Figure 6: A 2-hyperbolic graph with five atoms: four are 0-hyperbolic, one is 1-hyperbolic.

Figure 7 :

 7 Figure 7: An illustration of the metric property. The dashed lines represent shortest paths.

  and so is G B for G * B . It thus follows that max{δ(G * A ), δ(G * B )} ≥ max{δ(G A ), δ(G B )}. Let us now consider the 4-tuples of G which are separated by the disconnection. We recall that by Corollary 3, the hyperbolicity of any (a 1 , a 2 |b 1 , b 2 ) 4-tuple of G is bounded by 1. In addition, for every a ∈ A \ X, and for every b 1 , b 2 , b 3 ∈ B, there exists by construction a simplicial vertex a

  by Lemma 4. The proof is symmetric for b ∈ B \ X and a 1 , a 2 , a 3 ∈ A and it yields the expected result. To prove δ(G) ≥ max{1, δ(G * A ), δ(G * B )}, let us consider w.l.o.g. an arbitrary 4-tuple of G * B . If such a 4-tuple does not contain a simplicial vertex of G * B \ B, then we are done as it exists in the isometric subgraph G B of G. If it contains exactly one simplicial vertex a * ∈ G * B \ B, then by construction we can replace a * with a vertex a ∈ A \ X, satisfying N (a * ) = {x ∈ X : d G (a, x) = d G (a, X)}; this operation does not modify the hyperbolicity of the 4-tuple by Lemma 4. Finally, if it contains at least two simplicial vertices of G * B \ B, then it is an (a 1 , a 2 |b 1 , b 2 ) 4-tuple of G * B and so, the hyperbolicity is bounded by 1.

  X2 = {11, 18, 22} A2 = {11, 12, • • • , 22} X3 = {10, 23} A3 = {10, 11, 18, 22, 23} X4 = {5, 10, 23} A4 = {4, 5, 10, 23, 24} X5 = {6, 10, 23} A5 = {5, 6, 10, 23} A6 = {6, 7, 8, 9, 10, 23} (b) Atom tree of G

Figure 8 :

 8 Figure 8: A connected graph G (Figure8a), an atom tree of the graph (Figure8b), the substitute of the atoms of G (Figures8c-8h), and the characteristics of these graphs (Table8i).

Figure 9 :

 9 Figure 9: Characterization of 5-chordal 1 2 -hyperbolic graphs, in terms of forbidden isometric subgraphs.

Figure 10 :

 10 Figure 10: The forbidden subgraph of Figure 9b, and its characterization in the weak dual.

2 Figure 11 :

 211 Figure 11: Substitute graphs of the atoms of an outerplanar graph.

Figure 12 :

 12 Figure 12: An application of the substitution method to an outerplanar graph.

Figure 13 :

 13 Figure 13: Cumulative distributions of the size of the biconnected components (Figure13a) and of the atoms in the LBC of each graph (Figure13b).

Figure 14 :

 14 Figure 14: Cumulative distribution of the size of the clique-separators in the LA (Figure14a) and percentage of separated vertices as a function of the size of the clique-separators in the LA (Figure14b).

Figure 15 :

 15 Figure 15: Cumulative number of simplicial vertices connected to the LA normalized by the size of the LBC as a function of the size of the clique-separators to which they are connected (Figure 15a), cumulative degree distribution of the simplicial vertices connected to the LA normalized by the size of the LBC (Figure 15b)

  • Finally, if |C i ∩ {a, b, c, d}| ≤ 2 we can assume that a, b, c, d is an (a 1 , a 2 |b 1 , b 2 ) 4-tuple, for an appropriate merging of the sets C j ∪ X into two subsets A, B. We know by Corollary 3 that δ(a 1 , a 2 , b 1 , b 2 ) ≤ 1 in this case.

Table 2 :

 2 Distribution of clique-minimal separators, and of the vertices disconnected from the LA. The total number of vertices separated from the LA in the LBC is given as α 1 = n Bn LA , and the number of disconnected vertices being present in the subset of neighbouring atoms A LA asα 2 = |V (A LA \ X LA )|.Also, the number of clique-minimal separators in the LA is given as |X LA |.

		483 7 413 4 702	0.54	6.21% 43.01%
	ca-GrQc	1 265 1 079	698	0.5	7.03% 40.69%
	ca-HepPh	4 100 3 727 2 166	0.44	4.13% 41.3%
	ca-AstroPh	6 368 5 910 3 715	0.39	2.88% 37.1%
	ca-HepTh	2 206 1 942 1 506	0.41	4.47% 32.93%

RR n°8535

The characterization of[START_REF] Wu | Hyperbolicity and chordality of a graph[END_REF] is composed of six forbidden isometric subgraphs, but the sixth one is actually 6-chordal.Inria

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

* This work has been partially supported by ANR project Stint under reference ANR-13-BS02-0007, ANR program "Investments for the Future" under reference ANR-11-LABX-0031-01, and by European project FP7 EULER (Grant No.258307).

result, the only component of the graphs to deal with for computing their hyperbolicity is the substitute graph of the LA. We will denote it by LS in the sequel.

Size of the substitute graphs As explained in Section 5, the size of the LS depends on both the initial size of the LA and the number of added simplicial vertices. We have reported in Table 1 the original size n of each graph, the size n B of its LBC, the size n LA of the LA, and the size n LS of the largest substitute. We have then computed the percentage R LA of vertices that have been removed from the LBC to obtain the LA, that is

We observe a significant reduction rate R LA , varying from 37.40% to 49.22%. We have also computed the reduction rate R LS of the LS with respect to the LBC, that is

. We observe that this reduction rate falls between 11.22% and 20.84%. It indicates that the substitution method adds many simplicial vertices to the LA, when constructing the LS, despite the simplification rules that are presented in Section 5.