Guillaume Ducoffe
email: guillaume.ducoffe@ici.ro

Beyond Helly graphs: the diameter problem on absolute retracts

Keywords: absolute retract, chordal bipartite graphs, split graphs, planar graphs, diameter computation

A subgraph H of a graph G is called a retract of G if it is the image of some idempotent endomorphism of G. We say that H is an absolute retract of some graph class C if it is a retract of any G ∈ C of which it is an isochromatic and isometric subgraph. In this paper, we study the complexity of computing the diameter within the absolute retracts of various hereditary graph classes. First, we show how to compute the diameter within absolute retracts of bipartite graphs in randomized Õ(m √ n) time. Even on the proper subclass of cube-free modular graphs it is, to our best knowledge, the first subquadratic-time algorithm for diameter computation. For the special case of chordal bipartite graphs, it can be improved to linear time, and the algorithm even computes all the eccentricities. Then, we generalize these results to the absolute retracts of k-chromatic graphs, for every k ≥ 3. Finally, we study the diameter problem within the absolute retracts of planar graphs and split graphs.

Introduction

One of the most basic graph properties is the diameter of a graph (maximum number of edges on a shortest path). It is a rough estimate of the maximum delay in order to send a message in a communication network [START_REF] De Rumeur | Communications dans les réseaux de processeurs[END_REF], but it also got used in the literature for various other purposes [START_REF] Albert | Diameter of the world-wide web[END_REF][START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF]. The complexity of computing the diameter has received tremendous attention in the Graph Theory community [1, 14, 18, 20, 26, 25, 24, 29-31, 34, 43-45, 41, 47, 49, 65]. Indeed, while this can be done in O(nm) time for any n-vertex m-edge graph, via a simple reduction to breadth-first search, breaking this quadratic barrier (in the size n + m of the input) happens to be a challenging task. In fact, under plausible complexity assumptions such as the Strong Exponential-Time Hypothesis (SETH), the optimal running time for computing the diameter is essentially in O(nm) -up to sub-polynomial factors [START_REF] Roditty | Fast approximation algorithms for the diameter and radius of sparse graphs[END_REF]. This negative result holds even if we restrict ourselves to bipartite graphs or split graphs [START_REF] Abboud | Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs[END_REF][START_REF] Borassi | Into the square: On the complexity of some quadratic-time solvable problems[END_REF]. However, on the positive side, several recent works have identified important graph classes for which we can achieve for the diameter problem O(m 2-) time, or even better O(mn 1-) time, for some > 0. Next, we focus on a few such classes that are most relevant to our work. Specifically, we call G = (V, E) a Helly graph if every family of pairwise intersecting balls of G (of arbitrary radius and center) have a nonempty common intersection. The Helly graphs are a broad generalization of many better-known graph classes in Structural Graph Theory, such as: trees, interval graphs, strongly chordal graphs and dually chordal graphs [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF]. Furthermore, a celebrated theorem in Metric Graph Theory is that every graph is an isometric (distance-preserving) subgraph of some Helly graph [START_REF] Dress | Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces[END_REF][START_REF] Isbell | Six theorems about injective metric spaces[END_REF]. Other properties of Helly graphs were also thoroughly investigated in prior works [7, 8, 10, 23, 35-38, 63, 69, 70]. In particular, as far as we are concerned here, there is a randomized Õ(m √ n)-time algorithm in order to compute the diameter within n-vertex m-edge Helly graphs [START_REF] Ducoffe | A story of diameter[END_REF].

