11institutetext: Computer Science Department, Kent State University, Kent, USA
11email<EMAIL_ADDRESS>22institutetext: National Institute for Research
and Development in Informatics and University of Bucharest, Bucureşti, România
22email<EMAIL_ADDRESS>33institutetext: Department of Mathematical
and Computational Sciences, The College of Wooster, Wooster, USA
33email<EMAIL_ADDRESS>
# Fast deterministic algorithms for computing all eccentricities in
(hyperbolic) Helly graphs

Feodor F. Dragan 11 Guillaume Ducoffe 22 Heather M. Guarnera 33

###### Abstract

A graph is Helly if every family of pairwise intersecting balls has a nonempty
common intersection. The class of Helly graphs is the discrete analogue of the
class of hyperconvex metric spaces. It is also known that every graph
isometrically embeds into a Helly graph, making the latter an important class
of graphs in Metric Graph Theory. We study diameter, radius and all
eccentricity computations within the Helly graphs. Under plausible complexity
assumptions, neither the diameter nor the radius can be computed in truly
subquadratic time on general graphs. In contrast to these negative results, it
was recently shown that the radius and the diameter of an $n$-vertex $m$-edge
Helly graph $G$ can be computed with high probability in
$\tilde{\mathcal{O}}(m\sqrt{n})$ time (i.e., subquadratic in $n+m$). In this
paper, we improve that result by presenting a deterministic
${\mathcal{O}}(m\sqrt{n})$ time algorithm which computes not only the radius
and the diameter but also all vertex eccentricities in a Helly graph.
Furthermore, we give a parameterized linear-time algorithm for this problem on
Helly graphs, with the parameter being the Gromov hyperbolicity $\delta$. More
specifically, we show that the radius and a central vertex of an $m$-edge
$\delta$-hyperbolic Helly graph $G$ can be computed in $\mathcal{O}(\delta m)$
time and that all vertex eccentricities in $G$ can be computed in
$\mathcal{O}(\delta^{2}m)$ time. To show this more general result, we heavily
use our new structural properties obtained for Helly graphs.

##  1 Introduction

Given an undirected unweighted graph $G=(V,E)$, the distance $d_{G}(u,v)$
between two vertices $u$ and $v$ is the minimum number of edges on any path
connecting $u$ and $v$ in $G$. The eccentricity $e_{G}(u)$ of a vertex $u$ is
the maximum distance from $u$ to any other vertex. The radius and the diameter
of $G$, denoted by $rad(G)$ and $diam(G)$, are the smallest and the largest
eccentricities of vertices in $G$, respectively. A vertex with eccentricity
equal to $rad(G)$ is called a central vertex of $G$. We are interested in the
fundamental problems of finding a central vertex and of computing the diameter
and the radius of a graph. The problem of finding a central vertex of a graph
is one of the most famous facility location problems in Operation Research and
in Location Science. The diameter and radius of a graph play an important role
in the design and analysis of networks in a variety of networking environments
like social networks, communication networks, electric power grids, and
transportation networks. A naive algorithm which runs breadth-first-search
from each vertex to compute its eccentricity and then (in order to compute the
radius, the diameter and a central vertex) picks the smallest and the largest
eccentricities and a vertex with smallest eccentricity has running time
${\mathcal{O}}(nm)$ on an $n$-vertex $m$-edge graph. Interestingly, this naive
algorithm is conditionally optimal for general graphs as well as for some
restricted families of graphs [1, 10, 23, 66] since, under plausible
complexity assumptions, neither the diameter nor the radius can be computed in
truly subquadratic time on those graphs. Already for split graphs (a subclass
of chordal graphs), computing the diameter is roughly equivalent to Disjoint
Sets, a.k.a., the monochromatic Orthogonal Vector problem [19]. Under the
Strong Exponential-Time Hypothesis (SETH), we cannot solve Disjoint Sets in
truly subquadratic time [69], and so neither we can compute the diameter of
split graphs in truly subquadratic time [10].

In a quest to break this quadratic barrier (in the size $n+m$ of the input),
there has been a long line of work presenting more efficient algorithms for
computing the diameter and/or the radius on some special graph classes, by
exploiting their geometric and tree-like representations and/or some forbidden
pattern (e.g., excluding a minor, or a family of induced subgraphs). For
example, although the diameter of a split graph can unlikely be computed in
subquadratic time, there is an elegant linear-time algorithm for computing the
radius and a central vertex of a chordal graph [20]. Efficient algorithms for
computing the diameter and/or the radius or finding a central vertex are also
known for interval graphs [40, 63], AT-free graphs [44], directed path graphs
[24], distance-hereditary graphs [26, 32, 35, 39], strongly chordal graphs
[28], dually chordal graphs [11, 31], chordal bipartite graphs [48],
outerplanar graphs [53], planar graphs [15, 55], graphs with bounded clique-
width [26, 47], graphs with bounded tree-width [1, 13, 51] and, more
generally, $H$-minor free graphs and graphs of bounded (distance) VC-dimension
[51]. See also [22, 23, 43, 46, 50, 52] for other examples.

We here study the Helly graphs as a broad generalization of dually chordal
graphs which in turn contain all interval graphs, directed path graphs and
strongly chordal graphs. Recall that a graph is Helly if every family of
pairwise intersecting balls has a non-empty common intersection. This latter
property on the balls will be simply referred to as the Helly property in what
follows. Helly graphs have unbounded tree-width and unbounded clique-width,
they do not exclude any fixed minor and they cannot be characterized via some
forbidden structures. They are sometimes called absolute retracts or disk-
Helly graphs by opposition to other Helly-type properties on graphs [27]. The
Helly graphs are well studied in Metric Graph Theory. E.g., see the survey [5]
and the papers cited therein. This is partly because every graph is an
isometric subgraph of some Helly graph, thereby making of the latter the
discrete equivalent of hyperconvex metric spaces [42, 57]. A minimal by
inclusion Helly graph $H$ which contains a given graph $G$ as an isometric
subgraph is unique and called the injective hull [57] or the tight span [42]
of $G$. Polynomial-time recognition algorithms for the Helly graphs were
presented in [6, 28, 61]. Several structural properties of these graphs were
also identified in [6, 7, 8, 18, 28, 29, 30, 33, 34, 64, 65]. The dually
chordal graphs are exactly the Helly graphs in which the intersection graph of
balls is chordal, and they were studied independently from the general Helly
graphs [11, 12, 41, 31, 33, 68]. As we already mentioned it [11, 41, 31], the
diameter, the radius and a central vertex of a dually chordal graph can be
found in linear time, that is optimal. However, it was open until recently
whether there are truly subquadratic-time algorithms for these problems on
general Helly graphs. First such algorithms were recently presented in [49]
for computing both the radius and the diameter and in [45] for finding a
central vertex. Those algorithms are randomized and run, with high
probability, in $\tilde{\mathcal{O}}(m\sqrt{n})$ time on a given $n$-vertex
$m$-edge Helly graph (i.e., subquadratic in $n+m$). They make use of the Helly
property and of the unimodality of the eccentricity function in Helly graphs
[29]: every vertex of locally minimum eccentricity is a central vertex. In
[49], a linear-time algorithm for computing all eccentricities in $C_{4}$-free
Helly graphs was also presented. The $C_{4}$-free Helly graphs are exactly the
Helly graphs whose balls are convex. They properly include strongly chordal
graphs as well as bridged Helly graphs and hereditary Helly graphs [49].

#### Our Contribution.

We improve those results from [49] and [45] by presenting a deterministic
${\mathcal{O}}(m\sqrt{n})$ time algorithm which computes not only the radius
and the diameter but also all vertex eccentricities in an $n$-vertex $m$-edge
Helly graph. This is our first main result in the paper. Being able to
efficiently compute all vertex eccentricities is of great importance. For
example, in the analysis of social networks (e.g., citation networks or
recommendation networks), biological systems (e.g., protein interaction
networks), computer networks (e.g., the Internet or peer-to-peer networks),
transportation networks (e.g., public transportation or road networks), etc.,
the eccentricity $e_{G}(v)$ of a vertex $v$ is used to measure its importance
in the network: the eccentricity centrality index of $v$ [60] is defined as
$\frac{1}{e_{G}(v)}$.

Our second main result is a parameterized linear-time algorithm for computing
all vertex eccentricities in Helly graphs, with the parameter being the Gromov
hyperbolicity $\delta$, as defined by the following four point condition. The
hyperbolicity of a graph $G$ [56] is the smallest half-integer $\delta\geq 0$
such that, for any four vertices $u,v,w,x$, the two largest of the three
distance sums $d(u,v)+d(w,x)$, $d(u,w)+d(v,x)$, $d(u,x)+d(v,w)$ differ by at
most $2\delta$. In this case we say that $G$ is $\delta$-hyperbolic. As the
tree-width of a graph measures its combinatorial tree-likeness, so does the
hyperbolicity of a graph measure its metric tree-likeness. In other words, the
smaller the hyperbolicity $\delta$ of $G$ is, the closer $G$ is to a tree
metrically. The hyperbolicity of an $n$-vertex graph can be computed in
polynomial-time (e.g., in ${\mathcal{O}}(n^{3.69})$ time [54]), however it is
unlikely that it can be done in subquadratic time [10, 25, 54]. A
2-approximation of hyperbolicity can be computed in ${\mathcal{O}}(n^{2.69})$
time [54] and an 8-approximation can be computed in ${\mathcal{O}}(n^{2})$
time [16] (assuming that the input is the distance matrix of the graph). Graph
hyperbolicity has attracted attention recently due to the empirical evidence
that it takes small values in many real-world networks, such as biological
networks, social networks, Internet application networks, and collaboration
networks, to name a few (see, e.g., [2, 3, 9, 58, 62, 67]). Furthermore, many
special graph classes (e.g., interval graphs, chordal graphs, dually chordal
graphs, AT-free graphs, weakly chordal graphs and many others) have constant
hyperbolicity [2, 4, 14, 21, 34, 38, 59, 70]. In fact, the dually chordal
graphs and the $C_{4}$-free Helly graphs are known to be proper subclasses of
the $1$-hyperbolic Helly graphs (this follows from results in [12, 34]).
Notice also that any graph is $\delta$-hyperbolic for some $\delta\leq
diam(G)/2$.

