# αi-Metric Graphs: Radius, Diameter and all Eccentricities

Feodor F Dragan, Guillaume Ducoffe

► To cite this version:

Feodor F Dragan, Guillaume Ducoffe. αi-Metric Graphs: Radius, Diameter and all Eccentricities. Graph-Theoretic Concepts in Computer Science (WG 2023), Jun 2023, Fribourg (CH), Switzerland. pp.276-290, 10.1007/978-3-031-43380-1_20. hal-04267646

HAL Id: hal-04267646

https://hal.science/hal-04267646v1

Submitted on 2 Nov 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# α<sub>i</sub>-Metric Graphs: Radius, Diameter and all Eccentricities *

Feodor F. Dragan<fnref n="1" /> and Guillaume Ducoffe<fnref n="2" />

**Abstract.** We extend known results on chordal graphs and distance-hereditary graphs to much larger graph classes by using only a common metric property of these graphs. Specifically, a graph is called α<sub>i</sub>-metric (i ∈ N) if it satisfies the following α<sub>i</sub>-metric property for every vertices u, w, v and x: if a shortest path between u and w and a shortest path between x and v share a terminal edge vw, then d(u, x) ≥ d(u, v)+d(v, x)−i. Roughly, gluing together any two shortest paths along a common terminal edge may not necessarily result in a shortest path but yields a "near-shortest" path with defect at most i. It is known that α<sub>0</sub>-metric graphs are exactly ptolemaic graphs, and that chordal graphs and distance-hereditary graphs are α<sub>i</sub>-metric for i = 1 and i = 2, respectively. We show that an additive O(i)-approximation of the radius, of the diameter, and in fact of all vertex eccentricities of an α<sub>i</sub>-metric graph can be computed in total linear time. Our strongest results are obtained for α<sub>1</sub>-metric graphs, for which we prove that a central vertex can be computed in subquadratic time, and even better in linear time for so-called (α<sub>1</sub>, Δ)-metric graphs (a superclass of chordal graphs and of plane triangulations with inner vertices of degree at least 7). The latter answers a question raised in (Dragan, *IPL*, 2020). Our algorithms follow from new results on centers and metric intervals of α<sub>i</sub>-metric graphs. In particular, we prove that the diameter of the center is at most 3i + 2 (at most 3, if i = 1). The latter partly answers a question raised in (Yushmanov & Chepoi, *Mathematical Problems in Cybernetics*, 1991).

**Keywords:** metric graph classes; chordal graphs; α<sub>i</sub>-metric; radius; diameter; vertex eccentricity; eccentricity approximating trees; approximation algorithms.

## 1 Introduction

Euclidean spaces have the following nice property: if the geodesic between u and w contains v, and the geodesic between v and x contains w, then their

<footnote n="1">¹ Computer Science Department, Kent State University, Kent, USA
[dragan@cs.kent.edu](mailto:dragan@cs.kent.edu)</footnote>

<footnote n="2">² National Institute for Research and Development in Informatics and University of Bucharest, Bucureşti, România [guillaume.ducoffe@ici.ro](mailto:guillaume.ducoffe@ici.ro)</footnote>

<footnote>* This work was supported by a grant of the Romanian Ministry of Research, Innovation and Digitalization, CCCDI - UEFISCDI, project number PN-III-P2-2.1-PED-2021-2142, within PNCDI III.</footnote>
union must be the geodesic between $u$ and $x$. In 1991, Chepoi and Yushmanov introduced $\alpha_i$-metric properties ($i \in \mathcal{N}$), as a way to quantify by how much a graph is close to satisfy this above requirement [54] (see also [14, 15] for earlier use of $\alpha_1$-metric property). All graphs $G = (V, E)$ occurring in this paper are connected, finite, unweighted, undirected, loopless and without multiple edges. The length of a path between two vertices $u$ and $v$ is the number of edges in the path. The distance $d_G(u, v)$ is the length of a shortest path connecting $u$ and $v$ in $G$. The interval $I_G(u, v)$ between $u$ and $v$ consists of all vertices on shortest $(u, v)$-paths, that is, it consists of all vertices (metrically) between $u$ and $v$: $I_G(u, v) = \{x \in V : d_G(u, x) + d_G(x, v) = d_G(u, v)\}$. Let also $I_G^o(u, v) = I_G(u, v) \setminus \{u, v\}$. If no confusion arises, we will omit subindex $G$.

**$\alpha_i$-metric property:** if $v \in I(u, w)$ and $w \in I(v, x)$ are adjacent, then
$$d(u, x) \ge d(u, v) + d(v, x) - i = d(u, v) + 1 + d(w, x) - i.$$

Roughly, gluing together any two shortest paths along a common terminal edge may not necessarily result in a shortest path (unlike in the Euclidean space) but yields a “near-shortest” path with defect at most $i$. A graph is called $\alpha_i$-metric if it satisfies the $\alpha_i$-metric property. $\alpha_i$-Metric graphs were investigated in [14, 15, 54]. In particular, it is known that $\alpha_0$-metric graphs are exactly the distance-hereditary chordal graphs, also known as ptolemaic graphs [46]. Furthermore, $\alpha_1$-metric graphs contain all chordal graphs [14] and all plane triangulations with inner vertices of degree at least 7 [32]. $\alpha_2$-Metric graphs contain all distance-hereditary graphs [54] and, even more strongly, all HHD-free graphs [18]. Evidently, every graph is an $\alpha_i$-metric graph for some $i$. Chepoi and Yushmanov in [54] also provided a characterization of all $\alpha_1$-metric graphs: They are exactly the graphs where all disks are convex and the graph $W_6^{++}$ from Fig. 1 is forbidden as an isometric subgraph (see [54] or Theorem 5). This nice characterization was heavily used in [4] in order to characterize $\delta$-hyperbolic graphs with $\delta \le 1/2$.

Let the eccentricity of a vertex $v$ in $G$ be defined as $e_G(v) = \max_{u \in V} d_G(u, v)$. The diameter and the radius of a graph are defined as $diam(G) = \max_{u \in V} e_G(u)$ and $rad(G) = \min_{u \in V} e_G(u)$, respectively. Let the center of a graph $G$ be defined as $C(G) = \{u \in V : e_G(u) = rad(G)\}$. Each vertex from $C(G)$ is called a central vertex. In this paper, we investigate the radius, diameter, and all eccentricities computation problems in $\alpha_i$-metric graphs. Understanding the eccentricity function of a graph and being able to efficiently compute or estimate the diameter, the radius, and all vertex eccentricities is of great importance. For example, in the analysis of complex networks, the eccentricity of a vertex is used to measure its importance: the eccentricity centrality index of $v$ [47] is defined as $\frac{1}{e(v)}$. Furthermore, the problem of finding a central vertex is one of the most famous facility location problems. In [54], the following nice relation between the diameter and the radius of an $\alpha_i$-metric graph $G$ was established: $diam(G) \ge 2rad(G) - i - 1$. Recall that for every graph $G$, $diam(G) \le 2rad(G)$ holds. Authors of [54] also raised a question<fnref n="1" /> whether the diameter of the center of an $\alpha_i$-metric graph can

<footnote n="1">¹ It is conjectured in [54] that $diam(C(G)) \le i + 2$ for every $\alpha_i$-metric graph $G$.</footnote>
be bounded by a linear function of $i$. It is known that the diameters of the centers of chordal graphs or of distance-hereditary graphs are at most 3 [15, 54].