Recall that an endomorphism of a graph G is an edge-preserving mapping of G to itself. A retraction is an idempotent endomorphism. If H is the image of G by some retraction (in particular, H is a subgraph of G) then, we call H a retract of G. The notion of retract has applications in some discrete facility location problems [START_REF] Hell | Absolute retracts in graphs[END_REF], and it is useful in characterizing some important graph classes. For instance, the median graphs are exactly the retracts of hypercubes [START_REF] Bandelt | Retracts of hypercubes[END_REF]. We here focus on the relation between retracts and Helly graphs, that is as follows (for other classes related to the Helly graphs and considered recently, see [START_REF] Ducoffe | Distance problems within Helly graphs and k-Helly graphs[END_REF][START_REF] Chalopin | Helly groups[END_REF][START_REF] Dragan | Helly-gap of a graph and vertex eccentricities[END_REF][START_REF] Chepoi | Covering planar graphs with a fixed number of balls[END_REF][START_REF] Bousquet | VC-dimension and Erdős-Pósa property[END_REF][START_REF] Ducoffe | Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension[END_REF]). For some class C of reflexive graphs (i.e., with a loop at every vertex), let us define the absolute retracts of C as those H such that, whenever H is an isometric subgraph of some G ∈ C, H is a retract of G. Absolute retracts find their root in Geometry, where they got studied for various metric spaces [START_REF] Klisowski | A survey of various modifications of the notions of absolute retracts and absolute neighborhood retracts[END_REF]. In the special case of the class of all reflexive graphs, the absolute retracts are exactly the Helly (reflexive) graphs [START_REF] Hell | Absolute retracts and varieties of reflexive graphs[END_REF]. Motivated by this characterization of Helly graphs, and the results obtained in [START_REF] Ducoffe | A story of diameter[END_REF] for the diameter problem on this graph class, we here consider the following notion of absolute retracts, for irreflexive graphs. -Unless stated otherwise, all graphs considered in this paper are irreflexive. -Namely, let us first recall that a subgraph H of a graph G is isochromatic if it has the same chromatic number as G. Then, given a class of (irreflexive) graphs C, the absolute retracts of C are those H such that, whenever H is an isometric and isochromatic subgraph of some G ∈ C, H is a retract of G. We refer the reader to [START_REF] Bandelt | Absolute retracts of bipartite graphs[END_REF][START_REF] Bandelt | Absolute reflexive retracts and absolute bipartite retracts[END_REF][START_REF] Bandelt | Efficient characterizations of n-chromatic absolute retracts[END_REF][START_REF] Hell | Absolute retracts in graphs[END_REF][START_REF] Hell | Absolute planar retracts and the four color conjecture[END_REF][START_REF] Klavžar | Absolute retracts of split graphs[END_REF][START_REF] Kloks | On retracts, absolute retracts, and foldings in cographs[END_REF][START_REF] Loten | Absolute retracts and varieties generated by chordal graphs[END_REF][START_REF] Pesch | A characterization of absolute retracts of n-chromatic graphs[END_REF][START_REF] Pesch | Minimal extensions of graphs to absolute retracts[END_REF][START_REF] Pesch | Products of absolute retracts[END_REF], where this notion got studied for various graph classes.

Our results. In this paper, we prove new structural and algorithmic properties of the absolute retracts of various hereditary graph classes, such as: bipartite graphs, k-chromatic graphs (for any k ≥ 3), split graphs and planar graphs. Our focus is about the diameter problem on these graph classes but, on our way, we uncover several nice properties of the shortest-path distribution of their absolute retracts, that may be of independent interest. First, in Sec. 2, we consider the absolute retracts of bipartite graphs and some important subclasses of the latter. Recall that the diameter of a bipartite graph can unlikely be computed in subquadratic time. We prove that the diameter of absolute bipartite retracts can be computed in Õ(m √ n) time (Theorem 2). For that, we observe that in the square of such graph G, its two partite sets induce Helly graphs. This result complements the known relations between Helly graphs and absolute retracts of bipartite graphs [START_REF] Bandelt | Absolute reflexive retracts and absolute bipartite retracts[END_REF]. Then, roughly, we show how to compute the diameter of G from the diameter of both Helly graphs (actually, from the knowledge of the peripheral vertices in these graphs, i.e., their vertices with maximal eccentricity). Absolute bipartite retracts properly contain all cubefree modular graphs, and so, the cube-free median graphs and chordal bipartite graphs [START_REF] Bandelt | Absolute retracts of bipartite graphs[END_REF]. Therefore, as a byproduct of our Theorem 2, we get the first truly subquadratic-time algorithm for computing the diameter within the cube-free modular graphs. However, the structure of absolute bipartite retracts is far more complex than cube-free modular graphs: in fact, every bipartite graph is an isometric subgraph of some absolute bipartite retract [START_REF] Pesch | Minimal extensions of graphs to absolute retracts[END_REF].

Recently [START_REF] Dragan | Helly-gap of a graph and vertex eccentricities[END_REF], we announced an O(m √ n)-time algorithm in order to compute all the eccentricities in a Helly graph. However, extending this result to the absolute retracts of bipartite graphs appears to be a more challenging task. We manage to do so for the subclass of chordal bipartite graphs, for which we achieve a linear-time algorithm in order to compute all the eccentricities. For that, we use the stronger result that in the square of such graph, its two partite sets induce strongly chordal graphs.

