to $D(x, 1)$ for every $z \in F(x)$, whose existence follows from Corollary 13. By Lemma 31, this can be done in $O(m)$ time. Then, we compute $K = \bigcap\{N(x) \cap I(x, z) : z \in F(x)\}$. Note that $K = \bigcap\{N(x) \cap N(z^*) : z \in F(x)\}$, and therefore, we can also compute $K$ in $O(m)$ time. If $K = \emptyset$, then we can assert $e(x) \le \text{rad}(G) + 1$. Else, let $y \in K$ be arbitrary. If $e(x) \le e(y)$, then again we can assert that $e(x) \le \text{rad}(G) + 1$. Otherwise, we are done outputting $y$. $\square$

We can strengthen Lemma 33 as follows, at the expenses of a higher runtime.

**Lemma 34.** 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 a $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)$.

*Proof.* If $e(x) \le 2$ then $x$ is always a local minimum for the eccentricity function, unless $e(x) = 2$ and $x$ is adjacent to some universal vertex $y$. Therefore, we assume for the remainder of the proof $e(x) \ge 3$. First we compute $K = \bigcap\{N(x) \cap I(x, z) : z \in F(x)\}$. This can be done in $O(m)$ time by using the exact same approach as for Lemma 33. If $K = \emptyset$, then clearly $x$ is a local minimum for the eccentricity function. Otherwise, we are left deciding whether there exists a vertex of $K$ with eccentricity smaller than $e(x)$. For that, we claim that we only need to consider the vertices $v$ such that $d(v, K) \ge e(x) - 1 \ge 2$. Indeed, by Theorem 5, the disks of $G$ must be convex, which implies that $K$ is a clique. In particular, every vertex $v$ such that $d(v, K) \le e(x) - 2$ is at a distance at most $e(x) - 1$ to every vertex of $K$. Therefore, the claim is proved. Now, if $d(v, K) = e(x)$ for at least one vertex $v$, then every vertex of $K$ must have eccentricity at least $e(x)$, hence we can assert that $x$ is a local minimum for the eccentricity function. Otherwise, let $F(K) = \{v \in V : d(v, K) = e(x) - 1\}$. For every $y \in K$, in order to decide whether $e(y) < e(x)$, it suffices to decide whether $y \in \bigcap\{\text{proj}(v, K) : v \in F(K)\}$, or even more strongly to compute the number of vertices $v \in F(K)$ such that $y \in \text{proj}(v, K)$.

For general $\alpha_1$-metric graphs, we compute distance-two gates $v^*$ for every $v \in F(K)$, whose existence follows from Lemma 30. By Lemma 32, this can be done in $O(m^{1.41})$ time. Being also given the independent sets $J_K(v^*) \subseteq N(v^*)$, for every $v \in F(K)$, as in Lemma 32, we compute the following weight function $\alpha$ on $N(K)$: $\alpha(w) = |\{v \in F(K) : w \in J_K(v^*)\}|$. This can be done in $O(m)$ time. Recall that for every $v \in F(K)$, $\text{proj}(v, K)$ is the disjoint union of $N(w) \cap K$ for every $w \in J_K(v^*)$. As a result, for every $y \in K$, the number of vertices $v \in F(K)$ such that $y \in \text{proj}(v, K)$ is exactly $\sum\{\alpha(w) : w \in N(y) \setminus K\}$, which can be calculated in total $O(m)$ time for every vertex of $K$.

Finally, assume for the remainder of the proof that $G$ is $(\alpha_1, \Delta)$-metric, and let us modify this last part of the procedure as follows. We compute gates $v^*$ for every $v \in F(K)$, whose existence follows from Lemma 29. By Lemma 31, this can be done in $O(m)$ time. For every $w \in N(K)$, let $\alpha(w) = |\{v \in F(K) : v^* = w\}|$. As before, for every $y \in K$, the number of vertices $v \in F(K)$ such that $y \in \text{proj}(v, K)$ is exactly $\sum\{\alpha(w) : w \in N(y) \setminus K\}$, which can still be calculated in total $O(m)$ time for every vertex of $K$. $\square$

**The main procedures.** We start presenting our algorithm for the general $\alpha_1$-metric graphs.

**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.
*Proof.* 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 33 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)$. Then, we apply the following procedure, starting from $x_0$ and $X_0 := V$, until we can assert that the current vertex $x_i$ (considered at the $i^{th}$ iteration) is central.

1. If $\text{deg}(x_i) \le m^{29}$, then we output a vertex of minimum eccentricity within $D(x_i, 2)$, and then we stop. This is done by applying Lemma 34 to every vertex of $D(x_i, 1)$. Otherwise $(\text{deg}(x_i) > m^{29})$, we go to Step 2.

2. Let $z_i \in F(x_i)$ be arbitrary. We set $X_{i+1} := X_i \cap D(x_i, 5) \cap D(z_i, e(x_i) - 1)$. If $X_{i+1} = \emptyset$, then we output $x_i$. Otherwise, we pick an arbitrary vertex $y \in X_{i+1}$, and then we go to Step 3.

3. We consider several cases in what follows.

(a) If $e(y) < e(x_i)$, then we output $y$;

(b) Else, if $e(y) = e(x_i)$, then we set $x_{i+1} := y$ and we go back to Step 1;

(c) Else, there are three subcases. If $\bigcap\{X_{i+1} \cap N(y) \cap I(y, w) : w \in F(y)\} = \emptyset$, then we output $x_i$. Otherwise, we pick an arbitrary neighbour $y'$ in this subset. If $e(y') \ge e(y)$, then we also output $x_i$. Else, we set $y := y'$ and we repeat Step 3.