We show that the radius and a central vertex of an $m$-edge Helly graph $G$
with hyperbolicity $\delta$ can be computed in $\mathcal{O}(\delta m)$ time
and that all vertex eccentricities in $G$ can be computed in
${\mathcal{O}}(\delta^{2}m\log\delta)$ time, even if $\delta$ is not known to
us. If either $\delta$ or a constant approximation of it is known, then the
running time of our algorithm can be lowered to $\mathcal{O}(\delta^{2}m)$.
Thus, for Helly graphs with constant hyperbolicity, all vertex eccentricities
can be computed in linear time. As a byproduct, we get a linear time algorithm
for computing all eccentricities in $C_{4}$-free Helly graphs as well as in
dually chordal graphs, generalizing known results from [11, 31, 49].
Previously, for dually chordal graphs, it was only known that a central vertex
can be found in linear time [11, 31]. Notice that the diameter problem can
unlikely be solved in truly subquadratic time in general 1-hyperbolic graphs
and that the radius problem can unlikely be solved in truly subquadratic time
in general 2-hyperbolic graphs [23]. For general $\delta$-hyperbolic graphs,
there are only additive $\mathcal{O}(\delta)$-approximations of the diameter
and the radius, that can be computed in linear time [21, 36, 37].

To show our more general results, additionally to the unimodality of the
eccentricity function in Helly graphs, we rely on new structural properties
obtained for this class. It turns out that the hyperbolicity of a Helly graph
$G$ is governed by the size of a largest isometric rectilinear grid in $G$. As
a consequence, the hyperbolicity of an $n$-vertex Helly graph is at most
$\sqrt{n}+1$ and the diameter of the center $C(G)$ of $G$ is at most
$2\sqrt{n}+3$. These properties, along with others, play a crucial role in
efficient computations of all eccentricities in Helly graphs. We also give new
characterizations of the class of Helly graphs. Among others, we show that the
Helly property for balls of equal radii implies the Helly property for balls
with variable radii. It would be interesting to know whether a similar result
holds for all (discrete) metric spaces. We are not aware of such a general
result.

#### Notations.