In Sec. 3, we generalize our above framework to the absolute retracts of kchromatic graphs, for any k ≥ 3. Notice that we are not aware of any prior work showing the usefulness of (efficiently computable) proper colorings for faster diameter computation. Our positive results in Sec. 2 and 3 rely on some Hellytype properties of the graph classes considered. We complement those with a hardness result in Sec. 4, that hints that the weaker property of being an absolute retract of some well-structured graph class is not sufficient on its own for faster diameter computation. Specifically, we prove that under SETH, there is no O(mn 1-)-time algorithm for the diameter problem, for any > 0, on the class of absolute retracts of split graphs. This negative result follows from an elegant characterization of this subclass of split graphs in [START_REF] Klavžar | Absolute retracts of split graphs[END_REF].

Finally, in Sec. 5, we consider the absolute planar retracts. While there now exist several truly subquadratic-time algorithms for the diameter problem on all planar graphs [START_REF] Cabello | Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs[END_REF][START_REF] Ducoffe | Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension[END_REF][START_REF] Gawrychowski | Voronoi diagrams on planar graphs, and computing the diameter in deterministic Õ(n 5/3 ) time[END_REF] the existence of a quasi linear-time algorithm for this problem has remained so far elusive, and it is sometimes conjectured that no such algorithm exists [START_REF] Cabello | Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs[END_REF]. We give evidence that finding such algorithm for the absolute retracts of planar graphs is already a hard problem on its own. Specifically, we prove that every planar graph is an isometric subgraph of some absolute retract of planar graphs. This result mirrors the aforementioned property that every graph isometrically embeds in a Helly graph [START_REF] Dress | Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces[END_REF][START_REF] Isbell | Six theorems about injective metric spaces[END_REF].

Let us mention that all graph classes considered here are polynomial-time recognizable. For all that, we do not need to execute these recognition algorithms before we can compute the diameter of these graphs.

Notations. We mostly follow the graph terminology from [START_REF] Bondy | Graph theory[END_REF][START_REF] Diestel | Graph Theory[END_REF]. All graphs considered are finite, simple, unweighted and connected. For a graph G = (V, E), let the (open) neighbourhood of a vertex v be defined as

N G (v) = {u ∈ V | uv ∈ E} and its closed neighbourhood as N G [v] = N G (v)∪{v}. Similarly, for a vertex- subset S ⊆ V , let N G (S) = v∈S N G (v) \ S, and let N G [S] = N G (S) ∪ S.
The distance between two vertices u, v ∈ V equals the minimum number of edges on a uv-path, and it is denoted

d G (u, v). Let I G (u, v) = {w ∈ V | d G (u, v) = d G (u, w)+d G (w, v)}. The ball of center v and radius r is defined as N r G [v] = {u ∈ V | d G (u, v) ≤ r}. Furthermore, let the eccentricity of a vertex v be defined as e G (v) = max u∈V d G (u, v). The diameter and the radius of a graph G are defined as diam(G) = max v∈V e G (v) and rad(G) = min v∈V e G (v), respectively. A vertex v ∈ V is called central if e G (v) = rad(G), and peripheral if e G (v) = diam(G).
We introduce additional terminology where it is needed throughout the paper.

Bipartite graphs

The study of the absolute retracts of bipartite graphs dates back from Hell [START_REF] Hell | Rétractions de graphes[END_REF], and since then many characterizations of this graph class were proposed [START_REF] Bandelt | Absolute retracts of bipartite graphs[END_REF]. This section is devoted to the diameter problem on this graph class. In Sec. 2.1, we propose a randomized Õ(m √ n)-time algorithm for this problem. Then, we consider the chordal bipartite graphs in Sec. 2.2, that have been proved in [START_REF] Bandelt | Absolute retracts of bipartite graphs[END_REF] to be a subclass of the absolute retracts of bipartite graphs. For the chordal bipartite graphs, we present a deterministic linear-time algorithm in order to compute all the eccentricities. Before going further, let us introduce a few additional terminology. For a connected bipartite graph G, we denote its two partite sets by V 0 and V 1 . A half-ball is the intersection of a ball with one of the two partite sets of G. Finally, for i ∈ {0, 1}, let H i be the graph with vertex-set V i and an edge between every two vertices with a common neighbour in G.