We stress that at the $i^{th}$ iteration we ensure at Step 2 that $x_i \in X_i \setminus X_{i+1}$. In particular, $X_0 \supset X_1 \supset \dots \supset X_i$. It implies that our procedure eventually halts at some iteration $T$ because we always stop at Step 2 if $X_{i+1} = \emptyset$. Suppose by contradiction that we do not output a central vertex. For every $i$ such that $0 \le i < T$, we ensure at Step 3b that $e(x_{i+1}) = e(x_i)$. Therefore, $e(x_T) = e(x_{T-1}) = \dots = e(x_0) \le \text{rad}(G) + 1$. Since at the $T^{th}$ iteration, we output a vertex of eccentricity at most $e(x_T)$, we must have $e(x_T) \ge \text{rad}(G) + 1$. It implies $e(x_i) = \text{rad}(G) + 1$ for every $i$ such that $0 \le i \le T$. Then, by Theorem 6, $d(x_i, C(G)) \le 2$ for every $i$ such that $0 \le i \le T$. Let us now consider the last step executed during iteration $T$. It cannot be Step 1 because a minimum eccentricity vertex within $D(x_T, 2)$ must be central. Suppose by contradiction that we halt at Step 2. Then, $X_{T+1} = \emptyset$. We prove by induction that $C(G) \subseteq X_i$ for every $i$ with $0 \le i \le T + 1$, obtaining a contradiction. This is true for $i = 0$ because $X_0 = V$. Assume now this is true for some $i$ with $0 \le i \le T$. Recall that $d(x_i, C(G)) \le 2$. By Corollary 11, $\text{diam}(C(G)) \le 3$. As a result, $C(G) \subseteq D(x_i, 5)$. Furthermore, $C(G) \subseteq D(z_i, e(x_i) - 1)$ because we have $\text{rad}(G) = e(x_i) - 1$. Hence, $C(G) \subseteq X_i \cap D(x_i, 5) \cap D(z_i, e(x_i) - 1) = X_{i+1}$. We deduce from the above that we must halt at Step 3. Since we suppose that we output a vertex of eccentricity $e(x_T) = \text{rad}(G) + 1$, it implies that we halt at Step 3c. In particular, we found a vertex $y \in X_{T+1}$ such that $e(y) \ge e(x_T) + 1$, and either $\bigcap\{X_{T+1} \cap N(y) \cap I(y, w) : w \in F(y)\} = \emptyset$, or $e(y') \ge e(y)$ for some arbitrary neighbour of $y$ in this subset. However, by Corollary 9, there exists a shortest $yC(G)$-path that is decreasing and such that the only horizontal edge, if any, must have one end that is adjacent to the end-vertex in $\text{proj}(y, C(G))$ (i.e., it must be the penultimate edge of the path, starting from $y$). In particular, the neighbour $y''$ of $y$ on this shortest path must satisfy $e(y'') < e(y)$. Since $y \in X_{T+1}$, $C(G) \subseteq X_{T+1}$ and according to Theorem 5 the subset $X_{T+1}$ must be convex (as intersection of convex disks), we get that $y'' \in X_{T+1}$. Then, $\bigcap\{X_{T+1} \cap N(y) \cap I(y, w) : w \in F(y)\} \ne \emptyset$. Furthermore, since we assume $e(y) \ge \text{rad}(G) + 2$, by Lemma 33, every neighbour $y'$ in this subset must satisfy $e(y') < e(y)$. A contradiction occurs.

We end up analysing the runtime of the procedure. Recall that all vertices $x_0, x_1, \dots, x_T$ are pairwise different. Since all such vertices, except maybe the last one, have degree more than $m^{29}$, the number of iterations is in $O(m/m^{29}) = O(m^{71})$. Let us consider an arbitrary iteration $i$, for some $i$ such that $0 \le i \le T$. During Step 1, either we do nothing or (only if $i = T$) we call
*Proof.* 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 33 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)$. Then, we apply the following procedure, starting from $x_0$ and $X_0 := V$, until we can assert that the current vertex $x_i$ (considered at the $i^{th}$ iteration) is central.

1. If $\text{deg}(x_i) \le m^{29}$, then we output a vertex of minimum eccentricity within $D(x_i, 2)$, and then we stop. This is done by applying Lemma 34 to every vertex of $D(x_i, 1)$. Otherwise $(\text{deg}(x_i) > m^{29})$, we go to Step 2.

2. Let $z_i \in F(x_i)$ be arbitrary. We set $X_{i+1} := X_i \cap D(x_i, 5) \cap D(z_i, e(x_i) - 1)$. If $X_{i+1} = \emptyset$, then we output $x_i$. Otherwise, we pick an arbitrary vertex $y \in X_{i+1}$, and then we go to Step 3.

3. We consider several cases in what follows.

(a) If $e(y) < e(x_i)$, then we output $y$;

(b) Else, if $e(y) = e(x_i)$, then we set $x_{i+1} := y$ and we go back to Step 1;

(c) Else, there are three subcases. If $\bigcap\{X_{i+1} \cap N(y) \cap I(y, w) : w \in F(y)\} = \emptyset$, then we output $x_i$. Otherwise, we pick an arbitrary neighbour $y'$ in this subset. If $e(y') \ge e(y)$, then we also output $x_i$. Else, we set $y := y'$ and we repeat Step 3.