**Related work.** There is a naive algorithm which runs a BFS from each vertex in order to compute all eccentricities. It has running time $O(nm)$ on an $n$-vertex $m$-edge graph. Interestingly, this is conditionally optimal for general graphs as well as for some restricted families of graphs [1, 6, 20, 50] since, under plausible complexity assumptions, neither the diameter nor the radius can be computed in truly subquadratic time (i.e., in $O(n^a m^b)$ time, for some positive $a, b$ such that $a+b < 2$). In a quest to break this quadratic barrier, there has been a long line of work presenting more efficient algorithms for computing the diameter and/or the radius, or even better all eccentricities, on some special graph classes. For example, linear-time algorithms are known for computing all eccentricities of interval graphs [34, 48]. Extensions of these results to several superclasses of interval graphs are also known [7, 10, 21, 22, 28, 36, 37, 39, 40]. Chordal graphs are another well-known generalization of interval graphs, for which the diameter can unlikely be computed in subquadratic time [6]. For all that, there is an elegant linear-time algorithm for computing the radius and a central vertex of a chordal graph [16]. Until this work there has been little insight about how to extend this nice result to larger graph classes (a notable exception being the work in [18]). This intriguing question is partly addressed in our paper.

Since the existence of subquadratic time algorithm for exact diameter or radius computation is unlikely, even for simple families of graphs, a large volume of work was also devoted to approximation algorithms [1, 3, 13, 50, 52]. Authors of [13] additionally address a more challenging question of obtaining an additive $c$-approximation for the diameter, i.e., an estimate $D$ such that $diam(G) - c \le D \le diam(G)$. A simple $\tilde{O}(mn^{1-\epsilon})$ time algorithm achieves an additive $n^\epsilon$-approximation and, for any $\epsilon > 0$, getting an additive $n^\epsilon$-approximation algorithm for the diameter running in $O(n^{2-\epsilon'})$ time for any $\epsilon' > 2\epsilon$ would falsify the Strong Exponential Time Hypothesis (SETH). However, much better additive approximations can be achieved for graphs with bounded (metric) parameters. For example, a vertex furthest from an arbitrary vertex has eccentricity at least $diam(G) - 2$ for chordal graphs [16] and at least $diam(G) - \lfloor k/2 \rfloor$ for $k$-chordal graphs [11]. Later, those results were generalized to all $\delta$-hyperbolic graphs [19, 20, 30, 31]. In [27], we also introduce a natural generalization of an $\alpha_i$-metric and weakly bridged graphs, which we call a $(\lambda, \mu)$-bow metric: namely, if two shortest paths $P(u, w)$ and $P(v, x)$ share a common shortest subpath $P(v, w)$ of length more than $\lambda$ (that is, they overlap by more than $\lambda$), then the distance between $u$ and $x$ is at least $d(u, v) + d(v, w) + d(w, x) - \mu$. $\delta$-Hyperbolic graphs are $(\delta, 2\delta)$-bow metric and $\alpha_i$-metric graphs are $(0, i)$-bow metric. $(\alpha_1, \Delta)$-Metric graphs form an important subclass of $\alpha_1$-metric graphs and contain all chordal graphs and all plane triangulations with inner vertices of degree at least 7. In [32], it was shown that every $(\alpha_1, \Delta)$-metric graph admits an eccentricity 2-approximating spanning tree, i.e., a spanning tree $T$ such that $e_T(v) - e_G(v) \le 2$ for every vertex $v$. Finding similar results for general $\alpha_1$-metric graphs was left as an open problem in [32].
**Our Contribution.** We prove several new results on intervals, eccentricity and centers in $\alpha_i$-metric graphs, and their algorithmic applications, thus answering open questions in the literature [25, 32, 54]. To list our contributions, we need to introduce on our way some additional notations and terminology.

Section 2 is devoted to general $\alpha_i$-metric graphs ($i \ge 0$). The set $S_k(u, v) = \{x \in I(u, v) : d(u, x) = k\}$ is called a *slice* of the interval $I(u, v)$ where $0 \le k \le d(u, v)$. An interval $I(u, v)$ is said to be $\lambda$-thin if $d(x, y) \le \lambda$ for all $x, y \in S_k(u, v)$, $0 < k < d(u, v)$. The smallest integer $\lambda$ for which all intervals of $G$ are $\lambda$-thin is called the *interval thinness* of $G$. The disk of radius $r$ and center $v$ is defined as $\{u \in V : d(u, v) \le r\}$, and denoted by $D(v, r)$. In particular, $N[v] = D(v, 1)$ and $N(v) = N[v] \setminus \{v\}$ denote the closed and open neighbourhoods of a vertex $v$, respectively. More generally, for any vertex-subset $S$ and a vertex $u$, we define $d(u, S) = \min_{v \in S} d(u, v)$, $D(S, r) = \bigcup_{v \in S} D(v, r)$, $N[S] = D(S, 1)$ and $N(S) = N[S] \setminus S$. We say that a set of vertices $S \subseteq V$ of a graph $G = (V, E)$ is $d^k$-convex if for every two vertices $x, y \in S$ with $d(x, y) \ge k \ge 0$, the entire interval $I(x, y)$ is in $S$. For $k \le 2$, this definition coincides with the usual definition of convex sets in graphs [5, 14, 51]. We show first that, in $\alpha_i$-metric graphs $G$, the intervals are $(i+1)$-thin, and the disks (and, hence, the centers $C(G)$) are $d^{2i-1}$-convex. The main result of Section 2.1 states that the diameter of the center $C(G)$ of $G$ is at most $3i+2$, thus answering a question raised in [54].

Let $F_G(v)$ be the set of all vertices of $G$ that are most distant from $v$. A pair $x, y$ is called a pair of mutually distant vertices if $x \in F_G(y)$, $y \in F_G(x)$. In Section 2.2, we show that an additive $O(i)$-approximation of the radius and of the diameter of an $\alpha_i$-metric graph $G$ with $m$ edges can be computed in $O(m)$ time. For that, we carefully analyze the eccentricities of most distant vertices from an arbitrary vertex and of mutually distant vertices. In Section 2.3, we present three approximation algorithms for all eccentricities, with various trade-offs between their running time and the quality of their approximation. Hence, an additive $O(i)$-approximation of all vertex eccentricities of an $\alpha_i$-metric graph $G$ with $m$ edges can be computed in $O(m)$ time.

Section 3 is devoted to $\alpha_1$-metric graphs. The eccentricity function $e(v)$ of a graph $G$ is said to be *unimodal*, if for every non-central vertex $v$ of $G$ there is a neighbor $u \in N(v)$ such that $e(u) < e(v)$ (that is, every local minimum of the eccentricity function is a global minimum). We show in Section 3.1 that the eccentricity function on $\alpha_1$-metric graphs is almost unimodal and we characterize non-central vertices that violate the unimodality (that is, do not have a neighbor with smaller eccentricity). Such behavior of the eccentricity function was observed earlier in chordal graphs [32], in distance-hereditary graphs [29] and in all $(\alpha_1, \Delta)$-metric graphs [32]. In Section 3.2, we show that the diameter of $C(G)$ is at most 3. This generalizes known results for chordal graphs [15] and for $(\alpha_1, \Delta)$-metric graphs [32]. Finally, based on these results we present in Section 3.3 a local-search algorithm for finding a central vertex of an arbitrary $\alpha_1$-metric graph in subquadratic time. Our algorithm even achieves linear runtime on $(\alpha_1, \Delta)$-metric graphs, thus answering an open question from [32].

All omitted proofs can be found in our technical report [26].
## 2 General case of $\alpha_i$-metric graphs for arbitrary $i \ge 0$

First we present two important lemmas for what follows.

**Lemma 1.** Let $G$ be an $\alpha_i$-metric graph, and let $u, v, x, y$ be vertices such that $x \in I(u, v)$, $d(u, x) = d(u, y)$, and $d(v, y) \le d(v, x)+k$. Then, $d(x, y) \le k+i+2$.

**Lemma 2.** If $G$ is an $\alpha_i$-metric graph, then its interval thinness is at most $i+1$.

### 2.1 Centers of $\alpha_i$-metric graphs

We provide an answer to a question raised in [54] whether the diameter of the center of an $\alpha_i$-metric graph can be bounded by a linear function of $i$. For that, we show first that every disk must be $d^{2i-1}$-convex.

**Lemma 3.** Every disk of an $\alpha_i$-metric graph $G$ is $d^{2i-1}$-convex. In particular, the center $C(G)$ of an $\alpha_i$-metric graph $G$ is $d^{2i-1}$-convex.

Next auxiliary lemma is crucial in obtaining many results of this section.

**Lemma 4.** Let $G$ be an $\alpha_i$-metric graph. For any $x, y, v \in V$ and any integer $k \in \{0, \dots, d(x, y)\}$, there is a vertex $c \in S_k(x, y)$ such that $d(v, c) \le \max\{d(v, x), d(v, y)\} - \min\{d(x, c), d(y, c)\} + i$ and $d(v, c) \le \max\{d(v, x), d(v, y)\} + i/2$. For an arbitrary vertex $z \in I(x, y)$, we have $d(z, v) \le \max\{d(x, v), d(y, v)\} - \min\{d(x, z), d(y, z)\} + 2i + 1$ and $d(z, v) \le \max\{d(x, v), d(y, v)\} + 3i/2 + 1$. Furthermore, $e(z) \le \max\{e(x), e(y)\} - \min\{d(x, z), d(y, z)\} + 2i + 1$ and $e(z) \le \max\{e(x), e(y)\} + 3i/2 + 1$ when $v \in F(z)$.

Using Lemma 4, one can easily prove that the diameter of the center $C(G)$ of an $\alpha_i$-metric graph $G$ is at most $4i + 3$. Below we improve the bound.

**Theorem 1.** If $G$ is an $\alpha_i$-metric graph, then $\text{diam}(C(G)) \le 3i + 2$.

*Proof.* Let $r = \text{rad}(G)$. Suppose by contradiction $\text{diam}(C(G)) > 3i + 2$. Since $C(G)$ is $d^{2i-1}$-convex, there exist $x, y \in C(G)$ such that $d(x, y) = 3i + 3$ and $I(x, y) \subseteq C(G)$. Furthermore, for every $u \in V$ such that $\max\{d(u, x), d(u, y)\} < r$, $I(x, y) \subseteq D(u, r-1)$ because the latter disk is also $d^{2i-1}$-convex. Therefore, for every $z \in I(x, y)$, $F(z) \subseteq F(x) \cup F(y)$. Let $ab$ be an edge on a shortest $xy$-path such that $d(a, x) < d(b, x)$. Assume $F(b) \not\subseteq F(a)$. Let $v \in F(b) \setminus F(a)$. Since $G$ is $\alpha_i$-metric, $d(v, y) \ge d(v, b) + d(b, y) - i = r + (d(b, y) - i)$. Therefore, $d(b, y) \le i$. In the same way, if $F(a) \not\subseteq F(b)$, then $d(a, x) \le i$. By induction, $F(z) \subseteq F(x)$ ($F(z) \subseteq F(y)$, respectively) for every $z \in I(x, y)$ such that $d(y, z) \ge i + 1$ ($d(x, z) \ge i + 1$, respectively). In particular, if $i + 1 \le t \le d(x, y) - i - 1$, then $F(z) \subseteq F(x) \cap F(y)$ for every $z \in S_t(x, y)$. Note that the above properties are also true for every $x', y' \in C(G)$ with $d(x', y') \ge 2i - 1$, as $d^{2i-1}$-convexity argument can still be used.

Let $c \in I(x, y)$ be such that $F(c) \subseteq F(x) \cap F(y)$ and $k := |F(c)|$ is minimized. We claim that $k < |F(x) \cap F(y)|$. Indeed, let $v \in F(x) \cap F(y)$ be arbitrary.
By Lemma 4, some vertex $c_v \in S_{i+1}(x, y)$ satisfies $d(c_v, v) \le r - 1$. Then, $F(c_v) \subseteq (F(x) \cap F(y)) \setminus \{v\}$, and $k \le |F(c_v)| \le |F(x) \cap F(y)| - 1$ by minimality of $c$. Let $y_c \in I(x, y)$ be such that $F(y_c) \cap F(x) \cap F(y) \subseteq F(c)$ and $d(x, y_c)$ is maximized. We have $y_c \ne y$ because $F(x) \cap F(y) \not\subseteq F(c)$. Therefore, the maximality of $d(x, y_c)$ implies the existence of some $v \in (F(x) \cap F(y)) \setminus F(c)$ such that $d(v, y_c) = r - 1$. Since $G$ is $\alpha_i$-metric, $d(v, y) \ge d(v, y_c) + d(y_c, y) - i = r + (d(y_c, y) - i - 1)$. As a result, $d(y_c, y) \le i + 1$. Then, for every $z \in S_{i+1}(x, y_c)$, since we have $d(z, y_c) = d(x, y) - i - 1 - d(y_c, y) \ge d(x, y) - 2i - 2 = i + 1$, $F(z) \subseteq F(x) \cap F(y) \cap F(y_c) \subseteq F(c)$. By minimality of $k$, $F(z) = F(c)$. However, let $v \in F(c)$ be arbitrary. By Lemma 4, there exists some $c' \in S_{i+1}(x, y_c)$ such that $d(c', v) \le r - 1$, thus contradicting $F(c') = F(c)$. $\square$

## 2.2 Approximating radii and diameters of $\alpha_i$-metric graphs

In this subsection, we show that a vertex with eccentricity at most $rad(G) + O(i)$ and a vertex with eccentricity at least $diam(G) - O(i)$ of an $\alpha_i$-metric graph $G$ can be found in parameterized linear time. We summarize algorithmic results of this section in the following theorem.

**Theorem 2.** There is a linear ($O(m)$) time algorithm which finds vertices $v$ and $c$ of an $m$-edge $\alpha_i$-metric graph $G$ such that $e(v) \ge diam(G) - 5i - 2$, $e(c) \le rad(G) + 4i + (i+1)/2 + 2$ and $C(G) \subseteq D(c, 4i + (i+1)/2 + 2)$. Furthermore, there is an almost linear ($O(im)$) time algorithm which finds vertices $v$ and $c$ of $G$ such that $e(v) \ge diam(G) - 3i - 2$, $e(c) \le rad(G) + 2i + 1$ and $C(G) \subseteq D(c, 4i + 3)$.

Our algorithms are derived from the following new properties of an $\alpha_i$-metric graph $G$, whose proofs are omitted due to lack of space.

- Let $x, y$ be a pair of mutually distant vertices. Then, $d(x, y) \ge 2rad(G) - 4i - 3$ and $d(x, y) \ge diam(G) - 3i - 2$. Furthermore, any middle vertex $z$ of a shortest path between $x$ and $y$ satisfies $e(z) \le \lceil d(x, y)/2 \rceil + 2i + 1 \le rad(G) + 2i + 1$, and $C(G) \subseteq D(z, 4i + 3)$. There is also a vertex $c$ in $S_{\lfloor d(x,y)/2 \rfloor}(x, y)$ with $e(c) \le rad(G) + i$.

- Let $v \in V$, $x \in F(v)$ and $y \in F(x)$. Then, $e(x) = d(x, y) \ge 2rad(G) - 2i - diam(C(G)) \ge 2rad(G) - 5i - 2 \ge diam(G) - 5i - 2$. Furthermore, any middle vertex $z$ of a shortest path between $x$ and $y$ satisfies $e(z) \le \min\{rad(G) + 4i + (i+1)/2 + 2, \lceil d(x, y)/2 \rceil + 7i + 3\}$ and $C(G) \subseteq D(z, 4i + (i+1)/2 + 2)$.

In particular, using at most $O(i)$ breadth-first-searches, one can generate a sequence of vertices $v := v_0, x := v_1, y := v_2, v_3, \dots, v_k$ with $k \le 5i + 4$ such that each $v_i$ is most distant from $v_{i-1}$ and $v_k$, $v_{k-1}$ are mutually distant vertices (because the initial value $d(x, y) \ge diam(G) - 5i - 2$ can be improved at most $5i + 2$ times). Therefore, a pair of mutually distant vertices of an $\alpha_i$-metric graph can be computed in $O(im)$ total time, thus proving Theorem 2.

For every vertex $v \in V \setminus C(G)$ of a graph $G$ we can define a parameter $loc(v) = \min\{d(v, x) : x \in V, e(x) < e(v)\}$ and call it the *locality of $v$*. It shows how far from $v$ a vertex with a smaller eccentricity than that one of $v$ exists. In $\alpha_i$-metric graphs, the locality of each vertex is at most $i + 1$.
**Lemma 5.** Let $G$ be an $\alpha_i$-metric graph. Then, for every vertex $v$, $\text{loc}(v) \le i+1$.

In $\alpha_i$-metric graphs, the difference between the eccentricity of a vertex $v$ and the radius of $G$ shows how far vertex $v$ can be from the center $C(G)$ of $G$.

**Lemma 6.** Let $G$ be an $\alpha_i$-metric graph and $k$ be a positive integer. Then, for every vertex $v$ of $G$ with $e(v) \le \text{rad}(G) + k$, $d(v, C(G)) \le k + i$.

*Proof.* Let $x$ be a vertex from $C(G)$ closest to $v$. Consider a neighbor $z$ of $x$ on an arbitrary shortest path from $x$ to $v$. Necessarily, $e(z) = e(x) + 1 = \text{rad}(G) + 1$. Consider a vertex $u \in F(z)$. We have $d(u, x) = \text{rad}(G)$ and $x \in I(z, u)$, $z \in I(x, v)$. By the $\alpha_i$-metric property, $d(v, u) \ge d(v, x) + d(x, u) - i = d(v, x) - i + \text{rad}(G)$. As $e(v) \ge d(v, u)$ and $e(v) \le \text{rad}(G) + k$, we get $\text{rad}(G) + k \ge e(v) \ge d(v, x) - i + \text{rad}(G)$, i.e., $d(v, x) \le i + k$. $\square$

As an immediate corollary of Lemma 6 we get.

**Corollary 1.** Let $G$ be an $\alpha_i$-metric graph. Then, for every vertex $v$ of $G$, $d(v, C(G)) + \text{rad}(G) \ge e(v) \ge d(v, C(G)) + \text{rad}(G) - i$.

So, in $\alpha_i$-metric graphs, to approximate the eccentricity of a vertex $v$ up-to an additive one-sided error $i$, one needs to know only $\text{rad}(G)$ and the distance from $v$ to the center $C(G)$ of $G$.

## 2.3 Approximating all eccentricities in $\alpha_i$-metric graphs

In this subsection, we show that the eccentricities of all vertices of an $\alpha_i$-metric graph $G$ can be approximated with an additive one-sided error at most $O(i)$ in (almost) linear total time. The following first result is derived from the interesting property that the distances from any vertex $v$ to two mutually distant vertices give a very good estimation on the eccentricity of $v$.

**Theorem 3.** Let $G$ be an $\alpha_i$-metric graph with $m$-edges. There is an algorithm which in total almost linear ($O(im)$) time outputs for every vertex $v \in V$ an estimate $\hat{e}(v)$ of its eccentricity $e(v)$ such that $e(v) - 3i - 2 \le \hat{e}(v) \le e(v)$.

A spanning tree $T$ of a graph $G$ is called an *eccentricity k-approximating spanning tree* if for every vertex $v$ of $G$ $e_T(v) \le e_G(v) + k$ holds [49]. All $(\alpha_1, \Delta)$-metric graphs (including chordal graphs and the underlying graphs of 7-systolic complexes) admit eccentricity 2-approximating spanning trees [32]. An eccentricity 2-approximating spanning tree of a chordal graph can be computed in linear time [25]. An eccentricity $k$-approximating spanning tree with minimum $k$ can be found in $O(nm)$ time for any $n$-vertex, $m$-edge graph $G$ [35]. It is also known [20, 30] that if $G$ is a $\delta$-hyperbolic graph, then $G$ admits an eccentricity $(4\delta + 1)$-approximating spanning tree constructible in $O(\delta m)$ time and an eccentricity $(6\delta)$-approximating spanning tree constructible in $O(m)$ time.
**Lemma 7.** Let $G$ be an $\alpha_i$-metric graph with $m$ edges. If $c$ is a middle vertex of any shortest path between a pair $x, y$ of mutually distant vertices of $G$ and $T$ is a BFS(c)-tree of $G$, then, for every vertex $v$ of $G$, $e_G(v) \le e_T(v) \le e_G(v) + 4i + 2$. That is, $G$ admits an eccentricity $(4i + 2)$-approximating spanning tree constructible in $O(im)$ time.

**Lemma 8.** Let $G$ be an $\alpha_i$-metric graph with $m$ edges, and let $z \in V$, $x \in F(z)$ and $y \in F(x)$. If $c$ is a middle vertex of any shortest path between $x$ and $y$ and $T$ is a BFS(c)-tree of $G$, then, for every vertex $v$ of $G$, $e_G(v) \le e_T(v) \le e_G(v) + 9i + 5$. That is, $G$ admits an eccentricity $(9i + 5)$-approximating spanning tree constructible in $O(m)$ time.

It is a folklore by now that the eccentricities of all vertices in any tree $T = (V, U)$ can be computed in $O(|V|)$ total time. Consequently, by Lemma 7 and Lemma 8, we get the following additive approximations for the vertex eccentricities in $\alpha_i$-metric graphs.

**Theorem 4.** Let $G$ be an $\alpha_i$-metric graph with $m$ edges. There is an algorithm which in total linear $(O(m))$ time outputs for every vertex $v \in V$ an estimate $\hat{e}(v)$ of its eccentricity $e(v)$ such that $e(v) \le \hat{e}(v) \le e(v) + 9i + 5$. Furthermore, there is an algorithm which in total almost linear $(O(im))$ time outputs for every vertex $v \in V$ an estimate $\hat{e}(v)$ of its eccentricity $e(v)$ such that $e(v) \le \hat{e}(v) \le e(v) + 4i + 2$.

### 3 Graphs with $\alpha_1$-metric

Now we concentrate on $\alpha_1$-metric graphs, which contain all chordal graphs and all plane triangulations with inner vertices of degree at least 7 (see [14, 15, 32, 54]). For them we get much sharper bounds. First we recall some known results.

**Theorem 5 ([54]).** $G$ is an $\alpha_1$-metric graph if and only if all disks $D(v, k)$ ($v \in V, k \ge 1$) of $G$ are convex and $G$ does not contain the graph $W_6^{++}$ from Fig. 1 as an isometric subgraph.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Forbidden isometric subgraph $W_6^{++}$.</figcaption></figure>

**Lemma 9 ([51]).** All disks $D(v, k)$ ($v \in V, k \ge 1$) of a graph $G$ are convex if and only if for every vertices $x, y, z \in V$ and $v \in I(x, y)$, $d(v, z) \le \max\{d(x, z), d(y, z)\}$.

Letting $z$ to be from $F(v)$, we get:

**Corollary 2.** If all disks $D(v, k)$ ($v \in V, k \ge 1$) of a graph $G$ are convex then for every vertices $x, y \in V$ and $v \in I(x, y)$, $e(v) \le \max\{e(x), e(y)\}$.
**Lemma 10 ([32]).** Let $G$ be an $\alpha_1$-metric graph and $x$ be its arbitrary vertex with $e(x) \ge \text{rad}(G) + 1$. Then, for every vertex $z \in F(x)$ and every neighbor $v$ of $x$ in $I(x, z)$, $e(v) \le e(x)$ holds.

**3.1 The eccentricity function on $\alpha_1$-metric graphs is almost**
**unimodal**

We prove the following theorem.

**Theorem 6.** Let $G$ be an $\alpha_1$-metric graph and $v$ be an arbitrary vertex of $G$. If

(i) $e(v) > \text{rad}(G) + 1$ or

(ii) $e(v) = \text{rad}(G) + 1$ and $\text{diam}(G) < 2\text{rad}(G) - 1$,

then there must exist a neighbor $w$ of $v$ with $e(w) < e(v)$.

Theorem 6 says that if a vertex $v$ with $\text{loc}(v) > 1$ exists in an $\alpha_1$-metric graph $G$ then $\text{diam}(G) \ge 2\text{rad}(G) - 1$, $e(v) = \text{rad}(G) + 1$ and $d(v, C(G)) = 2$. Two $\alpha_1$-metric graphs depicted in Fig. 2 show that this result is sharp.

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** Sharpness of the result of Theorem 6. (a) An $\alpha_1$-metric graph $G$ with $\text{diam}(G) = 2\text{rad}(G) - 1$ and a vertex (topmost) with locality 2. (b) A chordal graph (and hence an $\alpha_1$-metric graph) $G$ with $\text{diam}(G) = 2\text{rad}(G)$ and a vertex (topmost) with locality 2. The number next to each vertex indicates its eccentricity.</figcaption></figure>

We formulate three interesting corollaries of Theorem 6.

**Corollary 3.** Let $G$ be an $\alpha_1$-metric graph. Then,

(i) if $\text{diam}(G) < 2\text{rad}(G) - 1$ (i.e., $\text{diam}(G) = 2\text{rad}(G) - 2$) then every local minimum of the eccentricity function on $G$ is a global minimum.

(ii) if $\text{diam}(G) \ge 2\text{rad}(G) - 1$ then every local minimum of the eccentricity function on $G$ is a global minimum or is at distance 2 from a global minimum.

**Corollary 4.** For every $\alpha_1$-metric graph $G$ and any vertex $v$, the following formula is true: $d(v, C(G)) + \text{rad}(G) \ge e(v) \ge d(v, C(G)) + \text{rad}(G) - \epsilon$, where $\epsilon \le 1$, if $\text{diam}(G) \ge 2\text{rad}(G) - 1$, and $\epsilon = 0$, otherwise.

A path $(v = v_0, \dots, v_k = x)$ of a graph $G$ from a vertex $v$ to a vertex $x$ is called *strictly decreasing* (with respect to the eccentricity function) if for every $i$ ($0 \le i \le k-1$), $e(v_i) > e(v_{i+1})$. It is called *decreasing* if for every $i$ ($0 \le i \le k-1$), $e(v_i) \ge e(v_{i+1})$. An edge $ab \in E$ of a graph $G$ is called *horizontal* (with respect to the eccentricity function) if $e(a) = e(b)$.
**Corollary 5.** Let $G$ be an $\alpha_1$-metric graph and $v$ be an arbitrary vertex. Then, there is a shortest path $P(v,x)$ from $v$ to a closest vertex $x$ in $C(G)$ such that:

(i) if $\mathrm{diam}(G) < 2\mathrm{rad}(G) - 1$ (i.e., $\mathrm{diam}(G) = 2\mathrm{rad}(G) - 2$) then $P(v,x)$ is strictly decreasing;

(ii) if $\mathrm{diam}(G) \ge 2\mathrm{rad}(G) - 1$ then $P(v,x)$ is decreasing and can have only one horizontal edge, with an end-vertex adjacent to $x$.

## 3.2 Diameters of centers of $\alpha_1$-metric graphs

In this section, we provide sharp bounds on the diameter and the radius of the center of an $\alpha_1$-metric graph. Previously, it was known that the diameter (the radius) of the center of a chordal graph is at most 3 (at most 2, respectively) [15]. To prove our result, we will need a few technical lemmas.

**Lemma 11.** Let $G$ be an $\alpha_1$-metric graph. Then, for every shortest path $P = (x_1, x_2, x_3, x_4, x_5)$ and a vertex $u$ of $G$ with $d(u, x_i) = k$ for all $i \in \{1, \dots, 5\}$, there exist vertices $t, w, s$ such that $d(t, u) = d(s, u) = k-1$, $k-2 \le d(w, u) \le k-1$, and $t$ is adjacent to $x_1, x_2, w$ and $s$ is adjacent to $x_4, x_5, w$.

**Lemma 12.** Let $G$ be an $\alpha_1$-metric graph. Then, for every shortest path $P = (x_1, x_2, x_3, x_4, x_5)$ and a vertex $u$ of $G$ with $d(u, x_i) = k$ for all $i \in \{1, \dots, 5\}$, there exists a shortest path $Q = (y_1, y_2, y_3)$ such that $d(u, y_i) = k-1$, for each $i \in \{1, \dots, 3\}$, and $N(y_1) \cap P = \{x_1, x_2\}$, $N(y_2) \cap P = \{x_2, x_3, x_4\}$ and $N(y_3) \cap P = \{x_4, x_5\}$.

**Theorem 7.** Let $G$ be an $\alpha_1$-metric graph. For every pair of vertices $s, t$ of $G$ with $d(s, t) \ge 4$ there exists a vertex $c \in I^o(s, t)$ such that $e(c) < \max\{e(s), e(t)\}$.

*Proof.* It is sufficient to prove the statement for vertices $s, t$ with $d(s, t) = 4$. We know, by Corollary 2, that $e(c) \le \max\{e(s), e(t)\}$ for every $c \in I(s, t)$. Assume, by way of contradiction, that there is no vertex $c \in I^o(s, t)$ such that $e(c) < \max\{e(s), e(t)\}$. Let, without loss of generality, $e(s) \le e(t)$. Then, for every $c \in I^o(s, t)$, $e(c) = e(t)$. Consider a vertex $c \in S_1(s, t)$. If $e(c) > e(s)$, then $e(c) = e(s) + 1$. Consider a vertex $z$ from $F(c)$. Necessarily, $z \in F(s)$. Applying the $\alpha_1$-metric property to $c \in I(s, t)$, $s \in I(c, z)$, we get $e(c) = e(t) \ge d(t, z) \ge d(c, t) + d(s, z) = 3 + e(s) = 2 + e(c)$, which is impossible. So, $e(s) = e(c) = e(t)$ for every $c \in I^o(s, t)$. Consider an arbitrary shortest path $P = (s = x_1, x_2, x_3, x_4, x_5 = t)$ connecting vertices $s$ and $t$. We claim that for any vertex $u \in F(x_3)$ all vertices of $P$ are at distance $k := d(u, x_3) = e(x_3)$ from $u$. As $e(x_i) = e(x_3)$, we know that $d(u, x_i) \le k$ ($1 \le i \le 5$). Assume $d(u, x_i) = k-1$, $d(u, x_{i+1}) = k$, and $i \le 2$. Then, the $\alpha_1$-metric property applied to $x_i \in I(u, x_{i+1})$ and $x_{i+1} \in I(x_i, x_{i+3})$ gives $d(x_{i+3}, u) \ge k-1+2 = k+1$, which is a contradiction with $d(u, x_{i+3}) \le k$. So, $d(u, x_1) = d(u, x_2) = k$. By symmetry, also $d(u, x_4) = d(u, x_5) = k$. Hence, by Lemma 12, for the path $P = (x_1, x_2, x_3, x_4, x_5)$, there exists a shortest path $Q = (y_1, y_2, y_3)$ such that $d(u, y_i) = k-1$, for each $i \in \{1, \dots, 3\}$, and $N(y_1) \cap P = \{x_1, x_2\}$, $N(y_2) \cap P =$
$\{x_2, x_3, x_4\}$ and $N(y_3) \cap P = \{x_4, x_5\}$. As $y_i \in I^o(x_1, x_5) = I^o(s, t)$ for each $i \in \{1, \dots, 3\}$, we have $e(y_i) = e(x_3) = k$.

All the above holds for every shortest path $P = (s = x_1, x_2, x_3, x_4, x_5 = t)$ connecting vertices $s$ and $t$. Now, assume that $P$ is chosen in such a way that, among all vertices in $S_2(s, t)$, the vertex $x_3$ has the minimum number of furthest vertices, i.e., $|F(x_3)|$ is as small as possible. As $y_2$ also belongs to $S_2(s, t)$ and has $u$ at distance $k-1$, by the choice of $x_3$, there must exist a vertex $u' \in F(y_2)$ which is at distance $k-1$ from $x_3$. Applying the previous arguments to the path $P' := (s = x_1, x_2, y_2, x_4, x_5 = t)$, we will have $d(x_i, u') = d(y_2, u') = k$ for $i = 1, 2, 4, 5$ and, by Lemma 12, get two more vertices $v$ and $w$ at distance $k-1$ from $u'$ such that $vx_1, vx_2, wx_4, wx_5 \in E$ and $vy_2, wy_2 \notin E$. By convexity of disk $D(u', k-1)$, also $vx_3, wx_3 \in E$. Now consider the disk $D(x_2, 2)$. Since $y_3, w$ are in the disk and $x_5$ is not, vertices $w$ and $y_3$ must be adjacent. But then vertices $y_2, x_3, w, y_3$ form an induced cycle $C_4$, which is forbidden because disks in $G$ must be convex.

Thus, a vertex $c \in I^o(s, t)$ with $e(c) < \max\{e(s), e(t)\}$ must exist. $\square$

**Corollary 6.** Let $G$ be an $\alpha_1$-metric graph. Then, $\text{diam}(C(G)) \le 3$ and $\text{rad}(C(G)) \le 2$.

Corollary 6 generalizes an old result on chordal graphs [15]. Finally, note that results of Theorem 7 and Corollary 6 are sharp.

## 3.3 Finding a central vertex of an $\alpha_1$-metric graph

We present a local-search algorithm for computing a central vertex of an arbitrary $\alpha_1$-metric graph in subquadratic time (Theorem 8). Our algorithm even achieves linear runtime on an important subclass of $\alpha_1$-metric graphs, namely, $(\alpha_1, \Delta)$-metric graphs (Theorem 9), thus answering an open question from [32] where this subclass was introduced. The $(\alpha_1, \Delta)$-metric graphs are exactly the $\alpha_1$-metric graphs that further satisfy the so-called triangle condition: for every vertices $u, v, w$ such that $u$ and $v$ are adjacent, and $d(u, w) = d(v, w) = k$, there must exist some common neighbour $x \in N(u) \cap N(v)$ such that $d(x, w) = k-1$. Chordal graphs, and plane triangulations with inner vertices of degree at least 7, are $(\alpha_1, \Delta)$-metric graphs (see [14, 15, 32, 54]).

We first introduce the required new notations and terminology for this part. In what follows, let $\text{proj}(v, A) = \{a \in A : d(v, a) = d(v, A)\}$ denote the metric projection of a vertex $v$ to a vertex subset $A$. For every $k$ such that $0 \le k \le d(v, A)$, we define $S_k(A, v) = \bigcup\{S_k(a, v) : a \in \text{proj}(v, A)\}$. A distance-$k$ gate of $v$ with respect to $A$ is a vertex $v^*$ such that $v^* \in \bigcap\{I(a, v) : a \in \text{proj}(v, A)\}$ and $d(v^*, A) \le k$. If $k=1$, then following [16] we simply call it a gate. Note that every vertex $v$ such that $d(v, A) \le k$ is its own distance-$k$ gate. A cornerstone of our main algorithms is that, in $\alpha_1$-metric graphs, for every closed neighbourhood (for every *clique*, resp.), every vertex has a gate (a distance-two gate, resp.). Proofs are omitted due to lack of space.

The problem of computing gates has already attracted some attention, e.g., see [16]. We use this routine in the design of our main algorithms.
**Lemma 13 ([39]).** Let $A$ be an arbitrary subset of vertices in some graph $G$ with $m$ edges. In total $O(m)$ time, we can map every vertex $v \notin A$ to some vertex $v^* \in D(v, d(v, A)-1) \cap N(A)$ such that $|N(v^*) \cap A|$ is maximized. Furthermore, if $v$ has a gate with respect to $A$, then $v^*$ is a gate of $v$.

The efficient computation of distance-two gates is more challenging. We present a subquadratic-time procedure that only works in our special setting.

**Lemma 14.** Let $K$ be a clique in some $\alpha_1$-metric graph $G$ with $m$ edges. In total $O(m^{1.41})$ time, we can map every vertex $v \notin K$ to some distance-two gate $v^*$ with respect to $K$. Furthermore, in doing so we can also map $v^*$ to some independent set $J_K(v^*) \subseteq D(v^*, 1)$ such that $\text{proj}(v^*, K)$ is the disjoint union of neighbour-sets $N(w) \cap K$, for every $w \in J_K(v^*)$.

Then, we turn our attention to the following subproblem: being given a vertex $x$ in an $\alpha_1$-metric graph $G$, either compute a neighbour $y$ such that $e(y) < e(x)$, or assert that $x$ is a local minimum for the eccentricity function (but not necessarily a central vertex). Our analysis of the next algorithms essentially follows from the results of Section 3.1. We first present the following special case, for which we obtain a better runtime than for the more general Lemma 16.

**Lemma 15.** Let $x$ be an arbitrary vertex in an $\alpha_1$-metric graph $G$ with $m$ edges. If $e(x) \ge \text{rad}(G) + 2$, then $\bigcap\{N(x) \cap I(x, z) : z \in F(x)\} \ne \emptyset$, and every neighbour $y$ in this subset satisfies $e(y) < e(x)$. In particular, there is an $O(m)$-time algorithm that either outputs $y \in N(x)$ such that $e(y) < e(x)$, or asserts that $e(x) \le \text{rad}(G) + 1$.

Note that Lemma 15 relies on the existence of gates for every vertex with respect to $D(x, 1)$, and that it uses Lemma 13 as a subroutine. We can strengthen Lemma 15 as follows, at the expenses of a higher runtime.

**Lemma 16.** Let $x$ be an arbitrary vertex in an $\alpha_1$-metric graph $G$ with $m$ edges. There is an $O(m^{1.41})$-time algorithm that either outputs $y \in N(x)$ such that $e(y) < e(x)$, or asserts that $x$ is a local minimum for the eccentricity function. If $G$ is $(\alpha_1, \Delta)$-metric, then its runtime can be lowered down to $O(m)$.

The improved runtime for $(\alpha_1, \Delta)$-metric graphs comes from the property that for every clique in such a graph, every vertex has a gate [32], and that gates are easier to compute than distance-two gates.

**Theorem 8.** If $G$ is an $\alpha_1$-metric graph with $m$ edges, then a vertex $x_0$ such that $e(x_0) \le \text{rad}(G) + 1$ can be computed in $O(m)$ time. Furthermore, a central vertex can be computed in $O(m^{1.71})$ time.

Let us sketch our algorithm for general $\alpha_1$-metric graphs. By Theorem 2, we can compute in $O(m)$ time a vertex $x_0$ such that $e(x_0) \le \text{rad}(G) + 3$. We repeatedly apply Lemma 15 until we can further assert that $e(x_0) \le \text{rad}(G) + 1$ (and, hence, by Theorem 6, $d(x_0, C(G)) \le 2$). Since there are at most two
calls to this local-search procedure, the runtime is in $O(m)$. Now, if $x_0$ has
small enough degree ($\le m^{29}$), then we can apply Lemma 16 to every vertex
of $D(x_0, 1)$ in order to compute a minimum eccentricity vertex within $D(x_0, 2)$,
which must be central. Otherwise, we further restrict our search for a central
vertex to $X_1 := D(x_0, 5) \cap D(z_0, e(x_0) - 1)$, for some arbitrary $z_0 \in F(x_0)$,
which must be a superset of $C(G)$ provided that $x_0$ is non-central. Starting
from an arbitrary vertex of $X_1$, if we apply Lemma 15 at most five times, then
we can either extract some $x_1 \in X_1$ such that $e(x_1) \le e(x_0)$, or assert that
$x_0$ is central. If $e(x_1) < e(x_0)$, then $x_1$ is central. Otherwise, we repeat our
above procedure for $x_1$. Doing so, we compute a decreasing chain of subsets
$X_0 = V \supset X_1 \supset \dots \supset X_i \supset \dots X_T$, and vertices $x_0, x_1, \dots, x_i, \dots, x_T$ such that
$x_i \in X_i \setminus X_{i+1}$ for every $i$, $0 \le i \le T$. We continue until we compute a vertex of
smaller eccentricity than $x_0$, or we reach $X_{T+1} = \emptyset$ (in which case, $x_0$ is central).

To lower the runtime to $O(m)$ for the $(\alpha_1, \Delta)$-metric graphs, we use a different
approach that is based on additional properties of these graphs. Unfortunately,
these properties crucially depend on the triangle condition.

**Theorem 9.** If $G$ is an $(\alpha_1, \Delta)$-metric graph with $m$ edges, then a central vertex can be computed in $O(m)$ time.

Roughly, the algorithm starts from a vertex $x$ which is a local minimum for
the eccentricity function of $G$. We run a core procedure which either outputs two
adjacent vertices $u, v \in D(x, 1)$ such that $e(u) = e(v) = e(x)$ and $F(u), F(v)$ are
not comparable by inclusion, or outputs a central vertex. In the former case, we
can either assert that $x$ is central, or extract a central vertex from $S_{e(x)-1}(y, z)$
for some arbitrary $y \in F(u) \setminus F(v)$, $z \in F(v) \setminus F(u)$. Indeed, we can apply
Lemma 16 to the latter slice because $S_{e(x)-1}(y, z) \subseteq D(w, 1)$ for some $w$ [32].

References

1. A. Abboud, V. Vassilevska Williams, and J. Wang, Approximation and fixed pa- rameter subquadratic algorithms for radius and diameter in sparse graphs, In *SODA*, pp. 377–391, SIAM, 2016.

2. N. Alon, R. Yuster, U. Zwick, Finding and Counting Given Length Cycles, *Algorithmica* 17 (1997), 209-223.

3. A. Backurs, L. Roditty, G. Segal, V. Vassilevska Williams, N. Wein, Towards tight approximation bounds for graph diameter and eccentricities, in *STOC* 2018, pp. 267-280.

4. H.-J. Bandelt, V. Chepoi, 1-Hyperbolic graphs, *SIAM J. Discr. Math.* 16 (2003), 323–334.

5. V. G. Boltyanskii and P. S. Soltan, Combinatorial Geometry of Various Classes of Convex Sets [in Russian], *Štiinţa, Kishinev* (1978).

6. M. Borassi, P. Crescenzi, and M. Habib, Into the square: On the complexity of some quadratic-time solvable problems, *Electronic Notes in TCS*, 322(2016), 51–67.

7. A. Brandstädt, V. Chepoi, and F.F. Dragan, The algorithmic use of hypertree structure and maximum neighbourhood orderings, *DAM*, 82(1998), 43–77.
8. K. Bringmann, T. Husfeldt, and M. Magnusson, Multivariate analysis of orthogonal range searching and graph distances parameterized by treewidth, In *IPEC*, 2018.

9. S. Cabello, Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs, *ACM TALG*, 15(2):21, 2018.

10. D. Corneil, F. F. Dragan, M. Habib, and C. Paul, Diameter determination on restricted graph families, *DAM*, 113(2001), 143-166.

11. D.G. Corneil, F.F. Dragan and E. Köhler, On the power of BFS to determine a graph's diameter, *Networks* 42 (2003), 209-222.

12. D. Coudert, G. Ducoffe, and A. Popa, Fully polynomial FPT algorithms for some classes of bounded clique-width graphs, *ACM TALG*, 15(3), 2019.

13. S. Chechik, D.H. Larkin, L. Roditty, G. Schoenebeck, R.E. Tarjan, V. Vassilevska Williams, Better Approximation Algorithms for the Graph Diameter, in *SODA* 2014, pp. 1041-1052.

14. V. Chepoi, Some $d$-convexity properties in triangulated graphs, in *Mathematical Research*, vol. 87, *Ştiinţa, Chișinău*, 1986, pp. 164-177 (Russian).

15. V. Chepoi, Centers of triangulated graphs, *Math. Notes* 43 (1988), 143-151.

16. V. Chepoi, F.F. Dragan, A linear-time algorithm for finding a central vertex of a chordal graph, in *Proceedings of the Second European Symposium on Algorithms – ESA’94*, 159–170.

17. V. Chepoi and F. F. Dragan, Disjoint sets problem, 1992.

18. V. Chepoi and F. F. Dragan, Finding a central vertex in an HHD-free graph, *DAM*, 131(1) (2003), 93-111.

19. V.D. Chepoi, F.F. Dragan, B. Estellon, M. Habib and Y. Vaxès, Diameters, centers, and approximating trees of $\delta$-hyperbolic geodesic spaces and graphs, *Proceedings of the 24th Annual ACM Symposium on Computational Geometry (SoCG 2008)*, June 9-11, 2008, College Park, Maryland, USA, pp. 59-68.

20. V. Chepoi, F.F. Dragan, M. Habib, Y. Vaxès, and H. Alrasheed, Fast approximation of eccentricities and distances in hyperbolic graphs, *Journal of Graph Algorithms and Applications*, 23(2019), 393-433.

21. F.F. Dragan, Centers of Graphs and the Helly Property (in Russian), PhD thesis, Moldava State University, Chișinău, 1989.

22. F.F. Dragan, HT-graphs: centers, connected $r$-domination and Steiner trees, *Comput. Sci. J. of Moldova* (Kishinev), 1(1993), 64-83.

23. F.F. Dragan, Dominating cliques in distance-hereditary graphs, In *SWAT '94*, pp. 370-381, Springer, 1994.

24. F.F. Dragan, Almost Diameter of a House-hole-free Graph in Linear Time Via LexBFS, *Discret. Appl. Math.* 95(1999), 223-239.

25. F.F. Dragan, An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time, *Information Processing Letters*, 154(2020), 105873.

26. F.F. Dragan, G. Ducoffe, $\alpha_i$-Metric Graphs: Radius, Diameter and all Eccentricities, *CoRR*, abs/2305.02545, 2023.

27. F.F. Dragan, G. Ducoffe, $\alpha_i$-Metric Graphs: Hyperbolicity, in *Preparation*, 2022-2023.

28. F.F. Dragan, G. Ducoffe, H.M. Guarnera, Fast Deterministic Algorithms for Computing All Eccentricities in (Hyperbolic) Helly Graphs, in *WADS* 2021. pp. 300-314.

29. F.F. Dragan and H.M. Guarnera, Eccentricity function in distance-hereditary graphs, *Theor. Comput. Sci.*, 833(2020), 26-40.

30. F.F. Dragan, H.M. Guarnera, Eccentricity terrain of $\delta$-hyperbolic graphs, *J. Comput. Syst. Sci.* 112 (2020), 50-65.

31. F.F. Dragan, M. Habib, and L. Viennot, Revisiting radius, diameter, and all eccentricity computation in graphs through certificates, *CoRR*, abs/1803.04660, 2018.
32. F.F. Dragan, E. Köhler, H. Alrasheed, Eccentricity Approximating Trees, *Discrete Applied Mathematics*, 232 (2017), 142–156.

33. F.F. Dragan and F. Nicolai, LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem, *DAM*, 98(2000), 191–207.

34. F.F. Dragan, F. Nicolai, A. Brandstädt, LexBFS-orderings and powers of graphs, Proceedings of the WG’96, *Lecture Notes in Computer Science*, Vol. 1197, Springer, Berlin, 1997, pp. 166–180.

35. G. Ducoffe, Easy computation of eccentricity approximating trees, *DAM*, 260 (2019), 267–271.

36. G. Ducoffe, Around the diameter of AT-free graphs, *JGT*, 99(4) (2022), 594–614.

37. G. Ducoffe, Beyond Helly graphs: the diameter problem on absolute retracts, In *WG*, pp. 321-335, 2021.

38. G. Ducoffe, Optimal diameter computation within bounded clique-width graphs, *Algorithmica*, 84 (2022), 3192–3222.

39. G. Ducoffe, Distance problems within Helly graphs and k-Helly graphs, *Theoretical Computer Science*, (2023).

40. G. Ducoffe and F.F. Dragan, A story of diameter, radius, and (almost) Helly property, *Networks*, 77(2021), 435-453.

41. G. Ducoffe, M. Habib, and L. Viennot, Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension, In *SODA*, pp. 1905–1922, SIAM, 2020.

42. M. Farber, R.E. Jamison, On local convexity in graphs, *Discr. Math.* 66 (1987), 231–247.

43. A. Farley and A. Proskurowski, Computation of the center and diameter of outer-planar graphs, *DAM*, 2(1980), 185–191.

44. P. Gawrychowski, H. Kaplan, S. Mozes, M. Sharir, and O. Weimann, Voronoi diagrams on planar graphs, and computing the diameter in deterministic $O(n^{5/3})$ time, In *SODA*, pp. 495–514, SIAM, 2018.

45. M. Gromov, Hyperbolic Groups, pages 75–263. Springer, New York, NY, 1987.

46. E. Howorka, A characterization of distance-hereditary graphs, *Quart. J. Math. Oxford Ser.* 28 (1977), 417–420.

47. D. Koschützki, K. Lehmann, L. Peeters, S. Richter, D. Tenfelde-Podehl, and O. Zlotowski, Centrality indices, In *Network Analysis*, pp. 16–61. Springer, 2005.

48. S. Olariu, A simple linear-time algorithm for computing the center of an interval graph, *Int. J. of Computer Mathematics*, 34(1990), 121–128.

49. E. Prisner, Eccentricity-approximating trees in chordal graphs, *Discrete Mathematics*, 220(2000), 263–269.

50. L. Roditty and V. Vassilevska Williams, Fast approximation algorithms for the diameter and radius of sparse graphs, In *STOC*, pp. 515–524. ACM, 2013.

51. V.P. Soltan, V.D. Chepoi, Conditions for invariance of set diameters under d-convexification in a graph, *Cybernetics* 19 (1983), 750–756 (Russian, English transl.).

52. O. Weimann, R. Yuster, Approximating the diameter of planar graphs in near linear time, *ACM Trans. Algorithms* 12(1), 12:1-12:13 (2016).

53. Y. Wu and C. Zhang, Hyperbolicity and chordality of a graph, *Electr. J. Comb.*, 18(1): Paper #P43, 2011.

54. S.V. Yushmanov, V. Chepoi, A general method of investigation of metric graph properties related to the eccentricity, in *Mathematical Problems in Cybernetics*, vol. 3, Nauka, Moscow, 1991, pp. 217–232 (Russian).