Faster diameter computation

We start with the following characterization of the absolute bipartite retracts: E) is an absolute retract of bipartite graphs if and only if the collection of half-balls of G satisfies the Helly property.

Theorem 1 ([5]). G = (V,
This above Theorem 1 leads us to the following simple observation about the internal structure of the absolute retracts of bipartite graphs: E) is an absolute retract of bipartite graphs then both H 0 and H 1 are Helly graphs.

Lemma 1. If G = (V 0 ∪ V 1 ,
Next, we prove that in order to compute diam(G), with G an absolute retract of bipartite graphs, it is sufficient to compute the peripheral vertices of the Helly graphs H 0 and H 1 .

Lemma 2. If G = (V 0 ∪V 1 , E) is an absolute bipartite retract such that diam(H 0 ) ≤ diam(H 1 ) then, diam(G) ∈ {2diam(H 1 ), 2diam(H 1 )+1}. Moreover, if diam(G) ≥ 3 then we have diam(G) = 2diam(H 1 ) + 1 if and only if: -diam(H 1 ) = 1; -or diam(H 0 ) = diam(H 1 )
and, for some i ∈ {0, 1}, there exists a peripheral vertex of H i whose all neighbours in G are peripheral vertices of H 1-i .

The remaining of Sec. 2.1 is devoted to the computation of all the peripheral vertices in both Helly graphs H 0 and H 1 . While there exists a truly subquadratictime algorithm for computing the diameter of a Helly graph [START_REF] Ducoffe | A story of diameter[END_REF], we observe that in general, we cannot compute H 0 and H 1 in truly subquadratic time from G. Next, we adapt [43, Theorem 2], for the Helly graphs, to our needs. E) is an absolute bipartite retract then, for any k, we can compute in O(km) time the set of vertices of eccentricity at most k in H 0 (resp., in H 1 ). Proof (Sketch). By symmetry, we only need to prove the result for H 0 . Let U = {v ∈ V 0 | e H0 (v) ≤ k} be the set to be computed. We consider the more general problem of computing, for any t, a partition P t = (A t 1 , A t 2 , . . . , A t pt ) of V 0 , in an arbitrary number p t of subsets, subject to the following constraints:

Lemma 3. If G = (V 0 ∪ V 1 ,
-For every 1 ≤ i ≤ p t , let C t i := v∈A t i N t G [v]. Let B t i := C t i ∩ V 0 if t is even and let B t i := C t i ∩ V 1 if t is odd (for short, B t i = C t i ∩ V t (mod 2)
). We impose the sets B t i to be nonempty and pairwise disjoint.

Indeed, under these two conditions above, we have U = ∅ if and only if, for any partition P 2k as described above, p 2k = 1. Furthermore if it is the case then U = B 2k 1 . To construct the desired partition, we proceed by induction over t. If t = 0 then, let V 0 = {v 1 , v 2 , . . . , v p0 }. We just set P 0 = ({v 0 }, {v 1 }, . . . , {v p0 }) (each set is a singleton), and for every 1

≤ i ≤ p 0 let B 0 i = A 0 i = {v i }.
Else, we construct P t from P t-1 . Specifically, for every 1 ≤ i ≤ p t-1 , we let

W t i := N G (B t-1 i
). Then, starting from j := 0 and F := P t-1 , we proceed as follows until we have

F = ∅. We pick a vertex u s.t. #{i | A t-1 i ∈ F, u ∈ W t
i } is maximized (the maximality of u ensures that all sets B t i will be pairwise disjoint). Then, we set

A t j := {A t-1 i | A t-1 i ∈ F, u ∈ W t i } and B t j := {W t i | A t-1 i ∈ F, u ∈ W t i }.
We add the new subset A t j to P t , we remove all the subsets A t-1 i , u ∈ W t i from F, then we set j := j + 1. Overall, by using standard lists and pointer structures, each inductive step takes O(n + m) time.

The base case of our above induction is trivially correct. In order to prove correctness of our inductive step, we use Theorem 1 in order to prove that for each 1 ≤ i ≤ p t we get

W t i = V t (mod 2) ∩ v∈A t-1 i N t G [v]
. Doing so, for each subset A t j created at step t, we have

B t j = V t (mod 2) ∩ v∈A t j N t G [v]
, as desired. Finally, observe that all the subsets B t j are nonempty since they at least contain the vertex u ∈ V t (mod 2) that is selected in order to create A t j .