We stress that at the $i^{th}$ iteration we ensure at Step 2 that $x_i \in X_i \setminus X_{i+1}$. In particular, $X_0 \supset X_1 \supset \dots \supset X_i$. It implies that our procedure eventually halts at some iteration $T$ because we always stop at Step 2 if $X_{i+1} = \emptyset$. Suppose by contradiction that we do not output a central vertex. For every $i$ such that $0 \le i < T$, we ensure at Step 3b that $e(x_{i+1}) = e(x_i)$. Therefore, $e(x_T) = e(x_{T-1}) = \dots = e(x_0) \le \text{rad}(G) + 1$. Since at the $T^{th}$ iteration, we output a vertex of eccentricity at most $e(x_T)$, we must have $e(x_T) \ge \text{rad}(G) + 1$. It implies $e(x_i) = \text{rad}(G) + 1$ for every $i$ such that $0 \le i \le T$. Then, by Theorem 6, $d(x_i, C(G)) \le 2$ for every $i$ such that $0 \le i \le T$. Let us now consider the last step executed during iteration $T$. It cannot be Step 1 because a minimum eccentricity vertex within $D(x_T, 2)$ must be central. Suppose by contradiction that we halt at Step 2. Then, $X_{T+1} = \emptyset$. We prove by induction that $C(G) \subseteq X_i$ for every $i$ with $0 \le i \le T+1$, obtaining a contradiction. This is true for $i=0$ because $X_0 = V$. Assume now this is true for some $i$ with $0 \le i \le T$. Recall that $d(x_i, C(G)) \le 2$. By Corollary 11, $\text{diam}(C(G)) \le 3$. As a result, $C(G) \subseteq D(x_i, 5)$. Furthermore, $C(G) \subseteq D(z_i, e(x_i) - 1)$ because we have $\text{rad}(G) = e(x_i) - 1$. Hence, $C(G) \subseteq X_i \cap D(x_i, 5) \cap D(z_i, e(x_i) - 1) = X_{i+1}$. We deduce from the above that we must halt at Step 3. Since we suppose that we output a vertex of eccentricity $e(x_T) = \text{rad}(G) + 1$, it implies that we halt at Step 3c. In particular, we found a vertex $y \in X_{T+1}$ such that $e(y) \ge e(x_T) + 1$, and either $\bigcap\{X_{T+1} \cap N(y) \cap I(y, w) : w \in F(y)\} = \emptyset$, or $e(y') \ge e(y)$ for some arbitrary neighbour of $y$ in this subset. However, by Corollary 9, there exists a shortest $yC(G)$-path that is decreasing and such that the only horizontal edge, if any, must have one end that is adjacent to the end-vertex in $\text{proj}(y, C(G))$ (i.e., it must be the penultimate edge of the path, starting from $y$). In particular, the neighbour $y''$ of $y$ on this shortest path must satisfy $e(y'') < e(y)$. Since $y \in X_{T+1}$, $C(G) \subseteq X_{T+1}$ and according to Theorem 5 the subset $X_{T+1}$ must be convex (as intersection of convex disks), we get that $y'' \in X_{T+1}$. Then, $\bigcap\{X_{T+1} \cap N(y) \cap I(y, w) : w \in F(y)\} \ne \emptyset$. Furthermore, since we assume $e(y) \ge \text{rad}(G) + 2$, by Lemma 33, every neighbour $y'$ in this subset must satisfy $e(y') < e(y)$. A contradiction occurs.

We end up analysing the runtime of the procedure. Recall that all vertices $x_0, x_1, \dots, x_T$ are pairwise different. Since all such vertices, except maybe the last one, have degree more than $m^{29}$, the number of iterations is in $O(m/m^{29}) = O(m^{71})$. Let us consider an arbitrary iteration $i$, for some $i$ such that $0 \le i \le T$. During Step 1, either we do nothing or (only if $i = T$) we call
Lemma 34 at most $O(m^{29})$ times and then we stop. In the latter case, the runtime is in $O(m^{1.7})$. Step 2 takes $O(m)$ time. Then, during Step 3, we only consider vertices $y \in D(x_i, 5)$. Since every such vertex $y$ satisfies $e(y) \le e(x_i) + 5$, we can execute Step 3c at most five times. For every execution of Step 3c, we can slightly modify the algorithm of Lemma 33 in order to perform all computations in $O(m)$ time. Therefore, Step 3 also takes $O(m)$ time. Overall, the total runtime of any iteration is in $O(m)$, except maybe for the last iteration whose runtime can be $O(m^{1.7})$. Since there are only $O(m^{71})$ iterations, the final runtime is in $O(m^{1.71})$. $\square$

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

**Lemma 35 ([32]).** Let $G$ be an $(\alpha_1, \Delta)$-metric graph. Then, in every slice $S_k(y, z)$, there is a vertex $w$ that is universal to that slice, i.e., $S_k(y, z) \subseteq D(w, 1)$.

**Lemma 36.** Let $x, y$ be adjacent vertices in an $(\alpha_1, \Delta)$-metric graph $G$ such that both $x, y$ are local minima for the eccentricity function and $e(x) = e(y) = \text{rad}(G) + 1$. For every $z \in \text{proj}(x, C(G))$, there exists a $u \in N(x) \cap N(z)$ such that $F(u) \subseteq F(x) \cap F(y)$.

*Proof.* First we prove that $z \in \text{proj}(y, C(G))$. Suppose by contradiction it is not the case. By Theorem 6, $d(x, C(G)) = d(y, C(G)) = 2$. Therefore, $d(y, z) = 3$ and $x \in N(y) \cap I(y, z)$. Let $w \in N(x) \cap N(z)$ be arbitrary. Note that $e(w) \le e(z) + 1 = e(x)$. It implies $e(w) = e(x) = \text{rad}(G) + 1$ because $x$ is assumed to be a local minimum for the eccentricity function. Then, let $v \in F(w)$ be arbitrary. Since $G$ is $\alpha_1$-metric, $d(v, y) \ge d(v, z) + d(w, y) = \text{rad}(G) + 2$. The latter is in contradiction with $e(y) = \text{rad}(G) + 1$.

Since $x, y$ are adjacent and $d(x, z) = d(y, z) = 2$, the triangle condition implies the existence of some common neighbour $u \in N(x) \cap N(y) \cap N(z)$. Recall that $e(u) = e(x) = e(y) = \text{rad}(G) + 1$. Suppose by contradiction that there exists a $v \in F(u) \setminus F(x)$. Since $G$ is an $\alpha_1$-metric graph, $d(z, v) \ge d(z, u)+d(x, v) = 1+\text{rad}(G)$, which is impossible for $z \in C(G)$. As a result, $F(u) \subseteq F(x)$. We prove similarly that $F(u) \subseteq F(y)$, and so $F(u) \subseteq F(x) \cap F(y)$. $\square$

**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.

*Proof.* The algorithm starts from a vertex $x$ which is a local minimum for the eccentricity function of $G$. To compute such a vertex in $O(m)$ time, we first apply Theorem 2 in order to compute a vertex of eccentricity at most $\text{rad}(G) + 3$. Then, we apply Lemma 34 at most three times.

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, let $y \in F(u) \setminus F(v)$ and $z \in F(v) \setminus F(u)$ be arbitrary. Since $G$ is an $\alpha_1$-metric graph, $d(y, z) \ge d(y, v) + d(u, z) = 2e(x) - 2$. If $d(y, z) \ge 2e(x) - 1$, then $\text{rad}(G) > e(x) - 1$, and therefore $x$ is a central vertex. From now on, we assume that $d(y, z) = 2e(x) - 2$. Then, any vertex of eccentricity $e(x) - 1$ must be contained in $S_{e(x)-1}(y, z)$. Let $w$ be such that $S_{e(x)-1}(y, z) \subseteq D(w, 1)$, whose existence follows from Lemma 35. We apply Lemma 34 in order to compute a minimum eccentricity vertex $x'$ within $D(w, 1)$. Finally, we output any of $x, x'$ that has minimum eccentricity. To complete the description of our algorithm, we now present the core procedure.

1. We compute gates $z^*$ with respect to $D(x, 1)$ for every $z \in F(x)$, whose existence follows from Corollary 13. By Lemma 31, this can be done in $O(m)$ time. Then, for every $y \in N(x)$, we
Lemma 34 at most $O(m^{29})$ times and then we stop. In the latter case, the runtime is in $O(m^{1.7})$. Step 2 takes $O(m)$ time. Then, during Step 3, we only consider vertices $y \in D(x_i, 5)$. Since every such vertex $y$ satisfies $e(y) \le e(x_i) + 5$, we can execute Step 3c at most five times. For every execution of Step 3c, we can slightly modify the algorithm of Lemma 33 in order to perform all computations in $O(m)$ time. Therefore, Step 3 also takes $O(m)$ time. Overall, the total runtime of any iteration is in $O(m)$, except maybe for the last iteration whose runtime can be $O(m^{1.7})$. Since there are only $O(m^{71})$ iterations, the final runtime is in $O(m^{1.71})$. $\square$

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

**Lemma 35 ([32]).** Let $G$ be an $(\alpha_1, \Delta)$-metric graph. Then, in every slice $S_k(y, z)$, there is a vertex $w$ that is universal to that slice, i.e., $S_k(y, z) \subseteq D(w, 1)$.

**Lemma 36.** Let $x, y$ be adjacent vertices in an $(\alpha_1, \Delta)$-metric graph $G$ such that both $x, y$ are local minima for the eccentricity function and $e(x) = e(y) = \text{rad}(G) + 1$. For every $z \in \text{proj}(x, C(G))$, there exists a $u \in N(x) \cap N(z)$ such that $F(u) \subseteq F(x) \cap F(y)$.

*Proof.* First we prove that $z \in \text{proj}(y, C(G))$. Suppose by contradiction it is not the case. By Theorem 6, $d(x, C(G)) = d(y, C(G)) = 2$. Therefore, $d(y, z) = 3$ and $x \in N(y) \cap I(y, z)$. Let $w \in N(x) \cap N(z)$ be arbitrary. Note that $e(w) \le e(z) + 1 = e(x)$. It implies $e(w) = e(x) = \text{rad}(G) + 1$ because $x$ is assumed to be a local minimum for the eccentricity function. Then, let $v \in F(w)$ be arbitrary. Since $G$ is $\alpha_1$-metric, $d(v, y) \ge d(v, z) + d(w, y) = \text{rad}(G) + 2$. The latter is in contradiction with $e(y) = \text{rad}(G) + 1$.

Since $x, y$ are adjacent and $d(x, z) = d(y, z) = 2$, the triangle condition implies the existence of some common neighbour $u \in N(x) \cap N(y) \cap N(z)$. Recall that $e(u) = e(x) = e(y) = \text{rad}(G) + 1$. Suppose by contradiction that there exists a $v \in F(u) \setminus F(x)$. Since $G$ is an $\alpha_1$-metric graph, $d(z, v) \ge d(z, u) + d(x, v) = 1 + \text{rad}(G)$, which is impossible for $z \in C(G)$. As a result, $F(u) \subseteq F(x)$. We prove similarly that $F(u) \subseteq F(y)$, and so $F(u) \subseteq F(x) \cap F(y)$. $\square$

**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.

*Proof.* The algorithm starts from a vertex $x$ which is a local minimum for the eccentricity function of $G$. To compute such a vertex in $O(m)$ time, we first apply Theorem 2 in order to compute a vertex of eccentricity at most $\text{rad}(G) + 3$. Then, we apply Lemma 34 at most three times.

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, let $y \in F(u) \setminus F(v)$ and $z \in F(v) \setminus F(u)$ be arbitrary. Since $G$ is an $\alpha_1$-metric graph, $d(y, z) \ge d(y, v) + d(u, z) = 2e(x) - 2$. If $d(y, z) \ge 2e(x) - 1$, then $\text{rad}(G) > e(x) - 1$, and therefore $x$ is a central vertex. From now on, we assume that $d(y, z) = 2e(x) - 2$. Then, any vertex of eccentricity $e(x) - 1$ must be contained in $S_{e(x)-1}(y, z)$. Let $w$ be such that $S_{e(x)-1}(y, z) \subseteq D(w, 1)$, whose existence follows from Lemma 35. We apply Lemma 34 in order to compute a minimum eccentricity vertex $x'$ within $D(w, 1)$. Finally, we output any of $x, x'$ that has minimum eccentricity. To complete the description of our algorithm, we now present the core procedure.

1. We compute gates $z^*$ with respect to $D(x, 1)$ for every $z \in F(x)$, whose existence follows from Corollary 13. By Lemma 31, this can be done in $O(m)$ time. Then, for every $y \in N(x)$, we
compute $f_x(y) = |\{z \in F(x) : y \in N(x) \cap I(x, z)\}|$. This can also be done in $O(m)$ time by enumerating the gates $z^*$ in $N(y)$ for every $y \in N(x)$.

2. We choose a neighbour $y_1$ such that $f_x(y_1)$ is maximized. There are three cases.

(a) If $e(y_1) > e(x)$ then, by Lemma 19, we can assert that $x$ is a central vertex. From now on, $e(y_1) \le e(x)$. Since $x$ is a local minimum for the eccentricity function, $e(x) = e(y_1)$.

(b) If $y_1$ is not a local minimum for the eccentricity function of $G$, then by Lemma 34 we can compute a central vertex within $N(y_1)$ in $O(m)$ time. From now on both $x, y_1$ are local minima for the eccentricity function.

(c) If $F(y_1) \setminus F(x) \ne \emptyset$, then we can output $u = x, v = y_1$. Indeed, we also have $F(x) \setminus F(y_1) \ne \emptyset$ because $y_1 \in N(x) \cap I(x, z)$ for some $z \in F(x)$. In what follows, we assume that $F(x), F(y_1)$ are comparable by inclusion, and so, $F(y_1) \subset F(x)$.

3. Let $z_1 \in F(y_1)$ be arbitrary. We choose some neighbour $y_2$ within $N(x) \cap I(x, z_1)$ which maximizes $f_x(y_2)$. Note that in order to compute $N(x) \cap I(x, z_1)$, and so $y_2$, in $O(m)$ time, it suffices to only consider the vertices of $N(x) \cap N(z_1^*)$. There are two cases.

(a) If $e(y_2) > e(x)$ then, by Lemma 19, we can assert that $x$ is a central vertex. From now on we assume $e(y_2) = e(x)$.

(b) If $y_2$ is not a local minimum for the eccentricity function of $G$, then by Lemma 34 we can compute a central vertex within $N(y_2)$ in $O(m)$ time. From now on vertices $x, y_1, y_2$ are local minima for the eccentricity function.

4. Due to the maximality of $f_x(y_1)$ and the existence of a $z_1 \in F(x) \cap F(y_1)$, we have $f_x(y_2) \le f_x(y_1) < |F(x)|$. Furthermore, both $F(x) \setminus F(y_1), F(x) \setminus F(y_2)$ are nonempty. For each $i \in \{1, 2\}$, we compute $B_i = \bigcap \{N(x) \cap I(x, z) : z \in F(x) \setminus F(y_i)\}$. Since $B_i = \bigcap \{N(x) \cap N(z^*) : z \in F(x) \setminus F(y_i)\}$, it can be done in $O(m)$ time. There are now two cases.

(a) Assume the existence of an edge $uv$ where $u \in B_1, v \in B_2$. If $\max\{e(u), e(v)\} > e(x)$ then, by Lemma 19, we can assert that $x$ is a central vertex. Otherwise, we prove next that $F(u), F(v)$ are not comparable by inclusion, and therefore we can output $u, v$. Indeed, $F(y_1), F(x) \cap F(y_2)$ are not comparable by inclusion because

$$|F(x) \cap F(y_2)| = |F(x)| - f_x(y_2) \ge |F(x)| - f_x(y_1) = |F(y_1)|$$

and $z_1 \in F(y_1) \setminus F(y_2)$. Furthermore, $F(x) \cap F(u) \subseteq F(y_1)$ ($F(x) \cap F(v) \subseteq F(y_2)$, respectively) because $u \in B_1$ ($v \in B_2$, respectively). Then, $F(u) \cap F(x) = F(y_1)$ and $F(v) \cap F(x) = F(y_2) \cap F(x)$, because otherwise this would contradict the maximality of either $f_x(y_1)$ or $f_x(y_2)$.

(b) Finally, assume that every vertex of $B_1$ is nonadjacent to every vertex of $B_2$. We claim that $x$ is a central vertex. Suppose by contradiction $e(x) = rad(G) + 1$. Let $z \in \text{proj}(x, C(G))$ be arbitrary. By Lemma 36, there exist vertices $u, v \in N(x) \cap N(z)$ such that $F(u) \subseteq F(x) \cap F(y_1) = F(y_1)$, $F(v) \subseteq F(x) \cap F(y_2)$. Note that $\max\{e(u), e(v)\} \le e(z) + 1 = rad(G) + 1$. Since $x$ is a local minimum for the eccentricity function, we obtain $e(u) = e(v) = rad(G) + 1$. Then, $u \in B_1, v \in B_2$. In particular, $u, v$ must be nonadjacent, thus contradicting the convexity of $D(x, 1) \cap D(z, 1)$, and so, Theorem 5. $\square$

We leave as an open question whether there exists a linear-time algorithm for computing a central vertex in an $\alpha_1$-metric graph.
compute $f_x(y) = |\{z \in F(x) : y \in N(x) \cap I(x, z)\}|$. This can also be done in $O(m)$ time by enumerating the gates $z^*$ in $N(y)$ for every $y \in N(x)$.

2. We choose a neighbour $y_1$ such that $f_x(y_1)$ is maximized. There are three cases.

(a) If $e(y_1) > e(x)$ then, by Lemma 19, we can assert that $x$ is a central vertex. From now on, $e(y_1) \le e(x)$. Since $x$ is a local minimum for the eccentricity function, $e(x) = e(y_1)$.

(b) If $y_1$ is not a local minimum for the eccentricity function of $G$, then by Lemma 34 we can compute a central vertex within $N(y_1)$ in $O(m)$ time. From now on both $x, y_1$ are local minima for the eccentricity function.

(c) If $F(y_1) \setminus F(x) \ne \emptyset$, then we can output $u = x, v = y_1$. Indeed, we also have $F(x) \setminus F(y_1) \ne \emptyset$ because $y_1 \in N(x) \cap I(x, z)$ for some $z \in F(x)$. In what follows, we assume that $F(x), F(y_1)$ are comparable by inclusion, and so, $F(y_1) \subset F(x)$.

3. Let $z_1 \in F(y_1)$ be arbitrary. We choose some neighbour $y_2$ within $N(x) \cap I(x, z_1)$ which maximizes $f_x(y_2)$. Note that in order to compute $N(x) \cap I(x, z_1)$, and so $y_2$, in $O(m)$ time, it suffices to only consider the vertices of $N(x) \cap N(z_1^*)$. There are two cases.

(a) If $e(y_2) > e(x)$ then, by Lemma 19, we can assert that $x$ is a central vertex. From now on we assume $e(y_2) = e(x)$.

(b) If $y_2$ is not a local minimum for the eccentricity function of $G$, then by Lemma 34 we can compute a central vertex within $N(y_2)$ in $O(m)$ time. From now on vertices $x, y_1, y_2$ are local minima for the eccentricity function.

4. Due to the maximality of $f_x(y_1)$ and the existence of a $z_1 \in F(x) \cap F(y_1)$, we have $f_x(y_2) \le f_x(y_1) < |F(x)|$. Furthermore, both $F(x) \setminus F(y_1), F(x) \setminus F(y_2)$ are nonempty. For each $i \in \{1, 2\}$, we compute $B_i = \bigcap \{N(x) \cap I(x, z) : z \in F(x) \setminus F(y_i)\}$. Since $B_i = \bigcap \{N(x) \cap N(z^*) : z \in F(x) \setminus F(y_i)\}$, it can be done in $O(m)$ time. There are now two cases.

(a) Assume the existence of an edge $uv$ where $u \in B_1, v \in B_2$. If $\max\{e(u), e(v)\} > e(x)$ then, by Lemma 19, we can assert that $x$ is a central vertex. Otherwise, we prove next that $F(u), F(v)$ are not comparable by inclusion, and therefore we can output $u, v$. Indeed, $F(y_1), F(x) \cap F(y_2)$ are not comparable by inclusion because

$$|F(x) \cap F(y_2)| = |F(x)| - f_x(y_2) \ge |F(x)| - f_x(y_1) = |F(y_1)|$$

and $z_1 \in F(y_1) \setminus F(y_2)$. Furthermore, $F(x) \cap F(u) \subseteq F(y_1)$ ($F(x) \cap F(v) \subseteq F(y_2)$, respectively) because $u \in B_1$ ($v \in B_2$, respectively). Then, $F(u) \cap F(x) = F(y_1)$ and $F(v) \cap F(x) = F(y_2) \cap F(x)$, because otherwise this would contradict the maximality of either $f_x(y_1)$ or $f_x(y_2)$.

(b) Finally, assume that every vertex of $B_1$ is nonadjacent to every vertex of $B_2$. We claim that $x$ is a central vertex. Suppose by contradiction $e(x) = rad(G) + 1$. Let $z \in \text{proj}(x, C(G))$ be arbitrary. By Lemma 36, there exist vertices $u, v \in N(x) \cap N(z)$ such that $F(u) \subseteq F(x) \cap F(y_1) = F(y_1)$, $F(v) \subseteq F(x) \cap F(y_2)$. Note that $\max\{e(u), e(v)\} \le e(z) + 1 = rad(G) + 1$. Since $x$ is a local minimum for the eccentricity function, we obtain $e(u) = e(v) = rad(G) + 1$. Then, $u \in B_1, v \in B_2$. In particular, $u, v$ must be nonadjacent, thus contradicting the convexity of $D(x, 1) \cap D(z, 1)$, and so, Theorem 5. $\square$

We leave as an open question whether there exists a linear-time algorithm for computing a central vertex in an $\alpha_1$-metric graph.
## 3.4 Approximating all eccentricities in $\alpha_1$-metric graphs

It follows from the results of Section 3.3 and Section 2.2 that a vertex with eccentricity at most $rad(G) + 1$ and a vertex with eccentricity at least $diam(G) - 5$ can be found in linear time for every $\alpha_1$-metric graph $G$. Furthermore, all vertex eccentricities with an additive one-sided error at most 5 in an $\alpha_1$-metric graph can be computed in total linear time (see Section 2.3). Here, we present two immediate consequences of the results of Section 3, hereby answering some open questions from [25, 32].

**Theorem 10.** Every $\alpha_1$-metric graph $G$ admits an eccentricity 3-approximating spanning tree. Furthermore, an additive 4-approximation of all vertex eccentricities in $G$ can be computed in subquadratic total time.

*Proof.* It is sufficient to show that any breadth-first-search tree $T$ of $G$ rooted at a vertex $c \in C(G)$ is an eccentricity 4-approximating spanning tree of $G$ and any breadth-first-search tree $T$ of $G$ rooted at a vertex $c \in C(C(G))$ (i.e., a central vertex of the subgraph of $G$ that is induced by $C(G)$) is an eccentricity 3-approximating spanning tree of $G$. We do not know how to find efficiently a vertex $c \in C(C(G))$ but, by Theorem 8, a central vertex $c$ of $G$ with $m$ edges can be computed in $O(m^{1.71})$ time.

Consider an arbitrary vertex $v$ in $G$ and let $v'$ be a vertex of $C(G)$ closest to $v$. By Corollary 8, $e(v) \ge d(v, v') + rad(G) - \epsilon$, where $\epsilon \le 1$. Since $T$ is a shortest path tree and $c$ is a central vertex of $G$, $e_T(v) \le d_T(v, c) + e_T(c) = d_G(v, c) + e_G(c) = d_G(v, c) + rad(G)$. Hence, by the triangle inequality, $e_T(v) - e_G(v) \le d_G(v, c) + rad(G) - d_G(v, v') - rad(G) + \epsilon \le d_G(c, v') + \epsilon \le d_G(c, v') + 1$.

By Corollary 11, we know $diam(C(G)) \le 3$ and $rad(C(G)) \le 2$. Hence, if $c \in C(G)$ then $d_G(c, v') \le 3$, and if $c \in C(C(G))$ then $d_G(c, v') \le 2$. $\square$

For $(\alpha_1, \Delta)$-metric graphs this result can be strengthened further.

**Theorem 11.** Every $(\alpha_1, \Delta)$-metric graph $G$ admits an eccentricity 2-approximating spanning tree. Furthermore, an additive 3-approximation of all vertex eccentricities in $G$ with $m$ edges can be computed in total $O(m)$ time.

*Proof.* Let $T$ be a BFS($c$)-tree, where $c$ is a central vertex of $G$. We can follow the proof of Theorem 10 and get $e_T(v) - e_G(v) \le d_G(c, v') + \epsilon$, where $v'$ is a vertex of $C(G)$ closest to $v$. In an $(\alpha_1, \Delta)$-metric graph $G$, we have $\epsilon \le 1$, if $diam(G) = 2rad(G)$, and $\epsilon = 0$, otherwise [32]. Furthermore, when $diam(G) = 2rad(G)$, $diam(C(G)) \le 2$ and $rad(C(G)) \le 1$ must hold [32]. Thus, if $c \in C(G)$ then $e_T(v) - e_G(v) \le d_G(c, v') + \epsilon \le diam(C(G)) + \epsilon \le 3$ (i.e., $\le 3 + 0$ or $\le 2 + 1$), and if $c \in C(C(G))$ then $e_T(v) - e_G(v) \le d_G(c, v') + \epsilon \le rad(C(G)) + \epsilon \le 2$ (i.e., $\le 2 + 0$ or $\le 1 + 1$). Note also that a central vertex of an $(\alpha_1, \Delta)$-metric graph can be computed in linear time (Theorem 9). $\square$

The existence of an eccentricity 2-approximating spanning tree in an $(\alpha_1, \Delta)$-metric graph is known already from [32]. The second part of Theorem 11 provides an answer to an open question from [25].

# 4 Concluding remarks

We conclude the paper with some immediate questions building off our results.
## 3.4 Approximating all eccentricities in $\alpha_1$-metric graphs

It follows from the results of Section 3.3 and Section 2.2 that a vertex with eccentricity at most $\mathrm{rad}(G) + 1$ and a vertex with eccentricity at least $\mathrm{diam}(G) - 5$ can be found in linear time for every $\alpha_1$-metric graph $G$. Furthermore, all vertex eccentricities with an additive one-sided error at most 5 in an $\alpha_1$-metric graph can be computed in total linear time (see Section 2.3). Here, we present two immediate consequences of the results of Section 3, hereby answering some open questions from [25, 32].

**Theorem 10.** Every $\alpha_1$-metric graph $G$ admits an eccentricity 3-approximating spanning tree. Furthermore, an additive 4-approximation of all vertex eccentricities in $G$ can be computed in subquadratic total time.

*Proof.* It is sufficient to show that any breadth-first-search tree $T$ of $G$ rooted at a vertex $c \in C(G)$ is an eccentricity 4-approximating spanning tree of $G$ and any breadth-first-search tree $T$ of $G$ rooted at a vertex $c \in C(C(G))$ (i.e., a central vertex of the subgraph of $G$ that is induced by $C(G)$) is an eccentricity 3-approximating spanning tree of $G$. We do not know how to find efficiently a vertex $c \in C(C(G))$ but, by Theorem 8, a central vertex $c$ of $G$ with $m$ edges can be computed in $O(m^{1.71})$ time.

Consider an arbitrary vertex $v$ in $G$ and let $v'$ be a vertex of $C(G)$ closest to $v$. By Corollary 8, $e(v) \ge d(v, v') + \mathrm{rad}(G) - \epsilon$, where $\epsilon \le 1$. Since $T$ is a shortest path tree and $c$ is a central vertex of $G$, $e_T(v) \le d_T(v, c) + e_T(c) = d_G(v, c) + e_G(c) = d_G(v, c) + \mathrm{rad}(G)$. Hence, by the triangle inequality, $e_T(v) - e_G(v) \le d_G(v, c) + \mathrm{rad}(G) - d_G(v, v') - \mathrm{rad}(G) + \epsilon \le d_G(c, v') + \epsilon \le d_G(c, v') + 1$.

By Corollary 11, we know $\mathrm{diam}(C(G)) \le 3$ and $\mathrm{rad}(C(G)) \le 2$. Hence, if $c \in C(G)$ then $d_G(c, v') \le 3$, and if $c \in C(C(G))$ then $d_G(c, v') \le 2$. $\square$

For $(\alpha_1, \Delta)$-metric graphs this result can be strengthened further.

**Theorem 11.** Every $(\alpha_1, \Delta)$-metric graph $G$ admits an eccentricity 2-approximating spanning tree. Furthermore, an additive 3-approximation of all vertex eccentricities in $G$ with $m$ edges can be computed in total $O(m)$ time.

*Proof.* Let $T$ be a BFS($c$)-tree, where $c$ is a central vertex of $G$. We can follow the proof of Theorem 10 and get $e_T(v) - e_G(v) \le d_G(c, v') + \epsilon$, where $v'$ is a vertex of $C(G)$ closest to $v$. In an $(\alpha_1, \Delta)$-metric graph $G$, we have $\epsilon \le 1$, if $\mathrm{diam}(G) = 2\mathrm{rad}(G)$, and $\epsilon = 0$, otherwise [32]. Furthermore, when $\mathrm{diam}(G) = 2\mathrm{rad}(G)$, $\mathrm{diam}(C(G)) \le 2$ and $\mathrm{rad}(C(G)) \le 1$ must hold [32]. Thus, if $c \in C(G)$ then $e_T(v) - e_G(v) \le d_G(c, v') + \epsilon \le \mathrm{diam}(C(G)) + \epsilon \le 3$ (i.e., $\le 3 + 0$ or $\le 2 + 1$), and if $c \in C(C(G))$ then $e_T(v) - e_G(v) \le d_G(c, v') + \epsilon \le \mathrm{rad}(C(G)) + \epsilon \le 2$ (i.e., $\le 2 + 0$ or $\le 1 + 1$). Note also that a central vertex of an $(\alpha_1, \Delta)$-metric graph can be computed in linear time (Theorem 9). $\square$

The existence of an eccentricity 2-approximating spanning tree in an $(\alpha_1, \Delta)$-metric graph is known already from [32]. The second part of Theorem 11 provides an answer to an open question from [25].

# 4 Concluding remarks

We conclude the paper with some immediate questions building off our results.
1. Can our (approximation) bounds on eccentricities in general $\alpha_i$-metric graphs be improved? In particular,

i) is our bound on the eccentricity of a middle vertex of a shortest path between two mutually distant vertices best possible?

ii) is our bound on the eccentricity of a vertex furthest from an arbitrary vertex sharp?

iii) can our bound $3i + 2$ on the diameter of the center be improved to $2i + 1$?

2. What best approximations of the radius and of the diameter of an $\alpha_1$-metric graph $G$ can be achieved in linear time? In particular,

iv) does there exist a linear-time algorithm for finding a central vertex (and, hence, the exact radius) of an $\alpha_1$-metric graph?