Recall that $d_{G}(u,v)$ denotes the distance between vertices $u$ and $v$ in
$G=(V,E)$. Let $n=|V|$ be the number of vertices and $m=|E|$ be the number of
edges in $G$. The ball of radius $r$ and center $v$ is defined as $\\{u\in
V:d_{G}(u,v)\leq r\\}$, and denoted by $N_{G}^{r}[v]$. Sometimes,
$N_{G}^{r}[v]$ is called the $r$-neighborhood of $v$. In particular,
$N_{G}[v]:=N_{G}^{1}[v]$ and $N_{G}(v):=N_{G}[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_{G}(u,S):=\min_{v\in
S}d_{G}(u,v),\ N_{G}^{r}[S]:=\bigcup_{v\in S}N_{G}^{r}[v],\
N_{G}[S]:=N_{G}^{1}[S]\ \text{and}\ N_{G}(S):=N_{G}[S]\setminus S$. The metric
projection of a vertex $u$ on $S$, denoted by $Pr_{G}(u,S)$, is defined as
$\\{v\in S:d_{G}(u,v)=d_{G}(u,S)\\}$. The metric interval $I_{G}(u,v)$ between
$u$ and $v$ is $\\{w\in V:d_{G}(u,w)+d_{G}(w,v)=d_{G}(u,v)\\}$. For any $k\leq
d_{G}(u,v)$, we can also define the slice $L(u,k,v):=\\{w\in
I_{G}(u,v):d_{G}(u,w)=k\\}$. Recall that the eccentricity of a vertex $u$ is
defined as $\max_{v\in V}d_{G}(u,v)$ and denoted by $e_{G}(u)$. Note that we
will omit the subscript if the graph $G$ is clear from the context. The radius
and the diameter of a graph $G$ are denoted by $rad(G)$ and $diam(G)$,
respectively. A vertex $c$ is called central in $G$ if $e_{G}(c)=rad(G)$. The
set of all central vertices of $G$ is denoted by $C(G):=\\{v\in
V:e_{G}(v)=rad(G)\\}$ and called the center of $G$. The eccentricity function
$e_{G}(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_{G}(v)$ such that
$e_{G}(u)<e_{G}(v)$ (that is, every local minimum of the eccentricity function
is a global minimum). Recall also that a vertex set $S\subseteq V$ is called
convex in $G$ if, for every vertices $x,y\in S$, all shortest paths connecting
them are contained in $S$ (i.e., $I_{G}(x,y)\subseteq S$). For $\beta\geq 0$,
we say that $S$ is $\beta$-_pseudoconvex_ [36] if, for every vertices $x,y\in
S$, any vertex $z\in I_{G}(x,y)\setminus S$ satisfies
$\min\\{d_{G}(z,x),d_{G}(z,y)\\}\leq\beta$. A subgraph $H$ of $G$ is called
isometric (or distance-preserving) if, for every vertices $x,y$ of $H$,
$d_{G}(x,y)=d_{H}(x,y)$.

##  2 Characterizations of Helly graphs and hyperbolicity in Helly graphs

Here we demonstrate that for Helly graphs, having a constant hyperbolicity is
equivalent to the following properties: having $\beta$-pseudoconvexity of
balls with a constant $\beta$, or having the diameter of the center bounded by
a constant for all subsets of vertices, or not having a large
$(\gamma\times\gamma)$ rectilinear grid as an isometric subgraph. These
results generalize some known results from [17, 21, 34, 36].

First we give new characterizations of Helly graphs through a formula for the
eccentricity function and relations between diameter and radius for all
subsets of vertices. For this we need to generalize our basic notations.
Define for any set $M\subseteq V$ and any vertex $v\in V$ the eccentricity of
$v$ in $G$ with respect to $M$ as follows:

$e_{M}(v)=\max_{u\in M}d_{G}(u,v).$

Let $diam_{M}(G)=\max_{v\in M}e_{M}(v)$, $rad_{M}(G)=\min_{v\in V}e_{M}(v)$,
$C_{M}(G)=\\{v\in V:e_{M}(v)=rad_{M}(G)\\}$. When $M=V$, these agree with
earlier definitions.

###### Theorem 2.1

For a graph $G$ the following statements are equivalent:

  * (1)

$G$ is Helly;

  * (2)

the eccentricity function $e_{M}(\cdot)$ is unimodal for every set $M\subseteq
V$;

  * (3)

$e_{M}(v)=d_{G}(v,C_{M}(G))+rad_{M}(G)$ holds for every set $M\subseteq V$ and
every vertex $v\in V$;

  * (4)

$2rad_{M}(G)-1\leq diam_{M}(G)\leq 2rad_{M}(G)$ holds for every set
$M\subseteq V$;

  * (5)

$rad_{M}(G)=\lfloor\frac{diam_{M}(G)+1}{2}\rfloor$ holds for every set
$M\subseteq V$.

###### Proof

The equivalence (1)$\Leftrightarrow$(2) was proven in [28, 29]. It was also
shown in [28] that (2) and (3) are equivalent for $M=V$. Here, we complete the
proof of all equivalencies. We will show (2)$\Leftrightarrow$(3), when one
considers any set $M\subseteq V$, and
(1)$\Rightarrow$(4)$\Rightarrow$(5)$\Rightarrow$(1).

(2)$\Rightarrow$(3): Let $M$ be any subset of $V$. We will prove the formula
in (3) by induction on $k=e_{M}(v)-rad_{M}(G)$. If $k=0$ then
$e_{M}(v)=rad_{M}(G)$, i.e., $v\in C_{M}(G)$, and the formula is trivially
correct. Consider now a vertex $v$ with $e_{M}(v)>rad_{M}(G)$. By the triangle
inequality, $e_{M}(v)\leq d_{G}(v,C_{M}(G))+rad_{M}(G)$ always holds. As the
eccentricity function $e_{M}(\cdot)$ is unimodal, there is a neighbor $u$ of
$v$ with $e_{M}(v)>e_{M}(u)$. By induction hypothesis,
$e_{M}(u)=d_{G}(u,C_{M}(G))+rad_{M}(G)$. Hence, by the triangle inequality,
$e_{M}(v)\geq e_{M}(u)+1=d_{G}(u,C_{M}(G))+rad_{M}(G)+1\geq
d_{G}(v,C_{M}(G))+rad_{M}(G)$. Combining both inequalities, we get
$e_{M}(v)=d_{G}(v,C_{M}(G))+rad_{M}(G)$.

(3)$\Rightarrow$(2): Let $M$ be any subset of $V$ and $v$ be an arbitrary
vertex of $G$ with $e_{M}(v)>rad_{M}(G)$. Let also $c_{v}$ be a vertex of
$C_{M}(G)$ closest to $v$ and $u$ be a neighbor of $v$ on a shortest path from
$v$ to $c_{v}$. We have
$e_{M}(v)=d_{G}(v,c_{v})+rad_{M}(G)=1+d_{G}(u,c_{v})+rad_{M}(G)\geq
1+d_{G}(u,C_{M}(G))+rad_{M}(G)=1+e_{M}(u)$. In particular,
$e_{M}(v)>e_{M}(u)$.

(1)$\Rightarrow$(4): It is clear that $diam_{M}(G)\leq 2rad_{M}(G)$ holds for
every graph $G$ and every set $M\subseteq V$ (by the triangle inequality).
Assume now that for a subset $M$ of $V$, $diam_{M}(G)\leq 2rad_{M}(G)-2$
holds. For every vertex $v$ in $M$, consider a ball centered at $v$ and with
radius $rad_{M}(G)-1$. All these balls pairwise intersect as $diam_{M}(G)\leq
2rad_{M}(G)-2$. By the Helly property, there must exist a vertex $c$ in $G$
such that $d_{G}(c,v)\leq rad_{M}(G)-1$ for every $v\in M$. The latter implies
that $e_{M}(c)\leq rad_{M}(G)-1$, giving a contradiction.

(4)$\Rightarrow$(5): It is straightforward.

(5)$\Rightarrow$(1): We know that a graph $G$ is Helly if and only if the
family of unit balls of $G$ has the Helly property and for any three vertices
$x,y,v$ with $d_{G}(x,y)\leq 2$ and $d_{G}(x,v)=d_{G}(y,v)=k\geq 2$ there
exists a common neighbor $u$ of $x$ and $y$ such that $d_{G}(v,u)=k-1$ (see
[6, 28, 29]).

Consider in $G$ a family $\mathfrak{F}$ of pairwise intersecting unit balls
with centers at vertices $v_{1},\dots,v_{q}$. Define
$M=\\{v_{1},\dots,v_{q}\\}$. As the balls pairwise intersect,
$d_{G}(v_{i},v_{j})\leq 2$ for each $i,j\in\\{1,\dots,q\\}$. Hence,
$diam_{M}(G)\leq 2$ and therefore
$rad_{M}(G)=\lfloor\frac{diam_{M}(G)+1}{2}\rfloor\leq 1$. The latter implies
the existence of a vertex $c$ in $G$ with $d_{G}(c,v_{i})\leq 1$ for all
$i\in\\{1,\dots,q\\}$. Necessarily, $c$ belongs to all unit balls from
$\mathfrak{F}$. In other words, the family of unit balls of $G$ has the Helly
property.

Let $x,y,v$ be any three vertices of $G$ with $d_{G}(x,y)\leq 2$ and
$d_{G}(x,v)=d_{G}(y,v)=k\geq 2$. We will show by induction on $k$ that there
exists a common neighbor $u$ of $x$ and $y$ such that $d_{G}(v,u)=k-1$. If
$k=2$ then the existence of $u$ follows from the Helly property for the family
of unit balls of $G$. Assume now that $k>2$ and first consider the case when
$k$ is even, say $k=2\ell$. Let $M=\\{x,y,v\\}$. As $k>2$,
$diam_{M}(G)=k=2\ell$ and therefore
$rad_{M}(G)=\lfloor\frac{diam_{M}(G)+1}{2}\rfloor=\ell$. Hence, there is a
vertex $c$ in $G$ such that $d_{G}(c,v)=d_{G}(c,x)=d_{G}(c,y)=\ell$. Notice
that $\ell\geq 2$. By induction, there must exist a common neighbor $u$ of $x$
and $y$ such that $d_{G}(c,u)=\ell-1$. Necessarily, $d_{G}(u,v)=2\ell-1=k-1$.
Assume now that $k$ is odd, say $k=2\ell+1$. If $k\geq 5$ then consider a
neighbor $x^{\prime}$ of $x$ on a shortest path from $x$ to $v$ and a neighbor
$y^{\prime}$ of $y$ on a shortest path from $y$ to $v$. Let
$M=\\{x^{\prime},y^{\prime},v\\}$. As
$d_{G}(x^{\prime},v)=d_{G}(y^{\prime},v)=k-1\geq 4$ and
$d_{G}(x^{\prime},y^{\prime})\leq 4$, $diam_{M}(G)=k-1=2\ell$ and therefore
$rad_{M}(G)=\lfloor\frac{diam_{M}(G)+1}{2}\rfloor=\ell$. Hence, there is a
vertex $c$ in $G$ such that
$d_{G}(c,v)=d_{G}(c,x^{\prime})=d_{G}(c,y^{\prime})=\ell$. Since
$d_{G}(c,x)=d_{G}(c,y)=\ell+1$, by induction, there must exist a common
neighbor $u$ of $x$ and $y$ such that $d_{G}(c,u)=\ell$. Necessarily,
$d_{G}(u,v)=2\ell=k-1$.

It remains to consider the case when $k=3$. Let $M=I_{G}(x,v)\cup I_{G}(y,v)$.
We have $3\leq diam_{M}(G)\leq 4$ and therefore $rad_{M}(G)=2$. The latter
implies existence of a vertex $c$ in $G$ such that $d_{G}(c,w)\leq 2$ for all
$w\in M$. Consider a neighbor $v_{x}$ of $v$ on a shortest path from $v$ to
$x$ and a neighbor $v_{y}$ of $v$ on a shortest path from $v$ to $y$. Since
$d_{G}(c,v_{x})\leq 2$, $d_{G}(c,x)\leq 2$ and $d_{G}(x,v_{x})=2$, the three
unit balls centered at vertices $x,c,v_{x}$ pairwise intersect. By the Helly
property for unit balls, there must exist a vertex $x^{\prime}$ in $G$ which
is adjacent to $x$ and $v_{x}$ and at distance at most 1 from $c$. By
symmetry, there exists also a vertex $y^{\prime}$ in $G$ which is adjacent to
$y$ and $v_{y}$ and at distance at most 1 from $c$. Since
$d_{G}(v,x^{\prime})=d_{G}(v,y^{\prime})=2$ and
$d_{G}(x^{\prime},y^{\prime})\leq d_{G}(c,x^{\prime})+d_{G}(c,y^{\prime})\leq
2$, by induction, there is a vertex $v^{\prime}$ in $G$ adjacent to all
$x^{\prime},y^{\prime},v$. Applying again the induction hypothesis to
$v^{\prime},x,y$, we get a vertex $u$ in $G$ which is adjacent to all
$v^{\prime},x,y$ and hence at distance 2 from $v$. This concludes the proof. ∎

The equivalence between (1) and (5) can be rephrased as follows.

###### Corollary 1

For every graph $G=(V,E)$, the family of all balls $\\{N^{r}_{G}[v]:v\in
V,r\in\mathbb{N}\\}$ of $G$ has the Helly property if and only if the family
of $k$-neighborhoods $\\{N^{k}_{G}[v]:v\in V\\}$ of $G$ has the Helly property
for every natural number $k$.

That is, the Helly property for balls of equal radii implies the Helly
property for balls with variable radii. It would be interesting to know
whether a similar result holds for all (discrete) metric spaces. We are not
aware of such a general result and did not find its analog in the literature.

###### Proof

It is sufficient to prove that if the family of $k$-neighborhoods
$\\{N^{k}_{G}[v]:v\in V\\}$ of $G$ has the Helly property for every natural
number $k$, then $G$ satisfies the condition (5) of Theorem 2.1.

Consider an arbitrary set $M\subseteq V$. Denote
$k:=\lfloor\frac{diam_{M}(G)+1}{2}\rfloor$. Since $d_{G}(x,y)\leq diam_{M}(G)$
for every pair $x,y$ of vertices from $M$, the family of $k$-neighborhoods
$\\{N^{k}_{G}[v]:v\in M\\}$ of $G$ consists of pairwise intersecting sets. By
the Helly property, there is a vertex $c\in V$ which belongs to all those
$k$-neighborhoods. Necessarily, $d_{G}(c,v)\leq k$ holds for every $v\in M$.
Hence, $rad_{M}(G)\leq k=\lfloor\frac{diam_{M}(G)+1}{2}\rfloor$. As
$diam_{M}(G)\leq 2rad_{M}(G)$, we get
$rad_{M}(G)=\lfloor\frac{diam_{M}(G)+1}{2}\rfloor$. ∎

We will also need the following lemma from [28].

###### Lemma 1

[28] For every Helly graph $G=(V,E)$ and every set $M\subseteq V$, the graph
induced by the center $C_{M}(G)$ is Helly and it is an isometric (and hence
connected) subgraph of $G$.

Given this lemma, it will be convenient to denote by $C_{M}(G)$ not only the
set of central vertices but also the subgraph of $G$ induced by this set.
Then, $diam(C_{M}(G))$ denotes the diameter of this graph
($diam(C_{M}(G))=diam_{C_{M}(G)}(G)$ by this isometricity).

Let $\delta(G)$ be the smallest half-integer $\delta\geq 0$ such that $G$ is
$\delta$-hyperbolic. Let $\gamma(G)$ be the largest integer $\gamma\geq 0$
such that $G$ has a $(\gamma\times\gamma)$ rectilinear grid as an isometric
subgraph. Let $\beta(G)$ be the smallest integer $\beta\geq 0$ such that all
balls in $G$ are $\beta$-pseudoconvex. Finally, let $\kappa(G)$ be the
smallest integer $\kappa\geq 0$ such that $diam(C_{M}(G))\leq\kappa$ for every
set $M\subseteq V$.

###### Theorem 2.2

For every Helly graph $G$, a constant bound on one parameter from
$\\{\delta(G),\gamma(G),\beta(G),\kappa(G)\\}$ implies a constant bound on all
others.

###### Proof

Let $\delta:=\delta(G),\gamma:=\gamma(G),\beta:=\beta(G),\kappa:=\kappa(G)$.
We will show that the following inequalities are true using a few claims:

$\kappa\leq\min\\{2\delta+1,2\gamma+3,\max\\{3,2\beta+1\\}\\},$
$\beta\leq\min\\{\max\\{0,2\delta-1\\},2\gamma+1,\kappa+1\\},$
$\gamma\leq\min\\{\delta,\beta,\kappa/2\\},$
$\delta\leq\min\\{\gamma,\beta,\kappa/2\\}+1.$

###### Claim 1

If $G$ is $\delta$-hyperbolic Helly, then $diam(C_{M}(G))\leq 2\delta+1$ and
$rad(C_{M}(G))\leq\delta+1$ for every set $M\subseteq V$. In particular,
$\kappa\leq 2\delta+1$.

Let $M$ be an arbitrary subset of $V$. Let also $d_{G}(x,y)=diam_{M}(G)$ for
$x,y\in M$ and let $d_{G}(u,v)=diam(C_{M}(G))$ for $u,v\in C_{M}(G)$. As $G$
is Helly, $d_{G}(x,y)\geq 2rad_{M}(G)-1$. We consider the following distance
sums: $d_{G}(x,y)+d_{G}(u,v)\geq 2rad_{M}(G)-1+diam(C_{M}(G))$,
$d_{G}(x,u)+d_{G}(v,y)\leq 2rad_{M}(G)$, and $d_{G}(x,v)+d_{G}(y,u)\leq
2rad_{M}(G)$. If $d_{G}(x,y)+d_{G}(u,v)$ is not the largest of the three sums,
then $diam(C_{M}(G))\leq 1$. Otherwise, by the four point condition,
$diam(C_{M}(G))\leq 2\delta+1$. Consider the pairwise intersecting balls
$N^{rad_{M}(G)}_{G}[v]$ for all $v\in M$ and $N^{\delta+1}_{G}[u]$ for all
$u\in C_{M}(G)$. By the Helly property, there is a vertex $c\in C_{M}(G)$ such
that $N^{\delta+1}_{G}[c]\supseteq C_{M}(G)$. As $C_{M}(G)$ is isometric for
any Helly graph (see Lemma 1), the diameter and radius of $C_{M}(G)$ are
realized by paths fully contained in $C_{M}(G)$.

###### Claim 2

If $G$ is $\delta$-hyperbolic, then any ball of $G$ is
$(2\delta-1)$-pseudoconvex, when $\delta>0$, and is convex, when
$0\leq\delta\leq 1/2$. In particular, $\beta\leq\max\\{0,2\delta-1\\}$.

Consider a ball $N^{r}_{G}[v]$ centered at a vertex $v\in V$ and with radius
$r$. Let $x,y\in N^{r}_{G}[v]$ and let $u\in I_{G}(x,y)$ be a vertex which is
not contained in $N^{r}_{G}[v]$. By contradiction, assume that $d_{G}(u,x)\geq
2\delta$ and $d_{G}(u,y)\geq 2\delta$. Since $u\notin N^{r}_{G}[v]$,
$d_{G}(u,v)>r$. Consider the following distance sums:
$d_{G}(x,y)+d_{G}(u,v)=d_{G}(x,u)+d_{G}(u,y)+d_{G}(u,v)>d_{G}(x,u)+d_{G}(u,y)+r$,
$d_{G}(x,u)+d_{G}(v,y)\leq d_{G}(x,u)+r$, and $d_{G}(x,v)+d_{G}(y,u)\leq
r+d_{G}(y,u)$. Clearly, $d_{G}(x,y)+d_{G}(u,v)$ is the largest sum. Without
loss of generality, assume that $d_{G}(x,u)+d_{G}(v,y)$ is the second largest
sum. By the four point condition, $2\delta\geq
d_{G}(x,y)+d_{G}(u,v)-d_{G}(x,u)-d_{G}(v,y)=d_{G}(u,y)+d_{G}(u,v)-d_{G}(v,y)>2\delta+r-r=2\delta$,
which is not possible.

###### Claim 3

If $G$ is a Helly graph whose all balls are $\beta$-pseudoconvex, then for
every set $M\subseteq V$, $diam(C_{M}(G))\leq 3$, when $\beta=0$, and
$diam(C_{M}(G))\leq 2\beta+1$, when $\beta>0$. In particular,
$\kappa\leq\max\\{3,2\beta+1\\}$.

Let $M$ be an arbitrary subset of $V$. Let also $d_{G}(x,y)=diam_{M}(G)$ for
$x,y\in M$ and let $d_{G}(u,v)=diam(C_{M}(G))$ for $u,v\in C_{M}(G)$. It is
known from [28] that if balls in a Helly graph $G$ are convex (i.e.,
$\beta=0$) then $diam(C_{M}(G))\leq 3$. Let now $\beta\geq 1$ and assume, by
way of contradiction, that $d_{G}(u,v)\geq 2\beta+2$. As $G$ is Helly,
$d_{G}(x,y)\geq 2rad_{M}(G)-1$. Set $r:=rad_{M}(G)$. Note that, since we
always have $diam(C_{M}(G))\leq 2r$ and we further assume $diam(C_{M}(G))\geq
2\beta+2$, $r\geq 2$. In particular, $2r-1\geq r+1$. Consider the following
four balls: $N^{r+1}_{G}[y]$, $N^{d_{G}(x,y)-r-1}_{G}[x]$,
$N^{\beta+1}_{G}[u]$ and $N^{d_{G}(u,v)-\beta-1}_{G}[v]$. We show that they
pairwise intersect. Clearly, $N^{r+1}_{G}[y]\cap
N^{d_{G}(x,y)-r-1}_{G}[x]\neq\emptyset$ and $N^{\beta+1}_{G}[u]\cap
N^{d_{G}(u,v)-\beta-1}_{G}[v]\neq\emptyset$. Furthermore, since $d_{G}(u,x)$,
$d_{G}(u,y)$, $d_{G}(v,x)$ and $d_{G}(v,y)$ are at most $r$, the ball
$N^{r+1}_{G}[y]$ intersects both $N^{\beta+1}_{G}[u]$ and
$N^{d_{G}(u,v)-\beta-1}_{G}[v]$. As $(d_{G}(x,y)-r-1)+(\beta+1)\geq
2r-1-r-1+\beta+1=r+\beta-1\geq r\geq d_{G}(u,x)$, the balls
$N^{d_{G}(x,y)-r-1}_{G}[x]$ and $N^{\beta+1}_{G}[u]$ also intersect.
Similarly, the balls $N^{d_{G}(x,y)-r-1}_{G}[x]$ and
$N^{d_{G}(u,v)-\beta-1}_{G}[v]$ must intersect as
$d_{G}(u,v)-\beta-1\geq\beta+1$. As all four balls pairwise intersect, by the
Helly property, there must exist a vertex $c$ in $G$ such that
$d_{G}(u,v)=d_{G}(u,c)+d_{G}(c,v)$ (i.e., $c\in I_{G}(u,v)$) and
$d_{G}(y,c)=r+1$, $d_{G}(x,c)=d_{G}(x,y)-r-1$. The latter contradicts with the
$\beta$-pseudoconvexity of the ball $N^{r}_{G}[y]$ as $u,v$ belong to that
ball and $c\in I_{G}(u,v)$ with $\min\\{d_{G}(c,u),d_{G}(c,v)\\}\geq\beta+1$
is not in $N^{r}_{G}[y]$.

###### Claim 4

For every graph, $\gamma\leq\min\\{\delta,\beta,\kappa/2\\}$.

Consider an isometric $(\gamma\times\gamma)$ rectilinear grid in $G$ and let
$a,b,c,d$ be the corner vertices of that grid listed in counterclockwise
order. The hyperbolicity of $G$ is at least the hyperbolicity of the quadruple
$a,b,c,d$ which is exactly
$(d_{G}(a,c)+d_{G}(b,d))-(d_{G}(a,b)+d_{G}(c,d))=\frac{1}{2}((2\gamma+2\gamma)-(\gamma+\gamma))=\gamma$.
Hence, $\gamma\leq\delta$. For the ball $N^{\gamma}_{G}[a]$, we get: $b,d\in
N^{\gamma}_{G}[a]$, $c\notin N^{\gamma}_{G}[a]$, and $c$ is on a shortest path
between $b$ and $d$ with $d_{G}(c,b)=d_{G}(c,d)=\gamma$. Hence,
$\gamma\leq\beta$. Let now $M=\\{a,c\\}$. Then, $diam_{M}(G)=2\gamma$ and
$rad_{M}(G)=\gamma$ and both $b$ and $d$ are in $C_{M}(G)$. As
$d_{G}(b,d)=2\gamma$, $diam(C_{M}(G))\geq 2\gamma$, giving $\kappa\geq
diam(C_{M}(G))\geq 2\gamma$.

###### Claim 5

For every Helly graph, $\delta\leq\gamma+1$.

This claim follows from a result in [34]. Let the hyperbolicity of $G$ be
$\delta$. According to [34, Lemma 8], if $\delta$ is an integer, then $G$ has
an isometric subgraph (named $H_{1}^{\delta}$ in [34]), which contains an
isometric $(\delta\times\delta)$ rectilinear grid, or an isometric subgraph
(named $H_{3}^{\delta-1}$ in [34]), which contains an isometric
$((\delta-1)\times(\delta-1))$ rectilinear grid. Furthermore, if $\delta$ is a
half-integer, then $G$ has an isometric subgraph (named
$H_{2}^{\delta-\frac{1}{2}}$ in [34]), which contains an isometric
$((\delta-\frac{1}{2})\times(\delta-\frac{1}{2}))$ rectilinear grid. Thus, in
both cases (whether $\delta$ is a half-integer or an integer),
$\gamma\geq\delta-1$ holds.

###### Claim 6

For every Helly graph, $\delta\leq\min\\{\beta,\kappa/2\\}+1$,
$\beta\leq\min\\{\kappa,2\gamma\\}+1$, $\kappa\leq 2\gamma+3$.

These remaining inequalities follow from the previous claims. We have

$\delta\leq\gamma+1\leq\beta+1,$ $\delta\leq\gamma+1\leq\kappa/2+1,$
$\beta\leq\max\\{0,2\delta-1\\}\leq\max\\{0,\kappa+1\\}=\kappa+1,$
$\beta\leq\max\\{0,2\delta-1\\}\leq 2\gamma+1,$ $\kappa\leq 2\delta+1\leq
2\gamma+3.$

This concludes the proof of the theorem. ∎

The following corollaries of Theorem 2.2 will play an important role in
efficient computations of all eccentricities of a Helly graph. Corollary 2
gives a sublinear bound on the hyperbolicity of a Helly graph. Corollary 3
gives a sublinear bound on the diameter of the center of a Helly graph.

###### Corollary 2

The hyperbolicity of an $n$-vertex Helly graph $G$ is at most $\sqrt{n}+1$.

###### Proof

If $G$ is $\delta$-hyperbolic then, by Claim 5, $G$ contains an isometric
rectilinear grid of side-length $\geq\delta-1$. In particular,
$(\delta-1)^{2}\leq n$. ∎

###### Corollary 3

For any $n$-vertex Helly graph $G$, we have $diam(C(G))\leq 2\sqrt{n}+3$.

###### Proof

We apply Corollary 2 and Claim 1 (with $M=V$). Thus, for a $\delta$-hyperbolic
Helly graph $G$, $diam(C(G))\leq 2\delta+1\leq 2\sqrt{n}+3$. ∎

##  3 All eccentricities in Helly graphs

It is known that the radius (see [49]) and a central vertex (see [45]) of an
$n$-vertex $m$-edge Helly graph can be computed in
$\tilde{\mathcal{O}}(m\sqrt{n})$-time with high probability. In this section,
we improve those results by presenting a deterministic
${\mathcal{O}}(m\sqrt{n})$ time algorithm which computes not only the radius
and a central vertex but also all vertex eccentricities in a Helly graph.

To show this more general result, we heavily make use of our new structural
results from Section 2. In particular, the fact that both the hyperbolicity of
a Helly graph $G$ and the diameter of its center $C(G)$ are upper bounded by
${\mathcal{O}}(\sqrt{n})$ will be very handy. The following results from [49],
[45] and [21, 36, 37] will be also very useful.

###### Lemma 2

[49] Let $G$ be an $m$-edge Helly graph and $k$ be a natural number. One can
compute the set of all vertices of $G$ of eccentricity at most $k$, and their
respective eccentricities, in ${\mathcal{O}}(km)$ time.

###### Lemma 3

[45] Let $G$ be an $m$-edge Helly graph and $v$ be an arbitrary vertex. There
is an ${\mathcal{O}}(m)$-time algorithm which either certifies that $v$ is a
central vertex of $G$ or finds a neighbor $u$ of $v$ such that $e(u)<e(v)$.

###### Lemma 4

[21, 36, 37] Let $G$ be an arbitrary $m$-edge graph and $\delta$ be its
hyperbolicity. There is an ${\mathcal{O}}(\delta m)$-time algorithm which
finds in $G$ a vertex $c$ with eccentricity at most $rad(G)+2\delta$. The
algorithm does not need to know the value of $\delta$ in order to work
correctly.

First, by combining Lemmas 3 and 4, we show that a central vertex of a Helly
graph $G$ can be computed in ${\mathcal{O}}(\delta m)$ time, where $\delta$ is
the hyperbolicity of $G$.

###### Lemma 5

If $G$ is an $m$-edge Helly graph, then one can compute a central vertex and
the radius of $G$ in ${\mathcal{O}}(\delta m)$ time, where $\delta$ is the
hyperbolicity of $G$.

###### Proof

We use Lemma 4 in order to find, in ${\mathcal{O}}(\delta m)$ time, a vertex
$c$ of $G$ with eccentricity $e(c)\leq rad(G)+2\delta$. Then we apply Lemma 3
at most $2\delta$ times in order to descend from $c$ to a central vertex
$c^{*}$. It takes ${\mathcal{O}}(\delta m)$ time. ∎

Combining this with Corollary 2, we get.

###### Corollary 4

For any $n$-vertex $m$-edge Helly graph $G$, a central vertex and the radius
of $G$ can be computed in ${\mathcal{O}}(m\sqrt{n})$ time.

We are now ready to prove our main result of this section.

###### Theorem 3.1

All vertex eccentricities in an $n$-vertex $m$-edge Helly graph $G$ can be
computed in total ${\mathcal{O}}(m\sqrt{n})$ time.

###### Proof

Our goal is to compute $e(v)$ for every $v\in V$. For that, we first find a
central vertex $c$ and compute the radius $rad(G)$ of $G$, which takes
${\mathcal{O}}(m\sqrt{n})$ time by Corollary 4. If $rad(G)\leq 5\sqrt{n}+6$
(the choice of this number will be clear later), then $diam(G)\leq 2rad(G)\leq
10\sqrt{n}+12$ and we are done by Lemma 2 (applied for $k=10\sqrt{n}+12$); it
takes in this case total time ${\mathcal{O}}(m\sqrt{n})$ to compute all
eccentricities in $G$. Thus, from now on, we assume $rad(G)>5\sqrt{n}+6$. By
Theorem 2.1(3), for every $v\in V$, $e(v)=d(v,C(G))+rad(G)$ holds. Thus, in
order to compute all the eccentricities, it is sufficient to compute $C(G)$.
For a central vertex $c\in C(G)$ found earlier, let
$S=N^{2\sqrt{n}+3}_{G}[c]$. Note that, by Corollary 3, $C(G)\subseteq S$.

In what follows, let $r=rad(G)$. Consider the BFS layers $L_{i}(S)=\\{v\in
V:d(v,S)=i\\}$. Note that if $i\leq r-4\sqrt{n}-6\leq r-diam_{S}(G)$, then all
the vertices of $L_{i}(S)$ are at distance at most $r$ from all the vertices
in $S$. As a result, in order to compute $C(G)\cap S$ ($=C(G)$), it is
sufficient to consider the layers $L_{i}(S)$, for $i>r-4\sqrt{n}-6$.

Set $A=\bigcup\limits_{i>r-4\sqrt{n}-6}L_{i}(S)$. Since for every $v\notin S$,
$d(v,c)=d(v,S)+2\sqrt{n}+3\leq r$, we deduce that there are at most
$(r-2\sqrt{n}-3)-(r-4\sqrt{n}-6)=2\sqrt{n}+3$ nonempty layers in $A$.

We will need to consider the “critical band” of all the layers $L_{i}(S)$, for
$1\leq i\leq r-4\sqrt{n}-6$ (all the layers between $S$ and $A$). We claim
that there are at least $\sqrt{n}$ layers in this band. Indeed, under the
above assumption, $r>5\sqrt{n}+6$. Then, the number of layers is exactly
$e(c)-2\sqrt{n}-3>3\sqrt{n}+3$, minus at most $2\sqrt{n}+3$ layers most
distant from $c$ (layers in $A$). Overall, there are at least $\sqrt{n}$
layers in the critical band, as claimed.

Then, one layer in the critical band, call it $L$, contains at most
$n/\sqrt{n}=\sqrt{n}$ vertices.

###### Claim 7

For every $a\in A$, there exists a “distant gate” $a^{*}\in Pr(a,L)$ with the
following property: $N^{r}[a]\cap S=N^{r-d(a,L)}[a^{*}]\cap S$.

In order to prove the claim, set $p=d(a,L)\ \text{and}\ q=d(a,c)\leq r$. Let
us consider a family of balls $\mathcal{F}=\\{N^{p}[a],\
N^{q-p}[c]\\}\cup\\{N^{r-p}[s]\ :\ s\in N^{r}[a]\cap(S\setminus c)\\}$. We
stress that $N^{p}[a]\cap N^{q-p}[c]=Pr(a,L)$. Then, in order to prove the
existence of a distant gate, it suffices to prove that the balls in
$\mathcal{F}$ intersect; indeed, if it is the case then we may choose for
$a^{*}$ any vertex in the common intersection of the balls in $\mathcal{F}$.
Clearly, $N^{p}[a]\cap N^{q-p}[c]\neq\emptyset$ and, in the same way,
$N^{p}[a]\cap N^{r-p}[s]\neq\emptyset$ for each $s\in N^{r}[a]\cap(S\setminus
c)$. Furthermore, since $L$ is in the critical band, $d(c,L)>2\sqrt{n}+3$, and
therefore we have for each $s,s^{\prime}\in S$:

$2(r-p)\geq 2(q-p)=2d(c,L)>diam_{S}(G)\geq d(s,s^{\prime}).$

In the same way $(q-p)+(r-p)\geq 2(q-p)>diam_{S}(G)\geq d(s,c)$. The latter
proves that the balls in $\mathcal{F}$ intersect. This concludes the proof of
Claim 7.

We finally explain how to compute these distant gates, and how to use this
information in order to compute $S\cap C(G)$. Specifically:

  * •

We make a BFS from every $u\in L$. it takes
${\mathcal{O}}(m|L|)={\mathcal{O}}(m\sqrt{n})$ time. Doing so, we can compute
$\forall a\in A,\ Pr(a,L)$, in total
${\mathcal{O}}(|A||L|)={\mathcal{O}}(n\sqrt{n})$ time.

  * •

Since $A$ contains at most ${\mathcal{O}}(\sqrt{n})$ nonempty layers, then the
number of pairwise distinct distances $d(a,L)$, for $a\in A$, is also in
${\mathcal{O}}(\sqrt{n})$. Call the set of all these distances $I_{A}$. Then,
$\forall u\in L$, and $\forall i\in I_{A}$, we also compute
$p(u,i)=|N_{G}^{r-i}[u]\cap S|$. For that, we consider the vertices $u\in L$
sequentially. Recall that we computed a BFS tree rooted at $u$. In particular,
we can order the vertices of $S$ by increasing distance to $u$. It takes
${\mathcal{O}}(n)$ time. Similarly, we can order $I_{A}$ in
${\mathcal{O}}(\sqrt{n}\log{n})=o(n)$ time. In order to compute all the values
$p(u,i)$, it suffices to scan in parallel these two ordered lists. The running
time is $\mathcal{O}(n)$ for every fixed $u\in L$, and so the total running
time is $\mathcal{O}(n|L|)=\mathcal{O}(n\sqrt{n})$.

  * •

Now, in order to compute a distant gate $a^{*}$, for $a\in A$, we proceed as
follows. Let $i=d(a,L)$. We scan $Pr(a,L)$ and we store a vertex $a^{*}$
maximizing $p(a^{*},i)$. It takes
${\mathcal{O}}(|A||L|)={\mathcal{O}}(n\sqrt{n})$ time. On the way, $\forall
u\in L$, let $q(u)$ be the maximum $i$ such that $a^{*}\equiv u$ is the
distant gate of some vertex $a\in A$, such that $d(a,L)=i$ (possibly, $q(u)=0$
if $u$ was not chosen as the distant gate of any vertex).

  * •

Let $s\in S$ be arbitrary. For having $s\in S\cap C(G)$, it is necessary and
sufficient to have $s\in N^{r}[a]\cap S,\forall a\in A$. Equivalently,
$\forall u\in L$, one must have $d(s,u)\leq r-q(u)$. This can be checked in
time ${\mathcal{O}}(|L|)$ per vertex in $S$, and so, in total
${\mathcal{O}}(n\sqrt{n})$ time.

∎

##  4 Eccentricities in Helly graphs with small hyperbolicity

In the previous section we showed that a central vertex of a Helly graph $G$
can be computed in ${\mathcal{O}}(\delta m)$ time, where $\delta$ is the
hyperbolicity of $G$. This nice result, combined with the property that all
Helly graphs have hyperbolicity ${\mathcal{O}}(\sqrt{n})$ (Corollary 2), was
key to the design of our ${\mathcal{O}}(m\sqrt{n})$-time algorithm for
computing all vertex eccentricities. Next, we deepen the connection between
hyperbolicity and fast eccentricity computation within Helly graphs.

As we have mentioned earlier, many graph classes (e.g., interval graphs,
chordal graphs, dually chordal graphs, AT-free graphs, weakly chordal graphs
and many others) have constant hyperbolicity. In particular, the dually
chordal graphs and the $C_{4}$-free Helly graphs (superclasses to the interval
graphs and to the strongly chordal graphs) are proper subclasses of the
$1$-hyperbolic Helly graphs. This raises the question whether all vertex
eccentricities can be computed in linear time in a Helly graph $G$ if its
hyperbolicity $\delta$ is a constant.

We prove in what follows that it is indeed the case, which is the main result
of this section. The following result could also be considered as a
parameterized algorithm on Helly graphs with $\delta$ as the parameter.

###### Theorem 4.1

If $G$ is an $m$-edge Helly graph of hyperbolicity $\delta$, then the
eccentricity of all vertices of $G$ can be computed in
${\mathcal{O}}(\delta^{2}m\log\delta)$ time. The algorithm does not need to
know the value of $\delta$ in order to work correctly. If $\delta$ (or a
constant approximation of it) is known, then the running time is
$\mathcal{O}(\delta^{2}m)$.

As a byproduct, we get a linear time algorithm for computing all vertex
eccentricities in $C_{4}$-free Helly graphs as well as in dually chordal
graphs, generalizing known results from [11, 31, 49]. We recall that for
dually chordal graphs, until this paper it was only known that a central
vertex of such a graph can be found in linear time [11, 31].

The remainder of this section is devoted to proving Theorem 4.1. For that, the
following result is proved in Subsection 4.1:

###### Lemma 6

Let $G$ be an $m$-edge Helly graph, $c$ be a central vertex of $G$ and $k$ be
a natural number. There is an ${\mathcal{O}}(k^{2}m)$-time algorithm which
computes $C(G)\cap N^{k}[c]$.

######  Proof (Proof of Theorem 4.1 assuming Lemma 6.)

Since, by Theorem 2.1(3), $e(v)=d(v,C(G))+rad(G)$ holds for every $v\in V$, as
before, in order to compute all the eccentricities, it is sufficient to
compute $C(G)$. We first find a central vertex $c$ and compute the radius
$rad(G)$ of $G$. This takes ${\mathcal{O}}(\delta m)$ time by Lemma 5.

By Claim 1, we know that $diam(C(G))\leq 2\delta+1$. Therefore, $C(G)\subseteq
N^{2\delta+1}[c]$.

  * •

If $\delta$ is kown to us, we will fix $k:=2\delta+1$ (if only a constant
approximation $\delta^{\prime}\geq\delta$ of $\delta$ is known, we set
$k=2\delta^{\prime}+1$). Then, we are done applying Lemma 6.

  * •

Otherwise, we work sequentially with
$k=2,3,4,5,8,9,\dots,2^{p},2^{p}+1,2^{p+1},2^{p+1}+1$,…, and we stop after
finding the smallest integer (power of 2) $k$ such that $C(G)\cap
N^{k}[c]=C(G)\cap N^{k+1}[c]$. Indeed, by the isometricity (and hence
connectedness) of $C(G)$ in $G$ (see Lemma 1), the set $C(G)\cap N^{k}[c]$
will contain all central vertices of $G$, i.e., $C(G)\cap N^{k}[c]=C(G)$. The
latter will happen for some $k<2(2\delta+1)$ after at most
${\mathcal{O}}(\log\delta)$ probes.

Overall, since we need to apply Lemma 6 at most ${\mathcal{O}}(\log\delta)$
times, for some values $k<2(2\delta+1)$, the total running time is
${\mathcal{O}}(\delta^{2}m\log\delta)$. If $\delta$ (or a constant
approximation of it is known), then we call Lemma 6 only once, and therefore
the running time goes down to ${\mathcal{O}}(\delta^{2}m)$. ∎

###  4.1 Proof of Lemma 6

In what follows, $G$ is a Helly graph, $k$ is an integer and $r=rad(G)$. Let
$S_{k}=N^{k}[c]$. If $r\leq 2k$, we can compute all central vertices in
${\mathcal{O}}(km)$ time (see Lemma 2). Thus from now on, $r>2k$. As
$diam_{S_{k}}(G)\leq 2k$, to find all central vertices in $S_{k}$ (i.e., the
set $C(G)\cap S_{k}$), we will need to consider only the vertices at distance
$>r-2k$ from $S_{k}$.

Let $i<2k$ be fixed (we need to consider all possible $i$ between $k$ and
$2k-1$ sequentially). Let $A_{k,i}=L_{r-i}(S_{k})$ (where we recall that
$L_{r-i}(S_{k})=\\{v\in V:d(v,S_{k})=r-i\\}$). We want to compute

$S_{k,i}:=\\{s\in S_{k}:A_{k,i}\subseteq N^{r}[s]\\}.$

Indeed, $C(G)\cap S_{k}=\bigcap_{i=k}^{2k-1}S_{k,i}$.

The computation of $S_{k,i}$ (for $k,i$ fixed) works by phases. We describe
below the two main phases of the process.

First phase of the algorithm. To give the intuition of our approach, we will
need the following simple claim. For a vertex $v\in V$ and an integer $j$, let
$L(v,j,S_{k}):=\\{u\in V:d(v,S_{k})=d(v,u)+d(u,S_{k})\mbox{ and }d(v,u)=j\\}$.

###### Claim 8

Let $B\subseteq A_{k,i}$ be such that $\bigcap\\{L(b,j,S_{k}):b\in
B\\}\neq\emptyset$, for some $0\leq j<r-i$. Then, for every $s\in S_{k}$,
$\max_{b\in B}d(s,b)\leq r$ if and only if $d(s,\bigcap\\{L(b,j,S_{k}):b\in
B\\})\leq r-j$.

###### Proof

If $d(s,\bigcap\\{L(b,j,S_{k}):b\in B\\})\leq r-j$, then clearly $\max_{b\in
B}d(s,b)\leq r$. Conversely, let us assume $\max_{b\in B}d(s,b)\leq r$. Set
${\mathcal{F}}=\\{N_{G}^{r-j}[s],N_{G}^{r+k-(i+j)}[c]\\}\cup\\{N_{G}^{j}[b]\
:\ b\in B\\}$. We prove that the balls in ${\mathcal{F}}$ intersect.

  * •

For each $b,b^{\prime}\in B$, $N^{j}_{G}[b]\cap
N^{j}_{G}[b^{\prime}]\supseteq\bigcap\\{L(b,j,S_{k}):b\in B\\}\neq\emptyset$.

  * •

Since we assume $\max_{b\in B}d(s,b)\leq r$, $N_{G}^{j}[b]\cap
N_{G}^{r-j}[s]\neq\emptyset$.

  * •

Furthermore, as for each $b\in B$ we have $d(b,c)=d(b,S_{k})+k=r-i+k$, we
obtain $N_{G}^{r-i+k-j}[c]\cap N_{G}^{j}[b]=L(b,j,S_{k})\neq\emptyset$.

  * •

Finally, since we have $j<r-i$, $(r-i+k-j)+(r-j)>k+i\geq k\geq d(s,c)$.
Therefore, $N_{G}^{r+k-(i+j)}[c]\cap N_{G}^{r-j}[s]\neq\emptyset$.

It follows from the above that the balls in ${\mathcal{F}}$ pairwise
intersect. By the Helly property, there exists a vertex $y$ in the common
intersection of all the balls in ${\mathcal{F}}$. As for each $b\in B$, $y\in
N_{G}^{r-i+k-j}[c]\cap N_{G}^{j}[b]=L(b,j,S_{k})$, we deduce that
$y\in\bigcap\\{L(b,j,S_{k}):b\in B\\}$. Finally, we have
$d(s,\bigcap\\{L(b,j,S_{k}):b\in B\\})\leq d(s,y)\leq r-j$. ∎

We are now ready to present the first phase of our algorithm (for $k,i$
fixed). It is divided into $r-i$ steps: from $j=0$ to $j=r-i-1$. At step $j$,
for $0\leq j<r-i$, the intermediate output is a collection of disjoint subsets
$V_{j}^{1},V_{j}^{2},...,V_{j}^{p_{j}}$ of the layer $L_{r-i-j}(S_{k})$. These
disjoint subsets are in one-to-one correspondence with some partition
$B_{1},B_{2},...,B_{p_{j}}$ of $A_{k,i}$. Specifically, the algorithm ensures
that:

$\forall 1\leq t\leq p_{j},\ V_{j}^{t}=\bigcap\\{L(b,j,S_{k}):b\in
B_{t}\\}\neq\emptyset.$

Doing so, by the above Claim 8, for any $s\in S_{k}$ we have

$\max_{z\in A_{k,i}}d(s,z)\leq r\iff\max_{1\leq t\leq p_{j}}d(s,V_{j}^{t})\leq
r-j.$

Initially, for $j=0$, every set $B_{t}$ is a singleton. Furthermore,
$B_{t}=V_{0}^{t}$. Then, we show how to partition $L_{r-i-(j+1)}(S_{k})$ from
$V_{j}^{1},V_{j}^{2},...,V_{j}^{p_{j}}$ in total $\mathcal{O}(\sum_{x\in
L_{r-i-j}(S_{k})}|N_{G}(x)|)$ time. Note that in doing so we get a total
running time in $\mathcal{O}(m)$ for that phase.

For that, let us define $W_{j}^{t}=N(V_{j}^{t})\cap L_{r-i-(j+1)}(S_{r})$.
Since the subsets $V_{j}^{t}$ are pairwise disjoint, the construction of the
$W_{j}^{t}$’s takes total $\mathcal{O}(\sum_{x\in
L_{r-i-j}(S_{k})}|N_{G}(x)|)$ time. Furthermore:

###### Claim 9

$W_{j}^{t}=\bigcap\\{L(b,j+1,S_{k}):b\in B_{t}\\}$.

###### Proof

We only need to prove that we have $\bigcap\\{L(b,j+1,S_{k}):b\in
B_{t}\\}\subseteq W_{j}^{t}$ (the other inclusion being trivial by
construction). For that, let $x\in\bigcap\\{L(b,j+1,S_{k}):b\in B_{t}\\}$ be
arbitrary. Recall that we have, for each $b\in B_{t}$,
$d(b,c)=k+d(b,S_{k})=r-i+k$. In particular, $x\in L(b,j+1,S_{k})=L(b,j+1,c)$.
It implies that the balls in $\\{N_{G}[x]$,
$N_{G}^{r-i+k-j}[c]\\}\cup\\{N_{G}^{j}[b]\ :\ b\in B_{t}\\}$ pairwise
intersect. By the Helly property, $x$ has a neighbour in
$N_{G}^{r-i+k-j}[c]\cap\left(\bigcap\\{N^{j}[b]\ :\ b\in
B_{t}\\}\right)=\bigcap\\{L(b,j,S_{k}):b\in B_{t}\\}=V_{j}^{t}$. Since $x\in
L_{r-i-(j+1)}(S_{k})$, we obtain as desired $x\in W_{j}^{t}$. ∎

Finally, in order to compute the new sets $V_{j+1}^{t^{\prime}}$, we proceed
as follows. Let $\mathcal{W}=\\{W_{j}^{t}:1\leq t\leq p_{j}\\}$. While
$\mathcal{W}\neq\emptyset$, we select some vertex $x\in L_{r-i-(j+1)}(S_{k})$
maximizing $\\#\\{t:x\in W_{j}^{t}\\}$. Then, we create a new set
$\bigcap_{t:x\in W_{j}^{t}}W_{j}^{t}$, and we remove $\\{W_{j}^{t}:x\in
W_{j}^{t}\\}$ from $\mathcal{W}$. Note that, by the above Claim 9,
$\bigcap_{t:x\in W_{j}^{t}}W_{j}^{t}=\bigcap_{t:x\in
W_{j}^{t}}\bigcap\\{L(b,j+1,S_{k}):b\in
B_{t}\\}=\bigcap\\{L(b,j+1,S_{k}):b\in\bigcup_{t:x\in W_{j}^{t}}B_{t}\\}$.
Furthermore, by maximality of vertex $x$, $\bigcap_{t:x\in
W_{j}^{t}}W_{j}^{t}$ is disjoint from the subsets in $\\{W_{j}^{t}:x\notin
W_{j}^{t}\\}$. The latter ensures that all the new sets we create are pairwise
disjoint.

In order to implement this above process efficiently, we store each $x\in
L_{r-i-(j+1)}(S_{k})$ in a list indexed by $\\#\\{t:x\in W_{j}^{t}\\}$. Then,
we traverse these lists by decreasing index. We keep, for each $x\in
L_{r-i-(j+1)}(S_{k})$, a pointer to its current position in order to
dynamically change its list throughout the process. See also the proof of
Lemma 2 in [49]. The running time is proportional to $\sum\\{|W_{j}^{t}|:1\leq
t\leq p_{j}\\}=\mathcal{O}(\sum_{x\in L_{r-i-j}(S_{k})}|N_{G}(x)|)$.

Second phase of the algorithm. Let $C_{1},C_{2},...,C_{p}$ denote the sets
$V_{r-i-1}^{1},...,V_{r-i-1}^{p_{r-i-1}}$ (i.e., those obtained at the end of
the first phase of our algorithm). Note that $C_{1},C_{2},...,C_{p}$ are
subsets of $L_{1}(S_{k})$ ($=N_{G}(S_{k})$). At this point, it is not possible
anymore to follow the shortest-paths between $A_{k,i}$ and $S_{k}$.

Then, let $X=A_{k,i}\cup\\{c\\}$. Set $\alpha(c)=k+i+2$ and $\alpha(a)=r$ for
each $a\in A_{k,i}$. We define the set $Y=\\{y:\forall x\in
X,d(y,x)\leq\alpha(x)\\}$. Observe that $S_{k,i}=Y\cap S_{k}$ (recall that
$S_{k,i}$ was defined as $\\{s\in S_{k}:A_{k,i}\subseteq N^{r}[s]\\}$).
Therefore, in order to compute $S_{k,i}$, it suffices to compute $Y$.

For that, we proceed in $i+2$ steps. At step $\ell$, for $0\leq\ell\leq i+1$,
we maintain a family of nonempty pairwise disjoint sets
$Z_{\ell}^{1},Z_{\ell}^{2},...,Z_{\ell}^{q_{\ell}}$ and a covering
$X_{\ell}^{1},X_{\ell}^{2},\ldots,X_{\ell}^{q_{\ell}}$ of $X$ such that the
following is true for every $1\leq t\leq q_{\ell}$:

$Z_{\ell}^{t}=\bigcap_{x\in X_{\ell}^{t}}N_{G}^{\alpha(x)-(i+1)+\ell}[x].$

Doing so, after $i+2$ steps, the set $Y$ is nonempty if and only if
$q_{i+1}=1$ (the above partition is reduced to one group). Furthermore, if it
is the case, $Y=Z_{i+1}^{1}$.

Initially, for $\ell=0$, we start from $Z_{0}^{1}=C_{1},...,Z_{0}^{p}=C_{p}$,
and then the corresponding covering is $\forall 1\leq t\leq p$,
$X_{1}^{t}=B_{t}\cup\\{c\\}$ (with $B_{1},B_{2},...,B_{p}$ being the partition
of $A_{k,i}$ after the first phase of our algorithm). – Note that this is only
a covering, and not a partition, because the vertex $c$ is contained in all
the groups. – For going from $\ell$ to $\ell+1$, we proceed as we did during
the first phase. Specifically, for every $t$, let
$U_{\ell}^{t}=N_{G}[Z_{\ell}^{t}]$. Since the sets $Z_{\ell}^{t}$ are pairwise
disjoint, the computation of all the intermediate sets $U_{\ell}^{t}$ takes
total ${\mathcal{O}}(m)$ time.

###### Claim 10

$U_{\ell}^{t}=\bigcap_{x\in X_{\ell}^{t}}N_{G}^{\alpha(x)-(i+1)+(\ell+1)}[x]$.

The proof is similar to that of Claim 9.

Finally, in order to compute the new sets $Z_{\ell+1}^{t^{\prime}}$, let
$\mathcal{U}=\\{U_{\ell}^{t}:1\leq t\leq q_{\ell}\\}$. While
$\mathcal{U}\neq\emptyset$, we select some vertex $u\in V$ maximizing
$\\#\\{t:u\in U_{\ell}^{t}\\}$. Then, we create a new set $\bigcap_{t:u\in
U_{\ell}^{t}}U_{\ell}^{t}$, and we remove $\\{U_{\ell}^{t}:u\in
U_{\ell}^{t}\\}$ from $\mathcal{U}$. The running time is proportional to
$\sum\\{|U_{\ell}^{t}|:1\leq t\leq q_{\ell}\\}=\mathcal{O}(m)$.

Complexity analysis. Overall, the first phase runs in ${\mathcal{O}}(m)$ time,
and the second phase runs in ${\mathcal{O}}(im)={\mathcal{O}}(km)$ time. Since
it applies for $k,i$ fixed, the total running time of the algorithm of Lemma 6
(for $k$ fixed) is in $\mathcal{O}(k^{2}m)$.

This completes the proof of Lemma 6.

## 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, pages 377–391. SIAM, 2016.
  * [2] M. Abu-Ata and F. F. Dragan.  Metric tree-like structures in real-world networks: an empirical study.  Networks, 67(1):49–68, 2016.
  * [3] A. B. Adcock, B. D. Sullivan, and M. W. Mahoney.  Tree-like structure in large social and information networks.  In 2013 IEEE 13th International Conference on Data Mining, pages 1–10. IEEE, 2013.
  * [4] H.-J. Bandelt and V. Chepoi.  1-hyperbolic graphs.  SIAM J. Discret. Math., 16(2):323–334, 2003.
  * [5] H.-J. Bandelt and V. Chepoi.  Metric graph theory and geometry: a survey.  Contemporary Mathematics, 453:49–86, 2008.
  * [6] H.-J. Bandelt and E. Pesch.  Dismantling absolute retracts of reflexive graphs.  European Journal of Combinatorics, 10(3):211–220, 1989.
  * [7] H.-J. Bandelt and E. Pesch.  A Radon theorem for Helly graphs.  Archiv der Mathematik, 52(1):95–98, 1989.
  * [8] H.-J. Bandelt and E. Prisner.  Clique graphs and Helly graphs.  Journal of Combinatorial Theory, Series B, 51(1):34–45, 1991.
  * [9] M. Borassi, D. Coudert, P. Crescenzi, and A. Marino.  On computing the hyperbolicity of real-world graphs.  In Algorithms-ESA 2015, pages 215–226. Springer, 2015.
  * [10] M. Borassi, P. Crescenzi, and M. Habib.  Into the square: On the complexity of some quadratic-time solvable problems.  Electronic Notes in Theoretical Computer Science, 322:51–67, 2016\.
  * [11] A. Brandstädt, V. Chepoi, and F. F. Dragan.  The algorithmic use of hypertree structure and maximum neighbourhood orderings.  Discret. Appl. Math., 82(1-3):43–77, 1998.
  * [12] A. Brandstädt, F. F. Dragan, V. Chepoi, and V. Voloshin.  Dually chordal graphs.  SIAM Journal on Discrete Mathematics, 11(3):437–455, 1998.
  * [13] K. Bringmann, T. Husfeldt, and M. Magnusson.  Multivariate analysis of orthogonal range searching and graph distances parameterized by treewidth.  In IPEC, 2018.
  * [14] G. Brinkmann, J. Koolen, and V. Moulton.  On the hyperbolicity of chordal graphs.  Annals of Combinatorics, 5(1):61–69, 2001.
  * [15] S. Cabello.  Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs.  ACM Transactions on Algorithms, 15(2):21, 2018.
  * [16] J. Chalopin, V. Chepoi, F. F. Dragan, G. Ducoffe, A. Mohammed, and Y. Vaxès.  Fast approximation and exact computation of negative curvature parameters of graphs.  In 34th International Symposium on Computational Geometry, SoCG 2018, June 11-14, 2018, Budapest, Hungary, pages 22:1–22:15, 2018.
  * [17] J. Chalopin, V. Chepoi, A. Genevois, H. Hirai, and D. Osajda.  Helly groups, 2020.
  * [18] M. Chastand, F. Laviolette, and N. Polat.  On constructible graphs, infinite bridged graphs and weakly cop-win graphs.  Discrete Mathematics, 224(1-3):61–78, 2000.
  * [19] V. Chepoi and F. F. Dragan.  Disjoint sets problem.  1992\.
  * [20] V. Chepoi and F. F. Dragan.  A linear-time algorithm for finding a central vertex of a chordal graph.  In J. van Leeuwen, editor, Algorithms - ESA ’94, Second Annual European Symposium, Utrecht, The Netherlands, September 26-28, 1994, Proceedings, volume 855 of Lecture Notes in Computer Science, pages 159–170. Springer, 1994.
  * [21] V. Chepoi, F. F. Dragan, B. Estellon, M. Habib, and Y. Vaxès.  Diameters, centers, and approximating trees of $\delta$-hyperbolic geodesic spaces and graphs.  In M. Teillaud, editor, Proceedings of the 24th ACM Symposium on Computational Geometry, College Park, MD, USA, June 9-11, 2008, pages 59–68. ACM, 2008.
  * [22] V. Chepoi, F. F. Dragan, and Y. Vaxès.  Center and diameter problems in plane triangulations and quadrangulations.  In SODA, pages 346–355, 2002.
  * [23] V. Chepoi, F. 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(2):393–433, 2019\.
  * [24] D. Corneil, F. F. Dragan, M. Habib, and C. Paul.  Diameter determination on restricted graph families.  Discrete Applied Mathematics, 113(2-3):143–166, 2001.
  * [25] D. Coudert and G. Ducoffe.  Recognition of c${}_{\mbox{4}}$-free and 1/2-hyperbolic graphs.  SIAM J. Discret. Math., 28(3):1601–1617, 2014.
  * [26] D. Coudert, G. Ducoffe, and A. Popa.  Fully polynomial FPT algorithms for some classes of bounded clique-width graphs.  ACM Transactions on Algorithms, 15(3), 2019.
  * [27] M. Dourado, F. Protti, and J. Szwarcfiter.  Complexity aspects of the Helly property: Graphs and hypergraphs.  The Electronic Journal of Combinatorics, 1000:17–12, 2009.
  * [28] F. F. Dragan.  Centers of Graphs and the Helly Property (in Russian).  PhD thesis, Moldava State University, Chişinău, 1989.
  * [29] F. F. Dragan.  Conditions for coincidence of local and global minima for eccentricity function on graphs and the Helly property (in Russian).  Studies in Applied Mathematics and Information Science, pages 49–56, 1990.
  * [30] F. F. Dragan.  Domination in quadrangle-free Helly graphs.  Cybernetics and Systems Analysis, 29(6):822–829, 1993.
  * [31] F. F. Dragan.  HT-graphs: centers, connected r-domination and Steiner trees.  Comput. Sci. J. of Moldova (Kishinev), 1(2):64–83, 1993.
  * [32] F. F. Dragan.  Dominating cliques in distance-hereditary graphs.  In E. M. Schmidt and S. Skyum, editors, Algorithm Theory - SWAT ’94, 4th Scandinavian Workshop on Algorithm Theory, Aarhus, Denmark, July 6-8, 1994, Proceedings, volume 824 of Lecture Notes in Computer Science, pages 370–381. Springer, 1994.
  * [33] F. F. Dragan and A. Brandstädt.  r-dominating cliques in graphs with hypertree structure.  Discrete Mathematics, 162(1-3):93–108, 1996.
  * [34] F. F. Dragan and H. M. Guarnera.  Obstructions to a small hyperbolicity in Helly graphs.  Discrete Mathematics, 342(2):326 – 338, 2019.
  * [35] F. F. Dragan and H. M. Guarnera.  Eccentricity function in distance-hereditary graphs.  Theor. Comput. Sci., 833:26–40, 2020.
  * [36] F. F. Dragan and H. M. Guarnera.  Eccentricity terrain of _$\delta$_ -hyperbolic graphs.  J. Comput. Syst. Sci., 112:50–65, 2020.
  * [37] F. F. Dragan, M. Habib, and L. Viennot.  Revisiting radius, diameter, and all eccentricity computation in graphs through certificates.  CoRR, abs/1803.04660, 2018.
  * [38] F. F. Dragan and A. Mohammed.  Slimness of graphs.  Discret. Math. Theor. Comput. Sci., 21(3), 2019.
  * [39] F. F. Dragan and F. Nicolai.  LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem.  Discret. Appl. Math., 98(3):191–207, 2000.
  * [40] F. F. Dragan, F. Nicolai, and A. Brandstädt.  LexBFS-orderings and power of graphs.  In F. d’Amore, P. G. Franciosa, and A. Marchetti-Spaccamela, editors, Graph-Theoretic Concepts in Computer Science, 22nd International Workshop, WG ’96, Cadenabbia (Como), Italy, June 12-14, 1996, Proceedings, volume 1197 of Lecture Notes in Computer Science, pages 166–180. Springer, 1996.
  * [41] F. F. Dragan, K. Prisakaru, and V. Chepoi.  The location problem on graphs and the Helly problem.  Diskretnaya Matematika, 4(4):67–73, 1992.
  * [42] A. Dress.  Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces.  Advances in Mathematics, 53(3):321–402, 1984.
  * [43] G. Ducoffe.  A New Application of Orthogonal Range Searching for Computing Giant Graph Diameters.  In SOSA, 2019.
  * [44] G. Ducoffe.  Around the diameter of AT-free graphs.  CoRR, abs/2010.15814, 2020.
  * [45] G. Ducoffe.  Distance problems within Helly graphs and k-Helly graphs.  CoRR, abs/2011.00001, 2020.
  * [46] G. Ducoffe.  Isometric embeddings in trees and their use in the diameter problem.  CoRR, abs/2010.15803, 2020.
  * [47] G. Ducoffe.  Optimal diameter computation within bounded clique-width graphs.  CoRR, abs/2011.08448, 2020.
  * [48] G. Ducoffe.  Beyond Helly graphs: the diameter problem on absolute retracts.  CoRR, abs/2101.03574, 2021.
  * [49] G. Ducoffe and F. F. Dragan.  A story of diameter, radius, and (almost) Helly property.  Networks, to appear.
  * [50] G. Ducoffe, M. Habib, and L. Viennot.  Fast diameter computation within split graphs.  In COCOA, pages 155–167. Springer, 2019.
  * [51] G. Ducoffe, M. Habib, and L. Viennot.  Diameter computation on $H$-minor free graphs and graphs of bounded (distance) VC-dimension.  In SODA, pages 1905–1922. SIAM, 2020.
  * [52] D. Eppstein.  Diameter and treewidth in minor-closed graph families.  Algorithmica, 27(3-4):275–291, 2000.
  * [53] A. Farley and A. Proskurowski.  Computation of the center and diameter of outerplanar graphs.  Discrete Applied Mathematics, 2(3):185–191, 1980.
  * [54] H. Fournier, A. Ismail, and A. Vigneron.  Computing the Gromov hyperbolicity of a discrete metric space.  Inf. Process. Lett., 115(6-8):576–579, 2015.
  * [55] P. Gawrychowski, H. Kaplan, S. Mozes, M. Sharir, and O. Weimann.  Voronoi diagrams on planar graphs, and computing the diameter in deterministic $\tilde{O}(n^{5/3})$ time.  In SODA, pages 495–514. SIAM, 2018.
  * [56] M. Gromov.  Hyperbolic Groups, pages 75–263.  Springer, New York, NY, 1987.
  * [57] J. Isbell.  Six theorems about injective metric spaces.  Commentarii Mathematici Helvetici, 39(1):65–76, 1964.
  * [58] W. S. Kennedy, I. Saniee, and O. Narayan.  On the hyperbolicity of large-scale networks and its estimation.  In 2016 IEEE International Conference on Big Data (Big Data), pages 3344–3351. IEEE, 2016.
  * [59] J. H. Koolen and V. Moulton.  Hyperbolic bridged graphs.  Eur. J. Comb., 23(6):683–699, 2002.
  * [60] D. Koschützki, K. A. Lehmann, L. Peeters, S. Richter, D. Tenfelde-Podehl, and O. Zlotowski.  Centrality indices.  In Network Analysis, pages 16–61. Springer, 2005.
  * [61] M. Lin and J. Szwarcfiter.  Faster recognition of clique-Helly and hereditary clique-Helly graphs.  Information Processing Letters, 103(1):40–43, 2007.
  * [62] O. Narayan and I. Saniee.  Large-scale curvature of networks.  Physical Review E, 84(6):066108, 2011.
  * [63] S. Olariu.  A simple linear-time algorithm for computing the center of an interval graph.  International Journal of Computer Mathematics, 34(3-4):121–128, 1990.
  * [64] N. Polat.  Convexity and fixed-point properties in Helly graphs.  Discrete Mathematics, 229(1-3):197–211, 2001.
  * [65] N. Polat.  On constructible graphs, locally Helly graphs, and convexity.  Journal of Graph Theory, 43(4):280–298, 2003.
  * [66] L. Roditty and V. Vassilevska Williams.  Fast approximation algorithms for the diameter and radius of sparse graphs.  In STOC, pages 515–524. ACM, 2013.
  * [67] Y. Shavitt and T. Tankel.  Hyperbolic embedding of internet graph for distance estimation and overlay construction.  IEEE/ACM Transactions on Networking, 16(1):25–36, 2008.
  * [68] J. L. Szwarcfiter and C. F. Bornstein.  Clique graphs of chordal and path graphs.  SIAM J. Discret. Math., 7(2):331–336, 1994.
  * [69] R. Williams.  A new algorithm for optimal 2-constraint satisfaction and its implications.  Theoretical Computer Science, 348(2-3):357–365, 2005.
  * [70] Y. Wu and C. Zhang.  Hyperbolicity and chordality of a graph.  Electr. J. Comb., 18(1):Paper #P43, 2011.