We use Lemma 3 when the diameters of H 0 and H 1 are in O( √ n). For larger values of diameters, we use a randomized procedure.

Lemma 4 (Theorem 3 in [START_REF] Ducoffe | A story of diameter[END_REF]). For a Helly graph H s.t. diam(H) > 3k = ω(log |V (H)|), one can compute with high probability its diameter and all the peripheral vertices in

Õ(|E(H)| • |V (H)|/k) time.
It is important to note that, in the algorithmic procedure of Lemma 4, we just need to perform a BFS from randomly selected vertices. As any BFS in H 0 or H 1 can be simulated with a BFS in G, we can implement this procedure in order to compute diam(H i ), for i ∈ {0, 1}, in Õ(mn/diam(H i )) time with high probability. Combined with Lemma 3, we get:

Theorem 2. If G = (V 0 ∪ V 1 , E
) is an absolute retract of bipartite graphs then, with high probability, we can compute diam(G) in Õ(m √ n) time.

We suspect that Theorem 2 can be derandomized by using a recent technique from [START_REF] Dragan | Helly-gap of a graph and vertex eccentricities[END_REF]Theorem 3]. This is left for future work.

Chordal bipartite graphs

We improve Theorem 2 for the special case of chordal bipartite graphs. Recall (amongst many characterizations) that a bipartite graph is chordal bipartite if and only if every induced cycle has length four [START_REF] Golumbic | Perfect elimination and chordal bipartite graphs[END_REF]. It was proved in [START_REF] Bandelt | Absolute retracts of bipartite graphs[END_REF] that every chordal bipartite graph is an absolute retract of bipartite graphs. Theorem 3. If G = (V, E) is chordal bipartite then we can compute all the eccentricities (and so, the diameter) in linear time.

We subdivide our proof of Theorem 3 into four main steps.

The chordal structure of the partite sets. A graph is chordal if it has no induced cycle of length more than three. It is strongly chordal if it is chordal and it does not contain any n-sun (n ≥ 3) as an induced subgraph [START_REF] Farber | Characterizations of strongly chordal graphs[END_REF]. We use the following characterization of the haf-sets of chordal bipartite graphs: E) is chordal bipartite, then H 0 and H 1 are strongly chordal graphs.

Lemma 5 ([62]). If G = (V 0 ∪ V 1 ,
Computation of a clique-tree. The same as in Sec. 2.1, in general we cannot compute H 0 and H 1 from G in subquadratic time. In order to overcome this issue, we use a more compact representation of the latter. Specifically, for a graph H = (V, E), a clique-tree is a tree T whose nodes are the maximal cliques of H and such that, for every v ∈ V , the maximal cliques of H containing v induce a connected subtree T v of T . It is well-known that H is chordal if and only if it has a clique-tree [START_REF] Buneman | A characterisation of rigid circuit graphs[END_REF][START_REF] Gavril | The intersection graphs of subtrees in trees are exactly the chordal graphs[END_REF][START_REF] Walter | Representations of rigid cycle graphs[END_REF]. By using standard results on dual hypertrees [START_REF] Beeri | On the desirability of acyclic database schemes[END_REF][START_REF] Tarjan | Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs[END_REF], we obtain that: E) is chordal bipartite then, we can compute a clique-tree for H 0 and H 1 in linear time.