v) is it possible to show that the eccentricity of a vertex furthest from an arbitrary vertex is at least $diam(G) - 2$?

vi) can a vertex with eccentricity at least $diam(G) - 1$ be found in linear time?

Recall that in chordal graphs (a subclass of $\alpha_1$-metric graphs) a central vertex can be found in linear time and the eccentricity of a vertex furthest from an arbitrary vertex is at least $diam(G) - 2$ [16]. Furthermore, a vertex with eccentricity at least $diam(G) - 1$ can be found in linear time by a LexBFS [34]. On the other hand, computing the exact diameter of a chordal graph in subquadratic time is impossible unless the well known Strong Exponential Time Hypothesis (SETH) is false [6].

# 5 Declatration

**Funding:** G.D. 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. F.F.D. did not receive support from any organization for the submitted work.

**Competing interests:** The authors have no competing interests to declare that are relevant to the content of this article.

# References

1. A. Abboud, V. Vassilevska Williams, and J. Wang, Approximation and fixed parameter 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.
1. Can our (approximation) bounds on eccentricities in general $\alpha_i$-metric graphs be improved? In particular,

i) is our bound on the eccentricity of a middle vertex of a shortest path between two mutually distant vertices best possible?

ii) is our bound on the eccentricity of a vertex furthest from an arbitrary vertex sharp?