Lemma 6. If G = (V 0 ∪ V 1 ,
Computation of all the eccentricities in the partite sets. Next, we propose a new algorithm in order to compute all the eccentricities of a strongly chordal graph H, being given a clique-tree. There already exist linear-time algorithms for computing all the eccentricities of a strongly chordal graphs, being given by its adjacency list [START_REF] Brandstädt | Dually chordal graphs[END_REF][START_REF] Dragan | Helly-gap of a graph and vertex eccentricities[END_REF][START_REF] Ducoffe | A story of diameter[END_REF]. However, in general these algorithms do not run in time linear in the size of a clique-tree. We often use in our proof the clique-vertex incidence graph of H, i.e., the bipartite graph I H whose partite sets are the vertices and the maximal cliques of H, and such that there is an edge between every vertex of H and every maximal clique of H containing it.

Let us first recall the following result about Helly graphs:

* ∈ N d H (v,C)-1 H [v] ∩ ( {N H (c) | c ∈ C, d H (v, c) = d H (v, C)}) (such vertex v * is called a gate of v).

Lemma 8 ([22]

). Every clique in a chordal graph is a gated set.

Lemma 9 ([43]

). If T is a clique-tree of a chordal graph H then, for every clique C of H, for every v / ∈ C we can compute d H (v, C) and a corresponding gate v * in total O(w(T )) time, where w(T ) denotes the sum of cardinalities of all the maximal cliques of H.

For every u, v ∈ V and k ≤ d H (u, v), the set L H (u, k, v) = {x ∈ I H (u, v) | d H (u, x) = k}
is called a slice. We also need the following result: Lemma 10 ( [START_REF] Chang | The k-domination and k-stability problems on sun-free chordal graphs[END_REF]). Every slice in a chordal graph is a clique. Now, consider the procedure described in Algorithm 1.

Lemma 11 (special case of Theorem 5 in [START_REF] Ducoffe | A story of diameter[END_REF]). Algorithm 1 outputs a central vertex of H.

Algorithm 1 Computation of a central vertex.

Require: A strongly chordal graph H. By using dynamic programming on a clique-tree in order to compute, for each candidate vertex c ∈ C, its number of neighbours in S, we get: Lemma 12. If T is a clique-tree of a strongly chordal graph H then, we can implement Algorithm 1 in order to run in O(w(T )) time, where w(T ) denotes the sum of cardinalities of all the maximal cliques of H.

We need one more result about the center of strongly chordal graphs: Lemma 13 ( [START_REF] Dragan | Centers of graphs and the Helly property[END_REF][START_REF] Dragan | Domination in quadrangle-free Helly graphs[END_REF]). If H is strongly chordal then, its center C(H) induces a strongly chordal graph of radius ≤ 1.

By Lemma 13, given a central vertex c of H, we can compute C(H) by local search in the neighbourhood at distance two around c. For doing that efficiently, we also need the following nice characterization of strongly chordal graphs. Recall that the clique-vertex incidence graph of H is a bipartite graph whose partite sets are the vertices and the maximal cliques of H, respectively; there is an edge between every vertex and every maximal clique in which this vertex is contained. Lemma 14 ([16, 46]). H is strongly chordal if and only if its clique-vertex incidence graph I H is chordal bipartite.

By Lemma 14, we can apply the techniques of Sec. 2.1 to the clique-vertex incidence graph of any strongly chordal H. In particular, by combining Lemma 3 with the dynamic programming technique of Lemma 12, we obtain:

Proposition 1. If T is a clique-tree of a strongly chordal graph H = (V, E) then, we can compute its center C(H) in O(w(T )) time.
Computation of all the eccentricities in G. Before proving Theorem 3, we need a final ingredient. Let us first generalize Lemma 2 as follows. E) is an absolute retract of bipartite graphs then, the following holds for every i ∈ {0, 1} and v ∈ V i :

Lemma 15. If G = (V 0 ∪ V 1 ,
-If e Hi (v) ≤ rad(H 1-i ) -1 then, e G (v) = 2e Hi (v) + 1 = 2rad(H 1-i ) -1. -If e Hi (v) = rad(H 1-i ) then, e G (v) = 2rad(H 1-i ) if and only if N G (v) ⊆ C(H 1-i ) and, for every u ∈ V 1-i , we have d H1-i (u, N G (v)) ≤ rad(H 1-i ) -1 (otherwise, e G (v) = 2rad(H 1-i ) + 1). -If e Hi (v) ≥ rad(H 1-i ) + 1 then, e G (v) = 2e Hi (v) if and only if we have e H1-i (u) < e Hi (v) for some u ∈ N G (v) (otherwise, e G (v) = 2e Hi (v) + 1).
Of the three cases in the above Lemma 15, the real algorithmic challenge is the case e Hi (v) = rad(H 1-i ), for some i ∈ {0, 1}. We solve this case by using similar techniques as for Proposition 1, which concludes the proof of Theorem 3.

k-chromatic graphs

Recall that a proper k-coloring of G = (V, E) is any mapping c : V → {1, 2, . . . , k} such that c(u) = c(v) for every edge uv ∈ E. The chromatic number of G is the least k such that it has a proper k-coloring, and a k-chromatic graph is a graph whose chromatic number is equal to k. We study the diameter problem within the absolute retracts of k-chromatic graphs, for every k ≥ 3.

Our approach requires such graphs to be equipped with a proper k-coloring. While this is a classic NP-hard problem for every k ≥ 3 [START_REF] Johnson | Computers and intractability: A guide to the theory of NP-completeness[END_REF], it can be done in polynomial time for absolute retracts of k-chromatic graphs [START_REF] Bandelt | Efficient characterizations of n-chromatic absolute retracts[END_REF]. By using a standard greedy coloring approach, we first improve this result as follows: Proposition 2. There is a linear-time algorithm such that, for every k ≥ 3, if the input G is an absolute retract of k-chromatic graphs, then it computes a proper k-coloring of G.

In the remainder of the section, we always assume the input graph G to be given with a proper k-coloring. We sometimes use the fact that, for an absolute retract, such proper k-coloring is unique up to permuting the colour classes [START_REF] Pesch | A characterization of absolute retracts of n-chromatic graphs[END_REF]. Now, let us recall the following characterization of absolute retracts: Theorem 4 ( [START_REF] Pesch | A characterization of absolute retracts of n-chromatic graphs[END_REF]). Let k ≥ 3. The graph G = (V, E) is an absolute retract of k-chromatic graphs if and only if for any proper k-coloring c, every peripheral vertex v is adjacent to all vertices u with c(u) = c(v), or it is covered1 and G \ v is an absolute retract of k-chromatic graphs.

A special case of Theorem 4 leads to a linear-time algorithm in order to decide whether an absolute k-chromatic retract has diameter at most two. For those graphs with diameter at least three, we propose a generalization of Lemma 2. Specifically, for each colour i, let

V i := {v ∈ V | c(v) = i} be called a colour class. For every v ∈ V i , e i (v) := max{d G (u, v) | u ∈ V i }. A vertex v ∈ V i is i-peripheral if it maximizes e i (v). Finally, let d i := max{e i (v) | v ∈ V i }.
Lemma 16. Let G = (V, E) be an absolute retract of k-chromatic graphs for some k ≥ 3, and let c be a corresponding proper k-coloring. Then, max 1≤i≤k d i ≤ diam(G) ≤ 1+max 1≤i≤k d i . Moreover, if diam(G) ≥ 3, then we have diam(G) = 1 + max 1≤i≤k d i if and only if:

either max 1≤i≤k d i = 2; or, for some i = j s.t. d i = d j is maximized, there is some i-peripheral vertex whose all neighbours coloured j are j-peripheral.

We end up sketching the computation, for each colour i, of the value d i and of the i-peripheral vertices. Our strategy is as follows. First, we prove that we can reduce our study to the case k = 3. This is done by using another, more algorithmic, characterization of absolute retracts [START_REF] Bandelt | Efficient characterizations of n-chromatic absolute retracts[END_REF].

Lemma 17. Let G = (V, E) be an absolute retract of k-chromatic graphs for some k ≥ 3, and let c be a corresponding proper k-coloring. For every distinct colours i 1 , i 2 , i 3 , the subgraph

H := G[V i1 ∪ V i2 ∪ V i3 ] is isometric. Moreover, H is an absolute retract of 3-chromatic graphs.
Next, we deal with the case when d i is sufficiently small. For that, we extend the techniques of Lemma 3 to the absolute 3-chromatic retracts. Correctness of our approach follows from the following property of these graphs: if v 1 , v 2 , . . . , v t are vertices coloured i then, for any r ≥ 2 and any colour j, the balls

N r G [v 1 ], N r G [v 2 ], . . . , N r G [v t ]
intersect in colour j if and only if they also intersect in colour i.

Lemma 18. Let G = (V, E) be an absolute retract of 3-chromatic graphs, and let c be a corresponding proper 3-coloring. For each colour i and D ≥ 2, we can compute in O(Dm) time the set U i := {v ∈ V i | e i (u) ≤ D}.

Finally, we address the case when d i is large. A function is called unimodal if every local minimum is also a global minimum. It is known that the eccentricity function of a Helly graph is unimodal [START_REF] Dragan | Centers of graphs and the Helly property[END_REF], and this property got used in [START_REF] Dragan | Helly-gap of a graph and vertex eccentricities[END_REF] in order to compute all the eccentricities in this graph class in subquadratic time. We prove that a similar, but weaker property holds for each colour class of absolute retracts: Lemma 19. Let G = (V, E) be an absolute retract of k-chromatic graphs for some k ≥ 3, and let c be a corresponding proper k-coloring. For each colour i and any u ∈

V i s.t. e i (u) ≥ (d i +5)/2 ≥ 7, there exists a u ∈ V i s.t. d G (u, u ) = 2 and e i (u ) = e i (u) -2.
We apply this almost-unimodality property to the computation of the d i 's: Lemma 20. Let G = (V, E) be an absolute retract of k-chromatic graphs for some k ≥ 3, let c be a corresponding proper k-coloring, and let i be such that d i ≥ 8D + 5 = ω(log n). Then, with high probability, we can compute in total Õ(mn/D) time the value d i and the i-peripheral vertices.

By combining Lemmas 17-20, we get: E) is an absolute k-chromatic retract, for some k ≥ 3, then we can compute its diameter with high probability in Õ(m √ n) time.