iii) can our bound $3i + 2$ on the diameter of the center be improved to $2i + 1$?

2. What best approximations of the radius and of the diameter of an $\alpha_1$-metric graph $G$ can be achieved in linear time? In particular,

iv) does there exist a linear-time algorithm for finding a central vertex (and, hence, the exact radius) of an $\alpha_1$-metric graph?

v) is it possible to show that the eccentricity of a vertex furthest from an arbitrary vertex is at least $diam(G) - 2$?

vi) can a vertex with eccentricity at least $diam(G) - 1$ be found in linear time?

Recall that in chordal graphs (a subclass of $\alpha_1$-metric graphs) a central vertex can be found in linear time and the eccentricity of a vertex furthest from an arbitrary vertex is at least $diam(G) - 2$ [16]. Furthermore, a vertex with eccentricity at least $diam(G) - 1$ can be found in linear time by a LexBFS [34]. On the other hand, computing the exact diameter of a chordal graph in subquadratic time is impossible unless the well known Strong Exponential Time Hypothesis (SETH) is false [6].

# 5 Declatration

**Funding:** G.D. 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. F.F.D. did not receive support from any organization for the submitted work.

**Competing interests:** The authors have no competing interests to declare that are relevant to the content of this article.

# References

1. A. Abboud, V. Vassilevska Williams, and J. Wang, Approximation and fixed parameter 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, Moldova 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. WG 2023, Lecture Notes in Computer Science 14093, 276-290.

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 outerplanar 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.
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, Moldova 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. WG 2023, Lecture Notes in Computer Science 14093, 276-290.

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 outerplanar 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).
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).