Theorem 5. If G = (V,

Split graphs

Recall that G = (V, E) is a split graph if its vertex-set V can be partitioned into a clique K and a stable set S. Such partition, that may not be unique, can be computed in linear time [START_REF] Golumbic | Algorithmic graph theory and perfect graphs[END_REF]. In contrast to Sec. 2 and 3, we prove that: Theorem 6. For any > 0, there exists a c( ) s.t., under SETH, we cannot compute the diameter in O(n 2-) time on the absolute retracts of split graphs of order n and clique-number at most c( ) log n.

Proof (Sketch). The result holds for general split graphs [START_REF] Borassi | Into the square: On the complexity of some quadratic-time solvable problems[END_REF]. Let G = (K +S, E) be any split graph. In order to decide whether diam(G) ≤ 2 or diam(G) = 3, we may remove first all vertices v s.t. N G (v) = K \ v (i.e., because e G (v) ≤ 2 and v is simplicial). By applying this above pruning rule until it can no more be done, we get a split graph G with a unique partition K + S [START_REF] Golumbic | Algorithmic graph theory and perfect graphs[END_REF]. All such graphs are absolute split retracts [START_REF] Klavžar | Absolute retracts of split graphs[END_REF].

Planar graphs

Our last (non-algorithmic) section is about the absolute retracts of planar graphs Theorem 7 ( [START_REF] Hell | Absolute planar retracts and the four color conjecture[END_REF]). A planar graph G is an absolute retract of planar graphs if and only if it is maximal planar and, in an embedding of G in the plane, any triangle bounding a face of G belongs to a subgraph of G isomorphic to K 4 .

To our best knowledge, there has been no relation uncovered between the absolute retracts of planar graphs and other important planar graph subclasses. We make a first step in this direction. Specifically, we prove the following two results.

Proposition 3. Every planar 3-tree is an absolute retract of planar graphs. Theorem 8. Every connected planar graph is an isometric subgraph of some absolute planar retract. In particular, there are absolute retracts of planar graphs with arbitrarily large treewidth.

We stress that the proof of Theorem 8 is constructive, and that it leads to a polynomial-time algorithm in order to construct an absolute planar retract in which the input planar graph G isometrically embeds. In contrast to our result, the smallest Helly graph in which a graph G isometrically embeds may be exponential in its size [START_REF] Guarnera | Injective hulls of various graph classes[END_REF].

The existence of an almost linear-time algorithm for computing the diameter of planar graphs is an important open problem. We see our Theorem 8 as evidence that answering to this problem for the absolute planar retracts would be already an important intermediate step toward a full resolution.

Lemma 7 (

 7 [START_REF] Dragan | Centers of graphs and the Helly property[END_REF]). If H is Helly then, for every vertex v we have e H (v) = d H (v, C(H)) + rad(H), where C(H) denotes the set of central vertices of H.Hence, by Lemma 7, we are left computing C(H). It starts with computing one central vertex. Define, for every vertex v and vertex-subset C, d H (v, C) = min c∈C d H (v, c). Following[START_REF] Chepoi | A linear-time algorithm for finding a central vertex of a chordal graph[END_REF], we call a set C gated if, for every v / ∈ C, there exists a vertex v

A vertex v is covered by another vertex w if NG(v) ⊆ NG(w) (a covered vertex is called embeddable in[START_REF] Pesch | A characterization of absolute retracts of n-chromatic graphs[END_REF]).

This work was supported by project PN-19-37-04-01 "New solutions for complex problems in current ICT research fields based on modelling and optimization", funded by the Romanian Core Program of the Ministry of Research and Innovation (MCI) 2019-2022.