# Beyond Helly graphs: the diameter problem on absolute retracts

Guillaume Ducoffe  National Institute for Research and Development in
Informatics, Romania University of Bucharest, Romania

###### Abstract

Characterizing the graph classes such that, on $n$-vertex $m$-edge graphs in
the class, we can compute the diameter faster than in ${\cal O}(nm)$ time is
an important research problem both in theory and in practice. We here make a
new step in this direction, for some metrically defined graph classes.
Specifically, a subgraph $H$ of a graph $G$ is called a retract of $G$ if it
is the image of some idempotent endomorphism of $G$. Two necessary conditions
for $H$ being a retract of $G$ is to have $H$ is an isometric and isochromatic
subgraph of $G$. We say that $H$ is an absolute retract of some graph class
${\cal C}$ if it is a retract of any $G\in{\cal C}$ of which it is an
isochromatic and isometric subgraph. In this paper, we study the complexity of
computing the diameter within the absolute retracts of various hereditary
graph classes. First, we show how to compute the diameter within absolute
retracts of bipartite graphs in randomized $\tilde{\cal O}(m\sqrt{n})$ time.
For the special case of chordal bipartite graphs, it can be improved to linear
time, and the algorithm even computes all the eccentricities. Then, we
generalize these results to the absolute retracts of $k$-chromatic graphs, for
every fixed $k\geq 3$. Finally, we study the diameter problem within the
absolute retracts of planar graphs and split graphs, respectively.

##  1 Introduction

One of the most basic graph properties is the diameter of a graph (maximum
number of edges on a shortest path). It is a rough estimate of the maximum
delay in order to send a message in a communication network [34], but it also
got used in the literature for various other purposes [2, 82]. The complexity
of computing the diameter has received tremendous attention in the Graph
Theory community [1, 16, 20, 22, 29, 28, 26, 31, 32, 33, 38, 48, 49, 50, 45,
53, 56, 73]. Indeed, while this can be done in ${\cal O}(nm)$ time for any
$n$-vertex $m$-edge graph, via a simple reduction to breadth-first search,
breaking this quadratic barrier (in the size $n+m$ of the input) happens to be
a challenging task. In fact, under plausible complexity assumptions such as
the Strong Exponential-Time Hypothesis (SETH), the optimal running time for
computing the diameter is essentially in ${\cal O}(nm)$ — up to sub-polynomial
factors [79]. This negative result holds even if we restrict ourselves to
bipartite graphs or split graphs [1, 15]. However, on the positive side,
several recent works have characterized important graph classes for which we
can achieve for the diameter problem ${\cal O}(m^{2-\epsilon})$ time, or even
better ${\cal O}(mn^{1-\epsilon})$ time, for some $\epsilon>0$. Next, we focus
on a few such classes that are most relevant to our work. Specifically, we
call $G=(V,E)$ a Helly graph if every family of pairwise intersecting balls of
$G$ (of arbitrary radius and center) have a nonempty common intersection. The
Helly graphs are a broad generalization of many better-known graph classes,
such as: trees, interval graphs, strongly chordal graphs and dually chordal
graphs [5]. Furthermore, a celebrated theorem in Metric Graph Theory is that
every graph is an isometric (distance-preserving) subgraph of some Helly graph
[44, 64]. Other properties of Helly graphs were also thoroughly investigated
in prior works [8, 9, 11, 25, 36, 37, 39, 41, 69, 77, 78]. In particular, as
far as we are concerned here, there is a randomized $\tilde{\cal
O}(m\sqrt{n})$-time algorithm in order to compute the diameter within
$n$-vertex $m$-edge Helly graphs with high probability [48].

Larger classes, related to the Helly graphs, have been considered recently.
For instance, $G=(V,E)$ is a $k$-Helly graph if every family of $k$-wise
intersecting balls of $G$ have a nonempty common intersection (Helly graphs
are exactly the $2$-Helly graphs). For every fixed $k$, there is a randomized
$\tilde{\cal O}(m\sqrt{n})$-time algorithm in order to compute the radius
(minimum eccentricity of a vertex) within $k$-Helly graphs [46]. The Helly-gap
of $G=(V,E)$ is the least $\alpha$ such that, for every family of pairwise
intersecting balls of $G$, if we increase all the radii by $\alpha$ then this
family has a nonempty common intersection [23, 42]. It also follows from [48]
that the radius and the diameter of a graph with bounded Helly-gap can be
approximated up to some additive constant, that only depends on its Helly-gap.
The latter result generalizes prior work on diameter and center approximations
within hyperbolic graph classes [28]. Finally, the graphs of bounded “distance
VC-dimension” were introduced in [30], where it was observed that, by a result
from [72], they satisfy certain “fractional” Helly property. Many interesting
graph classes have bounded distance VC-dimension, such as: proper minor-closed
graph classes [30], interval graphs [50] and bounded clique-width graphs [17].
For all the aforementioned sub-classes, there exist algorithms in ${\cal
O}(mn^{1-\epsilon})$ time, for some $\epsilon>0$, in order to compute all the
eccentricities, and so, the diameter [47, 50, 73]. Partial results also have
been obtained for the diameter problem on all graph classes of bounded
distance VC-dimension [50, 48].

Recall that an endomorphism of a graph $G$ is an edge-preserving mapping of
$G$ to itself. A retraction is an idempotent endomorphism. If $H$ is the image
of $G$ by some retraction (in particular, $H$ is a subgraph of $G$) then, we
call $H$ a retract of $G$. The notion of retract has applications in some
discrete facility location problems [62], and it is useful in characterizing
some important graph classes. For instance, the median graphs are exactly the
retracts of hypercubes [4]. We here focus on the relation between retracts and
Helly graphs, that is as follows. For some class ${\cal C}$ of reflexive
graphs (i.e., with a loop at every vertex), let us define the absolute
retracts of ${\cal C}$ as those $H$ such that, whenever $H$ is an isometric
subgraph of some $G\in{\cal C}$, $H$ is a retract of $G$. Absolute retracts
find their root in Geometry, where they got studied for various metric spaces
[67]. In the special case of the class of all reflexive graphs, the absolute
retracts are exactly the Helly (reflexive) graphs [63]. Motivated by this
characterization of Helly graphs, and the results obtained in [48] for the
diameter problem on this graph class, we here consider the following notion of
absolute retracts, for irreflexive graphs. – Unless stated otherwise, all
graphs considered in this paper are irreflexive. – Namely, let us first recall
that a subgraph $H$ of a graph $G$ is isochromatic if it has the same
chromatic number as $G$. Then, given a class of (irreflexive) graphs ${\cal
C}$, the absolute retracts of ${\cal C}$ are those $H$ such that, whenever $H$
is an isometric and isochromatic subgraph of some $G\in{\cal C}$, $H$ is a
retract of $G$. We refer the reader to [6, 7, 10, 62, 61, 66, 68, 70, 76, 74,
75], where this notion got studied for various graph classes.

#### Our results.

In this paper, we prove new structural and algorithmic properties of the
absolute retracts of various hereditary graph classes, such as: bipartite
graphs, $k$-chromatic graphs (for any $k\geq 3$), split graphs and planar
graphs. Our focus is about the diameter problem on these graph classes but, on
our way, we uncover several nice properties of the shortest-path distribution
of their absolute retracts, that may be of independent interest.

  * •

First, in Sec. 2, we consider the absolute retracts of bipartite graphs and
some important subclasses of the latter. We observe that in the square of such
graph $G$, its two partite sets induce Helly graphs. This result complements
the known relations between Helly graphs and absolute retracts of bipartite
graphs [7]. Then, we show how to compute the diameter of $G$ from the diameter
of both Helly graphs (actually, from the knowledge of the peripheral vertices
in these graphs, i.e., those vertices with maximal eccentricity). Recently
[40], we announced an ${\cal O}(m\sqrt{n})$-time algorithm in order to compute
all the eccentricities in a Helly graph. However, extending this result to the
absolute retracts of bipartite graphs appears to be a more challenging task.
We manage to do so for the subclass of chordal bipartite graphs, for which we
achieve a linear-time algorithm in order to compute all the eccentricities.
For that, we prove the stronger result that in the square of such graph, its
two partite sets induce strongly chordal graphs. Here also, our result
complements the known relations between both graph classes [18, 52].

  * •

In Sec. 3, we generalize our above framework to the absolute retracts of
$k$-chromatic graphs, for any $k\geq 3$. Our proofs in this part are more
technical and intricate than in Sec. 2. For instance, we cannot extract a
Helly graph from each colour class anymore. Instead, we define a partial
eccentricity function for each colour (i.e., by restricting ourselves to the
distances between vertices of the same colour), and we prove that the latter
functions almost have the same properties as the eccentricity function of a
Helly graph.

  * •

Our positive results in Sec. 2 and 3 rely on some Helly-type properties of the
graph classes considered. However, our hardness result in Sec. 4 hints that
the weaker property of being an absolute retract of some well-structured graph
class is not sufficient on its own for faster diameter computation.
Specifically, we prove that under SETH, there is no ${\cal
O}(mn^{1-\epsilon})$-time algorithm for the diameter problem, for any
$\epsilon>0$, on the class of absolute retracts of split graphs. This negative
result follows from an elegant characterization of this subclass of split
graphs in [66].

  * •

Finally, in Sec. 5, we briefly consider the absolute retracts of planar
graphs. While there now exist several truly subquadratic-time algorithms for
the diameter problem on all planar graphs [22, 50, 56] – with the best-known
running time being in $\tilde{\cal O}(n^{5/3})$ – the existence of a quasi
linear-time algorithm for this problem has remained so far elusive, and it is
sometimes conjectured that no such algorithm exists [22]. We give evidence
that finding such algorithm for the absolute retracts of planar graphs is
already a hard problem on its own. Specifically, we prove that every planar
graph is an isometric subgraph of some absolute retract of planar graphs. This
result mirrors the aforementioned property that every graph isometrically
embeds in a Helly graph [44, 64]. It implies the existence of some absolute
retracts of planar graphs with treewidth arbitrarily large and inner vertices
of degree three. Doing so, we rule out two general frameworks in order to
compute the diameter in quasi linear time on some subclasses of planar graphs
[29, 51].

Let us mention that all graph classes considered here are polynomial-time
recognizable. For the absolute retracts of $k$-chromatic graphs, the best-
known recognition algorithms have superquadratic running-time (even for $k=2$)
[6, 10]. Fortunately, we do not need to execute these recognition algorithms
before we can compute the diameter of these graphs. Indeed, our algorithms in
Sec. 2 and 3 are heuristics which can be applied to any graph. Sometimes,
these algorithms may fail in outputting a value, that certifies the input
graph is not an absolute retract of $k$-chromatic graphs, for some $k$.
Conversely, if the input graph is an absolute retract of $k$-chromatic graphs,
then the algorithm always succeeds in outputting a value and this value is
exactly the diameter. We consider our framework to be especially useful for
all subclasses of the absolute retracts of $k$-chromatic graphs that admit
quasi linear-time recognition algorithms. In this respect, we stress that the
absolute retract of bipartite graphs are a superclass of cube-free modular
graphs, and so, of chordal bipartite graphs, cube-free median graphs and
covering graphs of modular lattices of breadth at most two [6].

#### Notations.

We mostly follow the graph terminology from [14, 35]. All graphs considered
are finite, simple (i.e., without loops nor multiple edges), unweighted and
connected. For a graph $G=(V,E)$, let the (open) neighbourhood of a vertex $v$
be defined as $N_{G}(v)=\\{u\in V\mid uv\in E\\}$ and its closed neighbourhood
as $N_{G}[v]=N_{G}(v)\cup\\{v\\}$. Similarly, for a vertex-subset $S\subseteq
V$, let $N_{G}(S)=\bigcup_{v\in S}N_{G}(v)\setminus S$, and let
$N_{G}[S]=N_{G}(S)\cup S$. The distance between two vertices $u,v\in V$ equals
the minimum number of edges on a $uv$-path, and it is denoted $d_{G}(u,v)$. We
also let $I_{G}(u,v)$ denote the vertices “metrically” between $u$ and $v$,
i.e., $I_{G}(u,v)=\\{w\in V\mid d_{G}(u,v)=d_{G}(u,w)+d_{G}(w,v)\\}$. The ball
of center $v$ and radius $r$ is defined as $N_{G}^{r}[v]=\\{u\in V\mid
d_{G}(u,v)\leq r\\}$. Furthermore, let the eccentricity of a vertex $v$ be
defined as $e_{G}(v)=\max_{u\in V}d_{G}(u,v)$. The diameter and the radius of
a graph $G$ are defined as $diam(G)=\max_{v\in V}e_{G}(v)$ and
$rad(G)=\min_{v\in V}e_{G}(v)$, respectively. A vertex $v\in V$ is called
central if $e_{G}(v)=rad(G)$, and peripheral if $e_{G}(v)=diam(G)$. Note that
we sometimes omit the subscript if the graph $G$ is clear from the context. We
introduce additional terminology where it is needed throughout the paper.

##  2 Bipartite graphs

The study of the absolute retracts of bipartite graphs dates back from Hell
[60], and since then many characterizations of this graph class were proposed
[6]. This section is devoted to the diameter problem on this graph class. In
Sec. 2.1, we propose a randomized $\tilde{\cal O}(m\sqrt{n})$-time algorithm
for this problem. Then, we consider the chordal bipartite graphs in Sec. 2.2,
that have been proved in [6] to be a subclass of the absolute retracts of
bipartite graphs. For the chordal bipartite graphs, we present a deterministic
linear-time algorithm in order to compute all the eccentricities.

Let us introduce a few additional terminology. For a connected bipartite graph
$G$, we denote its two partite sets by $V_{0}$ and $V_{1}$. A half-ball is the
intersection of a ball with one of the two partite sets of $G$. Finally, for
$i\in\\{0,1\\}$, let $H_{i}$ be the graph with vertex-set $V_{i}$ and an edge
between every two vertices with a common neighbour in $G$.

###  2.1 Faster diameter computation

We start with the following characterization of the absolute retracts of
bipartite graphs:

######  Theorem 1 ([6]).

$G=(V,E)$ is an absolute retract of bipartite graphs if and only if the
collection of half-balls of $G$ satisfies the Helly property.

This above Theorem 1 leads us to the following simple, but important for what
follows, observation about the internal structure of the absolute retracts of
bipartite graphs:

######  Lemma 1.

If $G=(V_{0}\cup V_{1},E)$ is an absolute retract of bipartite graphs then
both $H_{0}$ and $H_{1}$ are Helly graphs.

###### Proof.

For each $i\in\\{0,1\\}$ the balls of $H_{i}$ are exactly the half-balls of
$G$ that intersect $V_{i}$ and have as their center a vertex of $V_{i}$.
Therefore, by Theorem 1, the collection of balls of $H_{i}$ satisfies the
Helly property, i.e., $H_{i}$ is a Helly graph. ∎

Next, we prove that in order to compute $diam(G)$, with $G$ an absolute
retract of bipartite graphs, it is sufficient to compute the peripheral
vertices of the Helly graphs $H_{0}$ and $H_{1}$.

######  Lemma 2.

If $G=(V_{0}\cup V_{1},E)$ is an absolute retract of bipartite graphs such
that $diam(H_{0})\leq diam(H_{1})$ then,
$diam(G)\in\\{2diam(H_{1}),2diam(H_{1})+1\\}$. Moreover, if $diam(G)\geq 3$
then we have $diam(G)=2diam(H_{1})+1$ if and only if:

  * •

$diam(H_{1})=1$;

  * •

or $diam(H_{0})=diam(H_{1})$ and, for some $i\in\\{0,1\\}$, there exists a
peripheral vertex of $H_{i}$ whose all neighbours in $G$ are peripheral
vertices of $H_{1-i}$.

###### Proof.

Let $i\in\\{0,1\\}$. Clearly, $diam(G)\geq\max_{u,v\in
V_{i}}d_{G}(u,v)=2diam(H_{i})$. Furthermore, since $G$ is connected, $V_{i}$
is a dominating set of $G$, and therefore, every vertex of $V_{i}$ has
eccentricity at most $2diam(H_{i})+1$. Overall, since we assume
$diam(H_{1})\geq diam(H_{0})$, we get as desired
$diam(G)\in\\{2diam(H_{1}),2diam(H_{1})+1\\}$. Note that this result holds for
any bipartite graph.

In what follows, we further assume $diam(G)\geq 3$. If $diam(H_{1})\leq 1$
then, $diam(G)\leq 2diam(H_{1})+1\leq 3$. Therefore, $diam(H_{1})=1$ and
$diam(G)=2diam(H_{1})+1$. From now on, $diam(H_{1})\geq 2$.

Let us first assume $diam(G)=2diam(H_{1})+1$. Observe that for each
$i\in\\{0,1\\}$, every vertex of $V_{i}$ is at a distance at most
$1+2diam(H_{1-i})$ from every vertex of $V_{1-i}$ (in order to see that, just
take any neighbour of this vertex in $V_{1-i}$). In particular, if
$diam(H_{0})<diam(H_{1})$, then every vertex of $V_{0}$ has eccentricity at
most $2diam(H_{0})+1<2diam(H_{1})$, while every vertex of $V_{1}$ has
eccentricity at most $\max\\{2diam(H_{1}),2diam(H_{0})+1\\}=2diam(H_{1})$.
Hence, in order to have $diam(G)=2diam(H_{1})+1$, we must have
$diam(H_{0})=diam(H_{1})$. Furthermore, for some fixed $i\in\\{0,1\\}$, let
$v\in V_{i}$ be a peripheral vertex of $G$. Since $2diam(H_{1})+1=e_{G}(v)\leq
2e_{H_{i}}(v)+1$, we must have $e_{H_{i}}(v)=diam(H_{i})=diam(H_{1})$. In the
same way, for any neighbour $u\in N_{G}(v)$, we have
$e_{G}(v)\leq\max\\{2diam(H_{i}),2e_{H_{1-i}}(u)+1\\}$, and therefore, we must
also have $e_{H_{1-i}}(u)=diam(H_{1-i})=diam(H_{1})$. It implies the existence
of a peripheral vertex of $H_{i}$ whose all neighbours are peripheral vertices
of $H_{1-i}$.

Conversely, let us assume that $diam(H_{0})=diam(H_{1})$ and that, for some
$i\in\\{0,1\\}$, there exists a $v\in V_{i}$ such that:
$e_{H_{i}}(v)=diam(H_{i})=diam(H_{1})$; for every $u\in N_{G}(v)$,
$e_{H_{1-i}}(u)=diam(H_{1-i})=diam(H_{1})$. Suppose by contradiction
$e_{G}(v)<2diam(H_{1})+1$. Then, since $G$ is bipartite, all the vertices of
$V_{1-i}$ are at a distance at most $2diam(H_{1})-1$ from vertex $v$.
Furthermore, for every $x,y\in V_{1-i}$, since we have
$d_{G}(x,y)=2d_{H_{1-i}}(x,y)$, we obtain that for every even $\ell\geq
d_{H_{1-i}}(x,y)$ the half-balls $N^{\ell}_{G}[x]\cap V_{1-i}$ and
$N^{\ell}_{G}[y]\cap V_{1-i}$ intersect. In particular, we may choose
$\ell=2(diam(H_{1})-1)$ because $diam(H_{1})\geq 2$ implies
$2(diam(H_{1})-1)\geq diam(H_{1})\geq d_{H_{1-i}}(x,y)$. But then, the half-
balls $N_{G}(v)$ ($=N_{G}^{1}[v]\cap V_{1-i}$) and
$N_{G}^{2(diam(H_{1})-1)}[w]\cap V_{1-i}$, for every $w\in V_{1-i}$, pairwise
intersect. By Theorem 1, there exists a $u\in N_{G}(v)$ s.t.
$e_{H_{1-i}}(u)\leq diam(H_{1})-1$. This is a contradiction because such
neighbour $u$ cannot be peripheral in $H_{1-i}$. ∎

The remaining of Sec. 2.1 is devoted to the computation of all the peripheral
vertices in both Helly graphs $H_{0}$ and $H_{1}$. While there exists a truly
subquadratic-time algorithm for computing the diameter of a Helly graph [48],
we observe that in general, we cannot compute $H_{0}$ and $H_{1}$ in truly
subquadratic time from $G$. Next, we adapt [48, Theorem 2], for the Helly
graphs, to our needs.

######  Lemma 3.

If $G=(V_{0}\cup V_{1},E)$ is an absolute retract of bipartite graphs then,
for any $k$, we can compute in ${\cal O}(km)$ time the set of vertices of
eccentricity at most $k$ in $H_{0}$ (resp., in $H_{1}$).

###### Proof.

By symmetry, we only need to prove the result for $H_{0}$. Let $U=\\{v\in
V_{0}\mid e_{H_{0}}(v)\leq k\\}$ be the set to be computed. We consider the
more general problem of computing, for any $t$, a partition ${\cal
P}_{t}=(A^{t}_{1},A^{t}_{2},\ldots,A^{t}_{p_{t}})$ of $V_{0}$, in an arbitrary
number $p_{t}$ of subsets, subject to the following constraints:

  * •

For every $1\leq i\leq p_{t}$, let $C^{t}_{i}:=\bigcap_{v\in
A^{t}_{i}}N^{t}_{G}[v]$. Let $B_{i}^{t}:=C^{t}_{i}\cap V_{0}$ if $t$ is even
and let $B_{i}^{t}:=C^{t}_{i}\cap V_{1}$ if $t$ is odd (for short,
$B_{i}^{t}=C_{i}^{t}\cap V_{t\pmod{2}}$). _We impose the sets $B_{i}^{t}$ to
be nonempty and pairwise disjoint_.

Indeed, under these two conditions above, we have $U\neq\emptyset$ if and only
if, for any partition ${\cal P}_{2k}$ as described above, $p_{2k}=1$.
Furthermore if it is the case then $U=B^{2k}_{1}$.

The algorithm. We construct the desired partition by induction over $t$. If
$t=0$ then, let $V_{0}=\\{v_{1},v_{2},\ldots,v_{p_{0}}\\}$. We just set ${\cal
P}_{0}=(\\{v_{0}\\},\\{v_{1}\\},\ldots,\\{v_{p_{0}}\\})$ (each set is a
singleton), and for every $1\leq i\leq p_{0}$ let
$B_{i}^{0}=A_{i}^{0}=\\{v_{i}\\}$. Else, we construct ${\cal P}_{t}$ from
${\cal P}_{t-1}$. Specifically, for every $1\leq i\leq p_{t-1}$, we let
$W_{i}^{t}:=N_{G}(B_{i}^{t-1})$. Then, starting from $j:=0$ and ${\cal
F}:={\cal P}_{t-1}$, we proceed as follows until we have ${\cal F}=\emptyset$.
We pick a vertex $u$ s.t. $\\#\\{i\mid A_{i}^{t-1}\in{\cal F},\ u\in
W_{i}^{t}\\}$ is maximized. Then, we set $A_{j}^{t}:=\bigcup\\{A_{i}^{t-1}\mid
A_{i}^{t-1}\in{\cal F},\ u\in W_{i}^{t}\\}$ and
$B_{j}^{t}:=\bigcap\\{W_{i}^{t}\mid A_{i}^{t-1}\in{\cal F},\ u\in
W_{i}^{t}\\}$. We add the new subset $A_{j}^{t}$ to ${\cal P}_{t}$, we remove
all the subsets $A_{i}^{t-1},u\in W_{i}^{t}$ from ${\cal F}$, then we set
$j:=j+1$.

Correctness. The base case of our above induction is trivially correct. In
order to prove correctness of our inductive step, we need the following two
intermediate claims.

######  Claim 1.

$W_{i}^{t}=V_{t\pmod{2}}\cap\left(\bigcap_{v\in
A^{t-1}_{i}}N^{t}_{G}[v]\right)$.

Proof. Recall that $B_{i}^{t-1}=V_{t-1\pmod{2}}\cap\left(\bigcap_{v\in
A^{t-1}_{i}}N^{t-1}_{G}[v]\right)$, and that $W_{i}^{t}=N_{G}(B_{i}^{t-1})$.
Therefore by construction, $W_{i}^{t}\subseteq
V_{t\pmod{2}}\cap\left(\bigcap_{v\in A^{t-1}_{i}}N^{t}_{G}[v]\right)$.
Conversely, let $w\in V_{t\pmod{2}}\cap\left(\bigcap_{v\in
A^{t-1}_{i}}N^{t}_{G}[v]\right)$ be arbitrary. Let $a\in A_{i}^{t-1}$ be
arbitrary. There are two cases. If $a\neq w$ then, by considering any $x\in
N_{G}(w)\cap I_{G}(a,w)$, we get that the half-balls $N_{G}(w)$
($=N_{G}^{1}[w]\cap V_{t-1\pmod{2}}$) and $N_{G}^{t-1}[a]\cap V_{t-1\pmod{2}}$
intersect. Otherwise, $a=w$ and then, $t$ is even. Here also the half-balls
$N_{G}(w)$ and $N_{G}^{t-1}[a]\cap V_{t-1\pmod{2}}$ ($=N_{G}^{t-1}[a]\cap
V_{1}$) intersect because we have $N_{G}(w)=N_{G}(a)\subseteq
N_{G}^{t-1}[a]\cap V_{t-1\pmod{2}}$. Overall, in all the cases, the half-balls
$N_{G}(w)$ and $N_{G}^{t-1}[a]\cap V_{t-1\pmod{2}}$, for every $a\in
A_{i}^{t-1}$, pairwise intersect. Then, by Theorem 1, vertex $w$ has a
neighbour in $B_{i}^{t-1}$. $\diamond$

It follows from this above claim that, for each subset $A_{j}^{t}$ created at
step $t$, we have $B_{j}^{t}=V_{t\pmod{2}}\cap\left(\bigcap_{v\in
A^{t}_{j}}N^{t}_{G}[v]\right)$, as desired. Observe that all the subsets
$B_{j}^{t}$ are nonempty since they at least contain the vertex $u\in
V_{t\pmod{2}}$ that is selected in order to create $A_{j}^{t}$. What now
remains to prove is that all the subsets $B_{j}^{t}$ are pairwise disjoint.
The latter easily follows from our next intermediate claim, namely:

######  Claim 2.

Let $u\in V_{t\pmod{2}}$ be a vertex maximizing $\\#\\{i\mid u\in
W_{i}^{t}\\}$. For every index $i^{\prime}$ s.t. $u\notin W_{i^{\prime}}^{t}$,
we have $W_{i^{\prime}}^{t}\cap\left(\bigcap_{u\in
W_{i}^{t}}W_{i}^{t}\right)=\emptyset$.

Proof. It directly follows from the maximality of $\\#\\{i\mid u\in
W_{i}^{t}\\}$. $\diamond$

We are done applying this above claim at each creation of a new subset
$A_{j}^{t}$.

Complexity. The base case of our induction requires ${\cal O}(n)$ time. Let us
prove that each inductive step requires ${\cal O}(m)$ time. First, since by
the hypothesis the sets $B_{i}^{t-1}$ are pairwise disjoint, we can compute
the sets $W_{i}^{t}$ in total linear time. Then, we create an array of
$p_{t-1}$ lists, numbered from $1$ to $p_{t-1}$. For each vertex $u\in
V_{t\pmod{2}}$ s.t. $\\{i\mid u\in W_{i}^{t}\\}\neq\emptyset$, we put it in
the list numbered $\\#\\{i\mid u\in W_{i}^{t}\\}$. Since it only requires to
scan the $W_{i}^{t}$’s once, it takes ${\cal O}(m+n)$ time. We scan the lists
in decreasing order (i.e., from $p_{t-1}$ downto $1$), going to the next list
each time the current one is empty. When the current list is nonempty, we pick
any vertex $u$ of this list in order to create the next subset $A_{j}^{t}$.
Note that both subsets $A_{j}^{t}$ and $B_{j}^{t}$ can be computed in ${\cal
O}(\sum\\{|A_{i}^{t-1}|+|W_{i}^{t}|\mid A_{i}^{t-1}\in{\cal F},\ u\in
W_{i}^{t}\\})$ time. Finally, we need to discard the vertices of $B_{j}^{t}$
from the list in which they are currently contained, while for every other
$w\in\left(\bigcup\\{W_{i}^{t}\mid A_{i}^{t-1}\in{\cal F},u\in
W_{i}^{t}\\}\right)\setminus B_{j}^{t}$ we need to update
$\\#\\{i^{\prime}\mid A_{i^{\prime}}^{t-1}\in{\cal F},w\in
W_{i^{\prime}}^{t}\\}$ and the corresponding list. If, for each vertex, we
store a pointer to its position in the corresponding list, we can also do the
latter in ${\cal O}(\sum\\{|W_{i}^{t}|\mid A_{i}^{t-1}\in{\cal F},\ u\in
W_{i}^{t}\\})$ time. Overall, since each set $A_{i}^{t-1}$ gets removed once
from ${\cal F}$, the total running time for the inductive step is in ${\cal
O}(m+n)$. ∎

We use this above Lemma 3 when the respective diameters of $H_{0}$ and $H_{1}$
are in ${\cal O}(\sqrt{n})$. For larger values of diameters, we use a
randomized procedure (Algorithm 1).

Algorithm 1 Diameter computation in Helly graphs.

0: A Helly graph $H$ s.t. $diam(H)>3k=\omega(\log{|V(H)|})$.

1: Set $p=c\frac{\log{|V(H)|}}{k}$, for some sufficiently large constant $c$.

2: Let $U(p)$ contain every $v\in V(H)$ independently with probability $p$.

3: for all $v\in V(H)$ do

4: if $\forall u\in U(p),\ d_{H}(u,v)>k$ then

5: Set $\bar{e}(v):=0$.

6: else

7: Set $\bar{e}(v):=\min\\{d_{H}(u,v)+e_{H}(u)\mid u\in U(p),\ d_{H}(u,v)\leq
k\\}$.

######  Lemma 4 (Theorem 3 in [48]).

With high probability, Algorithm 1 runs in $\tilde{\cal
O}(|E(H)|\cdot|V(H)|/k)$ time, we have $diam(H)=\max_{v\in V(H)}\bar{e}(v)$,
and the peripheral vertices of $H$ are exactly the vertices $v\in V(H)$ which
maximize $\bar{e}(v)$.

We are now ready to prove the main result of this section, namely:

######  Theorem 2.

If $G=(V_{0}\cup V_{1},E)$ is an absolute retract of bipartite graphs then,
with high probability, we can compute $diam(G)$ in $\tilde{\cal O}(m\sqrt{n})$
time.

###### Proof.

We may assume $diam(G)\geq 3$. Indeed, a bipartite graph has diameter at most
two if and only if it is complete bipartite. First, we compute the peripheral
vertices of $H_{0}$ and $H_{1}$. For that, we start computing a
$2$-approximation of $diam(G)$ in linear time (e.g., by computing the
eccentricity of an arbitrary vertex). Let $D$ be the resulting value. There
are two cases.

  * •

If $D<\sqrt{n}$ then, we compute the least $k$ s.t. all vertices of $H_{0}$
(resp., of $H_{1}$) have eccentricity at most $k$. For that, it is sufficient
to perform a one-sided binary search where, at each step, we apply Lemma 3.
Note that this value $k$ computed is in fact $diam(H_{0})$ (resp.,
$diam(H_{1})$). In particular, the total running time is in $\tilde{\cal
O}(mk)=\tilde{\cal O}(mD)=\tilde{\cal O}(m\sqrt{n})$. Then, in order to
compute the peripheral vertices of $H_{0}$ (resp., of $H_{1}$), it is
sufficient to apply Lemma 3 one more time in order to compute the vertices of
eccentricity at most $k-1$.

  * •

Otherwise, $D\geq\sqrt{n}$, and we apply Algorithm 1 to both $H_{0}$ and
$H_{1}$. Since by Lemma 1, both $H_{0}$ and $H_{1}$ are Helly graphs, we have
by Lemma 4 that the output of Algorithm 1 is correct with high probability.
Furthermore, since any breadth-first search in either $H_{0}$ or $H_{1}$ can
be simulated with a breadth-first search in $G$, the total running time for
executing Algorithm 1 is with high probability (by Lemma 4) in $\tilde{\cal
O}(mn/D)=\tilde{\cal O}(m\sqrt{n})$.

Finally, in order to compute $diam(G)$ from the peripheral vertices of $H_{0}$
and $H_{1}$, we apply the criterion of Lemma 2. For that, it is sufficient to
scan the neighbourhood of each peripheral vertex of $H_{0}$ and $H_{1}$, and
therefore it can be done in linear time. ∎

###  2.2 Chordal bipartite graphs

We improve Theorem 2 for the special case of chordal bipartite graphs. Recall
(amongst many characterizations) that a bipartite graph is chordal bipartite
if and only if every induced cycle has length four [58]. It was proved in [6]
that every chordal bipartite graph is an absolute retract of bipartite graphs.

######  Theorem 3.

If $G=(V,E)$ is chordal bipartite then we can compute all the eccentricities
(and so, the diameter) in linear time.

The remaining of this section is devoted to a proof of Theorem 3. For that, we
subdivide our proof into four main steps (undefined terminology below is
introduced step by step in this section):

  1. 1.

We base ourselves on the results from [19, 43] in order to prove that $H_{0}$
and $H_{1}$ – the two Helly graphs induced by the partite sets of $G$ in its
square – are strongly chordal graphs.

  2. 2.

The same as in Sec. 2.1, in general we cannot compute $H_{0}$ and $H_{1}$ from
$G$ in subquadratic time. In order to overcome this issue, we explain how to
compute a clique-tree for these two graphs.

  3. 3.

Then, we present an algorithm in order to compute all the eccentricities for
strongly chordal graphs, being given as input the clique-tree of such graph
(i.e., instead of its adjacency list).

  4. 4.

Finally, we present an “all eccentricities” version of Lemma 2, and we explain
how to solve the corresponding algorithmic problem for chordal bipartite
graphs.

#### The chordal structure of the partite sets.

A graph is chordal if it has no induced cycle of length more than three. It is
strongly chordal if it is chordal and it does not contain any $n$-sun ($n\geq
3$) as an induced subgraph [52]. A dually chordal graph is a Helly graph in
which the intersection graph of balls is chordal [5, 19]; for other
characterizations of this graph class, see [19]. The relation between dually
chordal graphs and strongly chordal graphs is as follows:

######  Lemma 5 ([19]).

A graph is strongly chordal if and only if each induced subgraph is dually
chordal.

The $k^{th}$-iterated neighbourhood of a vertex $V$, denoted $N^{k}_{G}(v)$,
is defined recursively as: $N_{G}^{1}(v)=N_{G}(v)$ (open neighbourhood) and
$N_{G}^{k+1}(v)=N_{G}(N_{G}^{k}(v))$ [43]. The following observation was used
implicitly in Lemma 3:

######  Lemma 6.

If $G=(V_{0}\cup V_{1},E)$ is bipartite then, for every $k\geq 1$ and $v\in
V_{0}$, $N_{G}^{2k}(v)=N_{H_{0}}^{k}[v]$.

###### Proof.

By induction, for every $k\geq 1$, $N_{G}^{2k-1}(v)=N_{G}^{2k-1}[v]\cap V_{1}$
and $N_{G}^{2k}(v)=N_{G}^{2k}[v]\cap V_{0}$. The lemma follows since we have
$N_{H_{0}}^{k}[v]=N_{G}^{2k}[v]\cap V_{0}$. ∎

For a vertex $v$ in $G$, a maximum neighbour111This terminology is sometimes
used, with a different meaning, for dually chordal graphs [19]. is a vertex
$u\in N_{G}(v)$ such that, for any other $w\in N_{G}(v)$, we have
$N_{G}(w)\subseteq N_{G}(u)$. A vertex $v^{\prime}\neq v$ such that
$N_{G}(v)\subseteq N_{G}(v^{\prime})$ is said to cover $v$. Finally a maximum
neighbourhood ordering of $G$ is a total ordering
$V=(v_{1},v_{2},\ldots,v_{n})$ of its vertex-set such that, for every $1\leq
i\leq n-2$, the vertex $v_{i}$ has a maximum neighbour and is covered in the
induced subgraph $G_{i}:=G\setminus\\{v_{1},v_{2},\ldots,v_{i-1}\\}$. We do
not use the existence of a maximum neighbourhood ordering directly in our
proofs, but rather the following two related results:

######  Lemma 7 ([43]).

$G=(V,E)$ is chordal bipartite if and only if every induced subgraph of $G$
has a maximum neighbourhood ordering.

######  Lemma 8 (items (iii) and (v) of the main theorem in [43]).

$G$ has a maximum neighbourhood ordering if and only if the system of all
iterated neighbourhoods has the Helly property and its intersection graph is
chordal.

The next result now follows by combining Lemmas 5–8.

######  Lemma 9.

If $G=(V_{0}\cup V_{1},E)$ is chordal bipartite, then $H_{0}$ and $H_{1}$ are
strongly chordal.

###### Proof.

By symmetry, it suffices to prove the result for $H_{0}$. For that, by Lemma
9, it is sufficient to prove that every induced subgraph of $H_{0}$ is dually
chordal. Let $U\subseteq V_{0}$ be arbitrary. We define $G_{U}$ as the
subgraph induced by $N_{G}[U]$ (the union of $U$ and of all the vertices of
$V_{1}$ with a neighbour in $U$). By construction, $H_{0}[U]$ is exactly the
graph with vertex-set $U$ and an edge between every two vertices with a common
neighbour in $G_{U}$. Furthermore, since the class of chordal bipartite graphs
is hereditary, $G_{U}$ is chordal bipartite, and so, by [6], an absolute
retract of bipartite graphs. It thus follows from Lemma 1 that $H_{0}[U]$ is a
Helly graph. In order to prove that $H_{0}[U]$ is dually chordal, it now
suffices to prove that the intersection graph of its balls is chordal. By the
combination of Lemmas 7 and 8, the intersection graph $I_{U}$ of all iterated
neighbourhoods of $G_{U}$ is chordal. By Lemma 6, the intersection graph of
all balls of $H_{0}[U]$ is an induced subgraph of $I_{U}$ and therefore, it is
also chordal. ∎

#### Computation of a clique-tree.

For a graph $H=(V,E)$, a clique-tree is a tree $T$ whose nodes are the maximal
cliques of $H$ and such that, for every $v\in V$, the maximal cliques of $H$
containing $v$ induce a connected subtree $T_{v}$ of $T$. It is well-known
that $H$ is chordal if and only if it has a clique-tree [21, 55, 81]. Our
intermediate goal is, given a chordal bipartite graph $G=(V_{0}\cup V_{1},E)$,
to compute a clique-tree for $H_{0}$ and $H_{1}$ (that are chordal graphs by
the above Lemma 9).

A hypergraph ${\cal H}=(X,{\cal R})$ is called a dual hypertree if there
exists a tree $T$ whose nodes are the hyperedges in ${\cal R}$ and such that,
for every $x\in X$, the hyperedges containing $x$ induce a connected subtree
$T_{x}$ of $T$ (such tree $T$ is called a join tree of ${\cal H}$). Note that
dual hypertrees can be recognized in linear time [80]. Furthermore, we have:

######  Lemma 10 ([43]).

If $G=(V_{0}\cup V_{1},E)$ is chordal bipartite then, both hypergraphs
$(V_{0},\\{N_{G}(v)\mid v\in V_{1}\\})$ and $(V_{1},\\{N_{G}(v)\mid v\in
V_{0}\\})$ are dual hypertrees.

######  Corollary 1.

If $G=(V_{0}\cup V_{1},E)$ is chordal bipartite then, we can compute a clique-
tree for $H_{0}$ and $H_{1}$ in linear time.

###### Proof.

By symmetry, we only prove the result for $H_{0}$. Consider the hypergraph
${\cal H}=(V_{0},\\{N_{G}(v)\mid v\in V_{1}\\})$. Note that the underlying
graph of ${\cal H}$ (obtained by adding an edge between every two vertices
that are contained in a common hyperedge of ${\cal H}$) is exactly $H_{0}$.
Since by Lemma 10, ${\cal H}$ is a dual hypertree, every maximal clique of the
underlying graph $H_{0}$ must be a hyperedge of ${\cal H}$ [12]. Then, let us
reduce ${\cal H}$, i.e., we remove all hyperedges that are strictly contained
into another hyperedge. Again since ${\cal H}$ is a dual hypertree, the
resulting reduced hypergraph ${\cal H}^{\prime}$ can be computed in linear
time [80]. Furthermore, by construction, the hyperedges of ${\cal H}^{\prime}$
are exactly the maximal cliques of $H_{0}$. Let us construct a join tree of
${\cal H}^{\prime}$. It can be done in linear time [80]. We are done as such
join tree is a clique-tree of $H_{0}$. ∎

#### Computation of all the eccentricities in the partite sets.

Next, we propose a new algorithm in order to compute all the eccentricities of
a strongly chordal graph $H$, being given a clique-tree. We often use in our
proof the clique-vertex incidence graph of $H$, i.e., the bipartite graph
whose partite sets are the vertices and the maximal cliques of $H$, and such
that there is an edge between every vertex of $H$ and every maximal clique of
$H$ containing it.

Let us first recall the following result about the eccentricity function of
Helly graphs:

######  Lemma 11 ([36]).

If $H=(V,E)$ is Helly then, for every vertex $v$ we have
$e_{H}(v)=d_{H}(v,C(H))+rad(H)$, where $C(H)$ denotes the set of central
vertices of $H$.

Hence, by Lemma 11, we are left computing $C(H)$. It starts with computing one
central vertex. Define, for every vertex $v$ and vertex-subset $C$,
$d_{H}(v,C)=\min_{c\in C}d_{H}(v,c)$. Following [27], we call a set $C$ gated
if, for every $v\notin C$, there exists a vertex $v^{*}\in
N_{H}^{d_{H}(v,C)-1}[v]\cap\left(\bigcap\\{N_{H}(c)\mid c\in C,\
d_{H}(v,c)=d_{H}(v,C)\\}\right)$ (such vertex $v^{*}$ is called a gate of
$v$).

######  Lemma 12 ([24]).

Every clique in a chordal graph is a gated set.

######  Lemma 13 ([48]).

If $T$ is a clique-tree of a chordal graph $H$ then, for every clique $C$ of
$H$, for every $v\notin C$ we can compute $d_{H}(v,C)$ and a corresponding
gate $v^{*}$ in total ${\cal O}(w(T))$ time, where $w(T)$ denotes the sum of
cardinalities of all the maximal cliques of $H$.

For every $u,v\in V$ and $k\leq d_{H}(u,v)$, the set $L_{H}(u,k,v)=\\{x\in
I_{H}(u,v)\mid d_{H}(u,x)=k\\}$ is called a slice. We also need the following
result about slices in chordal graphs:

######  Lemma 14 ([24]).

Every slice in a chordal graph is a clique.

Now, consider the procedure described in Algorithm 2 in order to compute a
central vertex.

Algorithm 2 Computation of a central vertex.

0: A strongly chordal graph $H$.

1: $v\leftarrow$ an arbitrary vertex of $H$

2: $u\leftarrow$ a furthest vertex from $v$, i.e., $d_{H}(u,v)=e_{H}(v)$

3: $w\leftarrow$ a furthest vertex from $u$, i.e., $d_{H}(u,w)=e_{H}(u)$

4: for all $r\in\\{\left\lceil
e_{H}(u)/2\right\rceil,\left\lceil(e_{H}(u)+1)/2\right\rceil,1+\left\lceil
e_{H}(u)/2\right\rceil\\}$ do

5: Set $C:=L(w,r,u)$ //$C$ is a clique by Lemma 14

6: for all $v\notin C$ do

7: Compute $d_{H}(v,C)$ and a corresponding gate $v^{*}$ //whose existence
follows from Lemma 12

8: Set $S:=\\{v^{*}\mid d_{H}(v,C)=r\\}$ //gates of vertices at max. distance
from $C$

9: for all $c\in C$ do

10: if $S\subseteq N_{H}(c)$ then

11: return $c$

######  Lemma 15 (special case of Theorem 5 in [48]).

Algorithm 2 outputs a central vertex of $H$.

######  Lemma 16.

If $T$ is a clique-tree of a strongly chordal graph $H$ then, we can implement
Algorithm 2 in order to run in ${\cal O}(w(T))$ time, where $w(T)$ denotes the
sum of cardinalities of all the maximal cliques of $H$.

###### Proof.

Lines 1–3 require executing breadth-first searches in $H$. It can be done in
${\cal O}(w(T))$ time by executing breadth-first searches in the clique-vertex
incidence graph $I_{H}$ of $H$. Note that we can compute $I_{H}$ in ${\cal
O}(w(T))$ time from the clique-tree $T$. Now, consider any of the at most
three executions of the for loop starting at Line 4. The subset $C$ at Line 5
can also be computed in ${\cal O}(w(T))$ time using breadth-first searches in
$I_{H}$. Then, for implementing the computation of all the gates, at Line 6–7,
we call Lemma 13. We are left explaining how to implement the internal for
loop, starting at Line 9, so that it runs in total ${\cal O}(w(T))$ time. For
that, we assign a counter $g(c)$ for every $c\in C$ (initially equal to $0$),
whose final value must be $|N_{H}(c)\cap S|$. Doing so, the test at Line 10
boilds down to verifying whether $g(c)=|S|$. In order to correctly set the
values of the counters $g(c),\ c\in C$, we root the clique-tree $T$
arbitrarily and then we perform a breadth-first search of this tree $T$
starting from the root. For each maximal clique $K$ of $H$, let $K^{\prime}$
be the common intersection with its father node in $T$ (in particular,
$K^{\prime}=\emptyset$ if $K$ is the root). For every $c\in C\cap(K\setminus
K^{\prime})$, we increase the counter $g(c)$ by exactly $|K\cap S|$. However,
for every $c\in C\cap K^{\prime}$, we only increase the counter $g(c)$ by
$|S\cap(K\setminus K^{\prime})|$; indeed, for these vertices, the contribution
of the gates in $S\cap K^{\prime}$ was already counted earlier during the
breadth-first search. Overall, we just need to scan each maximal clique of $H$
once, and so, the running time is in ${\cal O}(w(T))$, as desired. ∎

Then, given a central vertex $c$ of $H$, we explain how to compute $C(H)$ by
local search in the neighbourhood at distance two around $c$. For that, we
need one more structural result about the center of strongly chordal graphs,
namely:

######  Lemma 17 ([36, 37]).

If $H$ is strongly chordal then, its center $C(H)$ induces a strongly chordal
graph of radius $\leq 1$.

We also need the following nice characterization of strongly chordal graphs,
namely:

######  Lemma 18 ([18, 52]).

$H$ is strongly chordal if and only if its clique-vertex incidence graph
$I_{H}$ is chordal bipartite.

######  Proposition 1.

If $T$ is a clique-tree of a strongly chordal graph $H=(V,E)$ then, we can
compute its center $C(H)$ in ${\cal O}(w(T))$ time.

###### Proof.

Let $c\in C(H)$ be a fixed central vertex of $H$. By the combination of Lemmas
15 and 16, it can be computed in ${\cal O}(w(T))$ time. We also compute the
clique-vertex incidence graph $I_{H}$ from $T$, in ${\cal O}(w(T))$ time. Let
$r:=rad(H)$ (computable in ${\cal O}(w(T))$ time by using a breadth-first
search rooted at $c$ in $I_{H}$). Note that if $r\leq 2$, then in order to
compute $C(H)$, we are left computing all the vertices of eccentricity at most
$r$ in $H$. For that, since by Lemma 18 $I_{H}$ is chordal bipartite, we can
use Lemma 3. It takes time linear in the size of $I_{H}$, and so it takes
${\cal O}(w(T))$ time. From now on, we assume $r\geq 3$. By Lemma 17,
$C(H)\subseteq N_{H}^{2}[c]$. In particular, If $v\in V$ is such that
$d_{H}(v,c)\leq r-2$ then it is trivially at a distance $\leq r$ from every
vertex of $N_{H}^{2}[c]$. Thus, in order to compute $C(H)$ from
$N_{H}^{2}[c]$, we only need to consider the subsets $A_{r-1}:=\\{v\in V\mid
d_{H}(v,c)=r-1\\}$ and $A_{r}:=\\{v\in V\mid d_{H}(v,c)=r\\}$. We prove as an
intermediate claim that $N_{H}[c]$ is gated. Indeed, for every $v\notin
N_{H}[c]$, the closest vertices to $v$ in this closed neighbourhood are those
in the slice $L(v,d_{H}(v,c)-1,c)$, and thus they induce a clique by Lemma 14.
Then, the claim follows from Lemma 12. Furthermore, for every $v\notin
N_{H}[c]$, we can compute a corresponding gate $v^{*}$ as follows: we contract
in $T$ the subtree $T_{c}$ (induced by all the maximal cliques containing $c$)
to a single node representing $N_{H}[c]$, then we apply Lemma 13. It takes
${\cal O}(w(T))$ time.

Now, let $v\in A_{r-1}\cup A_{r}$. If the closed neighbourhood of any vertex
$u$ intersects $N_{H}[c]\cap N_{H}^{r-1}[v]$ then, $d_{H}(u,v)\leq r$.
Conversely, we claim that the closed neighbourhood of any central vertex must
intersect $N_{H}[c]\cap N_{H}^{r-1}[v]$. Indeed, observe that for every
$c^{\prime}\in C(H)$, $N_{H}[c^{\prime}]\cap N_{H}^{r-1}[v]\neq\emptyset$. By
Lemma 17, the balls $N_{H}[c^{\prime}],\ c^{\prime}\in C(H)$ also pairwise
intersect. Therefore, by the Helly property, there exists a $x\in
N^{r-1}_{H}[v]\cap\left(\bigcap_{c^{\prime}\in C(H)}N_{H}[c^{\prime}]\right)$.
We are done as in this situation $x\in N_{H}[c]\cap N_{H}^{r-1}[v]$. We now
analyse the following two cases:

Case $v\in A_{r}$. Let $v^{*}$ be the corresponding gate. Note that
$d_{H}(v^{*},c)=d_{H}(v,N_{H}[c])-1=d_{H}(v,c)-2=r-2$. In particular, every
vertex of $N_{H}^{2}[v^{*}]$ is at a distance $\leq r$ from vertex $v$.
Conversely, the closed neighbourhood of every central vertex must intersect
$N_{H}[c]\cap N^{r-1}_{H}[v]=L(v,r-1,c)\subseteq N_{H}[v^{*}]$. As a result,
$C(H)\subseteq N_{H}^{2}[v^{*}]$.

Case $v\in A_{r-1}$. Let $Z=\\{z\in N_{H}[c]\mid d_{H}(v,c)=r-1\\}$. Note that
$c\in Z$. Since the balls $N^{r-2}_{H}[v]$ and $N_{H}[z],\ z\in Z$ pairwise
intersect, by the Helly property there exists a vertex $v^{\prime}\in
N_{H}^{r-2}[v]\cap\left(\bigcap\\{N_{H}(z)\mid z\in Z\\}\right)$. Observe that
$v^{\prime}\in N_{H}^{r-2}[v]\cap N_{H}[c]=L(v,r-2,c)$. In particular, every
vertex of $N_{H}^{2}[v^{\prime}]$ is at a distance $\leq r$ from $v$.
Conversely, since by Lemma 14 the set $L(v,r-2,c)$ is a clique,
$N_{H}^{r-1}[v]\cap N_{H}[c]=L(v,r-2,c)\cup Z\subseteq N_{H}[v^{\prime}]$.
Thus, $C(H)\subseteq N_{H}^{2}[v^{\prime}]$.

Note that we may choose as our $v^{\prime}$ any $y\in N_{H}(v^{*})$ that
maximizes $|N_{H}[y]\cap N_{H}[c]|$, where $v^{*}$ is the gate computed for
$v$. In order to compute such vertex $v^{\prime}$, for every $v\in A_{r-1}$,
we use a similar trick as for Lemma 16. Namely, for every $y\in V$, we assign
a counter $h(y)$ (initially equal to $0$), whose final value must be
$|N_{H}[y]\cap N_{H}[c]|$. In order to correctly set the values of these
counters, we root the clique-tree $T$ arbitrarily and then we perform a
breadth-first search of this tree $T$ starting from the root. For each maximal
clique $K$ of $H$, let $K^{\prime}$ be the common intersection with its father
node in $T$ (in particular, $K^{\prime}=\emptyset$ if $K$ is the root). For
every $y\in K\setminus K^{\prime}$, we increase the counter $h(y)$ by exactly
$|K\cap N_{H}[c]|$. However, for every $y\in K^{\prime}$, we only increase the
counter $h(y)$ by $|N_{H}[c]\cap(K\setminus K^{\prime})|$. Overall, we just
need to scan each maximal clique of $H$ once, and so, the running time is in
${\cal O}(w(T))$. Finally, we scan each maximal clique $K$ once more and, to
every vertex of $K$, we assign a vertex $y\in K$ maximizing $h(y)$. For every
$v\in A_{r-1}$, we choose for $v^{\prime}$ any vertex $y$ assigned to $v^{*}$
and maximizing $h(y)$.

Overall, let $B:=\\{c\\}\cup\\{v^{*}\mid v\in A_{r}\\}\cup\\{v^{\prime}\mid
v\in A_{r-1}\\}$. By the above case analysis, $C(H)=\\{x\in V\mid\forall b\in
B,\ d_{H}(b,x)\leq 2\\}$. Since $I_{H}$ is chordal bipartite (Lemma 18) we can
adapt the technique of Lemma 3 in order to compute $C(H)$ (i.e., we set $k=2$,
and then compute partitions of the subset $B$ instead of computing partitions
for the full half-set $V$). It takes time linear in the size of $I_{H}$, and
so, it can be done in ${\cal O}(w(T))$ time. ∎

#### Computation of all the eccentricities in $G$.

Before proving Theorem 3, we need a final ingredient. Let us first generalize
Lemma 2 as follows.

######  Lemma 19.

If $G=(V_{0}\cup V_{1},E)$ is an absolute retract of bipartite graphs then,
the following holds for every $i\in\\{0,1\\}$ and $v\in V_{i}$:

  * •

If $e_{H_{i}}(v)\leq rad(H_{1-i})-1$ then,
$e_{G}(v)=2e_{H_{i}}(v)+1=2rad(H_{1-i})-1$.

  * •

If $e_{H_{i}}(v)=rad(H_{1-i})$ then, $e_{G}(v)=2rad(H_{1-i})$ if and only if
$N_{G}(v)\subseteq C(H_{1-i})$ and, for every $u\in V_{1-i}$, we have
$d_{H_{1-i}}(u,N_{G}(v))\leq rad(H_{1-i})-1$ (otherwise,
$e_{G}(v)=2rad(H_{1-i})+1$).

  * •

If $e_{H_{i}}(v)\geq rad(H_{1-i})+1$ then, $e_{G}(v)=2e_{H_{i}}(v)$ if and
only if we have $e_{H_{1-i}}(u)<e_{H_{i}}(v)$ for some neighbour $u\in
N_{G}(v)$ (otherwise, $e_{G}(v)=2e_{H_{i}}(v)+1$).

###### Proof.

Let us first consider the case $e_{H_{i}}(v)\leq rad(H_{1-i})-1$. In
particular, every neighbour $u\in N_{G}(v)$ is at a distance $\leq
1+2e_{H_{i}}(v)+1\leq 2rad(H_{1-i})$ from any vertex of $V_{1-i}$. Therefore,
$e_{H_{i}}(v)=rad(H_{1-i})-1$, and every vertex of $N_{G}(v)$ is central in
$H_{1-i}$. Observe that $v$ must be at a distance $\geq 2rad(H_{1-i})-1$ from
at least one vertex of $V_{1-i}$ since otherwise, the eccentricity of all the
vertices of $N_{G}(v)$, in $H_{1-i}$, would be $<rad(H_{1-i})$. As a result,
$e_{G}(v)=2rad(H_{1-i})-1$.

Now, consider the case $e_{H_{i}}(v)=rad(H_{1-i})$. Then, since $G$ is
bipartite, we have $e_{G}(v)=2rad(H_{1-i})$ if and only if every vertex of
$V_{1-i}$ is at a distance $\leq 2rad(H_{1-i})-1$ from vertex $v$ (otherwise,
$e_{G}(v)=2rad(H_{1-i})+1$). Equivalently, $e_{G}(v)=2rad(H_{1-i})$ if and
only if, for every $u\in V_{1-i}$, we have $d_{G}(u,N_{G}(v))\leq
2rad(H_{1-i})-2$. Again, since $d_{H_{1-i}}(u,N_{G}(v))=d_{G}(u,N_{G}(v))/2$,
the latter is equivalent to have $d_{H_{1-i}}(u,N_{G}(v))\leq rad(H_{1-i})-1$.
Note that since $N_{G}(v)$ is a clique of $H_{1-i}$, this last equivalence
also implies that $N_{G}(v)\subseteq C(H_{1-i})$.

Finally, consider the case $e_{H_{i}}(v)\geq rad(H_{1-i})+1$. If furthermore
there is a neighbour $u\in N_{G}(v)$ s.t. $e_{H_{1-i}}(u)<e_{H_{i}}(v)$ then,
vertex $v$ is at a distance at most $2e_{H_{1-i}}(u)+1<2e_{H_{i}}(v)$ from
every vertex of $V_{1-i}$, and so, $e_{G}(v)=2e_{H_{i}}(v)$. Now, let us
assume to have $e_{H_{1-i}}(u)\geq e_{H_{i}}(v)$ for every neighbour $u\in
N_{G}(v)$. Suppose for the sake of contradiction $e_{G}(v)<2e_{H_{i}}(v)+1$.
In particular, every vertex of $V_{1-i}$ must be at a distance at most
$2e_{H_{i}}(v)-1$ from vertex $v$. Equivalently for any $x\in V_{1-i}$, the
half-balls $N_{G}(v)$ and $N_{G}^{2e_{H_{i}}(v)-2}[x]\cap V_{1-i}$ intersect.
Note that $2e_{H_{i}}(v)-2\geq 2rad(H_{1-i})\geq diam(H_{1-i})$. Hence, the
half-balls $N_{G}^{2e_{H_{i}}(v)-2}[x]\cap V_{1-i},\ x\in V_{1-i}$ also
pairwise intersect. But then, by Theorem 1, there is a neighbour $u\in
N_{G}(v)$ such that $e_{H_{1-i}}(u)\leq(2e_{H_{i}}(v)-2)/2=e_{H_{i}}(v)-1$. A
contradiction. ∎

Of the three cases in the above Lemma 19, the real algorithmic challenge is
the case $e_{H_{i}}(v)=rad(H_{1-i})$, for some $i\in\\{0,1\\}$. Finally, we
prove that such case can be solved in linear time for chordal bipartite
graphs.

###### Proof of Theorem 3.

By Lemma 9, $H_{0}$ and $H_{1}$ are strongly chordal graphs. We compute
clique-trees $T_{0}$ and $T_{1}$ for both $H_{0}$ and $H_{1}$, that takes
linear time by Corollary 1. Note that in particular, for each $i\in\\{0,1\\}$
we get $w(T_{i})={\cal O}(m+n)$, with $w(T_{i})$ the sum of the cardinalities
of the maximal cliques of $H_{i}$. Then, we compute all the eccentricities of
$H_{0}$ (resp, of $H_{1}$), that is ${\cal O}(w(T_{0}))$-time equivalent to
computing $C(H_{0})$ according to Lemma 11 (resp., ${\cal O}(w(T_{1}))$-time
equivalent to computing $C(H_{1})$). By Proposition 1, the center can be
computed in ${\cal O}(w(T_{0}))$ time (resp., in ${\cal O}(w(T_{1}))$ time).
Overall, for each $i\in\\{0,1\\}$ and every $v\in V_{i}$, we so computed
$e_{H_{i}}(v)$. It takes total linear time. Doing so, we can also compute
$rad(H_{0})$ and $rad(H_{1})$ within the same amount of time. Finally, we are
left explaining how to deduce from the latter the eccentricities $e_{G}(v),\
v\in V_{0}$ (the case $v\in V_{1}$ is symmetric to this one). By Lemma 19, if
$e_{H_{0}}(v)\neq rad(H_{1})$ then, we can compute $e_{G}(v)$ by scanning the
neighbour set $N_{G}(v)$. Therefore, in total ${\cal O}(m)$ time, we can
compute $e_{G}(v)$ for every $v\in V_{0}$ s.t. $e_{H_{0}}(v)\neq rad(H_{1})$.
In the same way, for every $v\in V_{0}$ s.t. $e_{H_{0}}(v)=rad(H_{1})$ and
$N_{G}(v)\not\subseteq C(H_{1})$, we set directly $e_{G}(v)=2rad(H_{1})+1$,
that is correct by Lemma 19, and it also takes ${\cal O}(m)$ time in total.

Let $S:=\\{v\in V_{0}\mid e_{H_{0}}(v)=rad(H_{1}),\ N_{G}(v)\subseteq
C(H_{1})\\}$. By Lemma 19, every vertex of $S$ has eccentricity either
$2rad(H_{1})$ or $2rad(H_{1})+1$ in $G$. We may further assume $rad(H_{1})\geq
3$ because otherwise, we can compute the eccentricity of all the vertices of
$S$ in total ${\cal O}(m)$ time by applying the technique of Lemma 3. In this
situation, we define a set $W\subseteq V_{1}$ with the following property: for
every $v\in S$, we have $e_{G}(v)=2rad(H_{1})$ if and only if for every $w\in
W$ we have $d_{G}(v,w)\leq 3$. Note that doing so, we may compute the
eccentricity of all the vertices of $S$ in ${\cal O}(m)$ time by applying the
same technique as for Lemma 3 (i.e., we set $k=3$, then we compute partitions
for $W$ rather than for the full half-set $V_{1}$). Furthermore, in order to
compute this set $W$, we proceed in a quite similar fashion as for Proposition
1. We detail this procedure next.

The algorithm. Let $r=rad(H_{1})$. First, we compute a vertex $c\in C(H_{1})$
that is adjacent to all the central vertices of $H_{1}$ (such vertex is
guaranteed to exist by Lemma 17). For every $u\in V_{1}$ s.t.
$d_{H_{1}}(u,c)\geq r-1$, we compute a vertex $u^{*}\in
N_{H_{1}}^{r-2}[u]\cap\left(\bigcap\\{N_{H_{1}}[x]\mid x\in N_{H_{1}}[c]\cap
N^{r-1}_{H_{1}}[u]\\}\right)$ and we add this gate $u^{*}$ to the set $W$.

Correctness. By Lemma 19, for every $v\in S$, we have $e_{G}(v)=2rad(H_{1})$
if and only if, for every $u\in V_{1},\ d_{H_{1}}(u,N_{G}(v))\leq r-1$. Note
that if $d_{H_{1}}(u,c)\leq r-2$ then, the distance in $H_{1}$ between $u$ and
any vertex of $C(H_{1})$ is at most $r-1$. So, we are only interested in those
$u$ s.t. $d_{H_{1}}(u,c)\geq r-1$. Assume the existence for such vertex $u$ of
a $u^{*}\in N_{H_{1}}^{r-2}[u]\cap\left(\bigcap\\{N_{H_{1}}[x]\mid x\in
N_{H_{1}}[c]\cap N^{r-1}_{H_{1}}[u]\\}\right)$. If $d_{G}(v,u^{*})\leq 3$
then, $d_{G}(u,v)\leq 3+2(r-2)=2r-1$, as desired. Conversely, if
$e_{G}(v)=2rad(H_{1})$ then there must be a $c_{u}\in N_{G}(v)\subseteq
C(H_{1})$ s.t. $d_{H_{1}}(c_{u},u)\leq r-1$. In particular, $c_{u}\in
N_{H_{1}}[c]\cap N^{r-1}_{H_{1}}[u]\subseteq N_{H_{1}}[u^{*}]$ and therefore,
$d_{G}(v,u^{*})\leq
d_{G}(v,c_{u})+d_{G}(c_{u},u^{*})=1+2d_{H_{1}}(c_{u},u^{*})\leq 3$. The
existence of a $u^{*}$ as above was already proved in Proposition 1, but we
repeat here the arguments for completeness. There are two cases. If
$d_{H_{1}}(u,c)=r$ then, $N_{H_{1}}[c]\cap
N^{r-1}_{H_{1}}[u]=L_{H_{1}}(u,r-1,c)$, and the result follows from the
combination of Lemmas 14 and 12. Otherwise, $d_{H_{1}}(u,c)=r-1$, and let
$Z=\\{z\in N_{H_{1}}[c]\mid d_{H_{1}}(u,z)=r-1\\}$. Since the balls
$N_{H_{1}}^{r-2}[u]$ and $N_{H_{1}}[z],\ z\in Z$ pairwise intersect, by the
Helly property, there exists a $u^{*}\in
N_{H_{1}}^{r-2}[u]\cap\left(\bigcap\\{N[z]\mid z\in Z\\}\right)$. Observe that
by construction, $u^{*}\in L_{H_{1}}(u,r-2,c)$, that is a clique according to
Lemma 14. We are done as $N^{r-1}_{H_{1}}[u]\cap
N_{H_{1}}[c]=L_{H_{1}}(u,r-2,c)\cup Z\subseteq N_{H_{1}}[u^{*}]$.

Complexity. The constructive proof of Proposition 1 yields an ${\cal
O}(w(T_{1}))$-time algorithm in order to compute $W$. Therefore, this set $W$
can be constructed in linear time. ∎

##  3 $k$-chromatic graphs

Recall that a proper $k$-coloring of $G=(V,E)$ is any mapping
$c:V\to\\{1,2,\ldots,k\\}$ such that $c(u)\neq c(v)$ for every edge $uv\in E$.
The chromatic number of $G$ is the least $k$ such that it has a proper
$k$-coloring, and a $k$-chromatic graph is a graph whose chromatic number is
equal to $k$. Note in particular with this definition that a $(k-1)$-chromatic
graph is not $k$-chromatic. We study the diameter within the absolute retracts
of $k$-chromatic graphs, for every fixed $k\geq 3$.

Our approach requires such graphs to be equipped with a proper $k$-coloring.
While this is a classic NP-hard problem for every $k\geq 3$ [65], it is known
that it can be done in polynomial time for absolute retracts of $k$-chromatic
graphs [10]. We remind this colouring algorithm in Sec. 3.1 where we observe
it can be implemented in order to run in linear time. Our general framework
for diameter computation (somehow mimicking what we did in Sec. 2.1) is
presented in Sec. 3.2. We complete our approach in Sec. 3.3, before concluding
this section with its main result in Sec 3.4.

###  3.1 Colouring algorithm

We start with a reminder of the Colouring algorithm presented in [10]
(Algorithm 3). The description below is exactly the same as in [10], where an
${\cal O}(n^{2})$ running-time was claimed.

Algorithm 3 Colouring algorithm.

0: A graph $G=(V,E)$.

1: Pick a vertex $u$ and let $K$ be a maximal clique containing $u$.

2: Let $k:=|K|$ and let $c:K\to\\{1,2,\ldots,k\\}$ be a proper $k$-coloring.
For each $v\in K\setminus\\{u\\}$, colour the common neighbours of
$K\setminus\\{v\\}$ with $c(v)$. Then, let $L$ be the set of vertices coloured
so far. For each neighbour $v$ of $u$ not in $L$, there is a unique colour $i$
such that $u$ does not have a neighbour in $L$ with colour $i$ (otherwise, $G$
is not an absolute retract). Assign $c(u):=i$. If $N_{G}[u]$ includes all of
$G$, then goto Step 5.

3: For each vertex $v\in V$ s.t. $d_{G}(u,v)=2$, there is a unique colour $i$
not occurring in $N_{G}(u)\cap N_{G}(v)$ or in $\\{u\\}\cup(N_{G}(u)\cap
N_{G}(v))$ (otherwise, $G$ is not an absolute retract). Assign $c(v):=i$. If
$N_{G}^{2}[u]$ includes all of $G$, then goto Step 5, otherwise assign
$\ell:=3$.

4: For each vertex $v\in V$ s.t. $d_{G}(u,v)=\ell$, there is a unique colour
$i$ not occurring in $N_{G}^{\ell-1}[u]\cap N_{G}(v)$ (otherwise, $G$ is not
an absolute retract). Assign $c(v):=i$. If $N_{G}^{\ell}[u]$ does not yet
contain all of $G$, then assign $\ell:=\ell+1$ and start Step 4 again.

5: If $c(u)=c(v)$ for some edge $uv$, then $G$ is not an absolute retract.
Otherwise, $c$ is a proper $k$-coloring of $G$, and $G$ is $k$-chromatic.

We refer to [10] for a correctness proof of Algorithm 3. Our modest, but
important contribution for our claimed running-times is as follows:

######  Proposition 2.

There is a linear-time algorithm such that, for every $k\geq 3$, if the input
$G$ is an absolute retract of $k$-chromatic graphs, then it computes a proper
$k$-coloring of $G$.

###### Proof.

Consider the following modified version of Algorithm 3:

  1. 1.

We start from an arbitrary vertex $u$ and we greedily compute a maximal clique
$K$ containing vertex $u$. It takes linear time. Furthermore, let $k:=|K|$ and
let $c:K\to\\{1,2,\ldots,k\\}$ be a proper $k$-coloring (i.e., obtained by
numbering the vertices of $K$ from $1$ to $k$).

  2. 2.

For every vertex $x\in V$, we compute $|N_{G}(x)\cap K|$. It can be done in
linear time by scanning once the neighbourhood of each vertex $v\in K$. We
consider the vertices $v\in N_{G}(u)\setminus K$ by non-increasing value of
$|N_{G}(x)\cap K|$. Note that such ordering of $N_{G}(u)\setminus K$ can be
computed using a linear-time sorting algorithm. As in the standard greedy
coloring algorithm, we assign to $v$ the least color $i$ not present in its
neighbourhood. If $i\geq k+1$ then, $G$ is not an absolute retract and we
stop. Doing so, it takes ${\cal O}(|N_{G}(v)|)$ time in order to color $v$,
and so, this whole step takes ${\cal O}(m)$ time.

  3. 3.

We perform a breadth-first search rooted at $u$. Then, we consider the
vertices $v\in V$ s.t. $d_{G}(u,v)=2$. First, we search for the least color
$i$ such that $i\neq c(u)$ and there is no neighbour of $v$ coloured $i$. If
$i\leq k$ then, we set $c(v):=i$. Otherwise, we assign to $v$ the least color
$i$ not present in $N_{G}(v)$ (possibly, $i=c(u)$). If $i\geq k+1$ then, $G$
is not an absolute retract and we stop. This whole step also takes ${\cal
O}(m)$ time.

  4. 4.

Finally, we consider all the remaining vertices $v,\ d_{G}(u,v)\geq 3$, by
non-decreasing value of $d_{G}(u,v)$ (these distances were computed during the
breadth-first search). Here also, we can compute such ordering of the
remaining vertices by using a linear-time sorting algorithm. We apply the
classic greedy coloring procedure, assigning to the current vertex $v$ the
least colour $i$ not present in its neighbourhood. If $i\geq k+1$ then $G$ is
not an absolute retract, and we stop. Overall, the whole algorithm indeed runs
in linear time.

In order to prove correctness of this above algorithm, it suffices to prove
that if $G$ is an absolute retract, then it computes the same coloring as
Algorithm 3. This is clear at Step 1, where we only colour the vertices of the
maximal clique $K$. Then, at Step 2, we start coloring the neighbours of $u$
with exactly $k-1$ neighbours in $K$. Note that the only possible color
amongst $\\{1,\ldots,k\\}$ to assign to such vertex $x$ is $c(v)$, where $v$
is the unique non-neighbour of $x$ in $K$. This is also what Algorithm 3 does.
Let $L$ be the set of vertices coloured so far. We continue coloring the
remaining neighbours $v\in N_{G}(u)\setminus L$. Algorithm 3 exploits the
property that such vertices have exactly one color $i\in\\{1,\ldots,k\\}$ that
is not present amongst their neighbours in $L$. But then, the classic greedy
coloring procedure also assigns this color $i$ to $v$. Next, consider a vertex
$v$ s.t. $d_{G}(u,v)=2$. If there is a unique available color $i$ amongst
$\\{1,\ldots,k\\}$ that is not present in $N_{G}(u)\cap N_{G}(v)$ then,
Algorithm 3 assigns this color to $v$; so does the classic greedy coloring
procedure. Otherwise, Algorithm 3 assigns to $v$ the unique color amongst
$\\{1,\ldots,k\\}$ that is not present in $\\{u\\}\cup(N_{G}(u)\cap
N_{G}(v))$; so does our modified greedy coloring procedure, where we first
exclude color $c(u)$ from the range of possibilities. Finally, similar
arguments apply to the vertices $v$ s.t. $d_{G}(u,v)\geq 3$. ∎

In the remainder of the section, we always assume the input graph $G$ to be
given with a proper $k$-coloring. We sometimes use implicitly the fact that,
for an absolute retract, such proper $k$-coloring is unique up to permuting
the colour classes [76].

###  3.2 General framework

The present section aims at introducing the necessary results and terminology
for Sec 3.3. Recall that in a graph $G=(V,E)$, a vertex $v$ is covered by
another vertex $w$ if $N_{G}(v)\subseteq N_{G}(w)$ (a covered vertex is called
embeddable in [76]). We now introduce a first characterization of absolute
retracts:

######  Theorem 4 ([76]).

Let $k\geq 3$. The graph $G=(V,E)$ is an absolute retract of $k$-chromatic
graphs if and only if for any proper $k$-coloring $c$, every peripheral vertex
$v$ is adjacent to all vertices $u$ with $c(u)\neq c(v)$, or it is covered and
$G\setminus v$ is an absolute retract of $k$-chromatic graphs.

We highlight the following special case of this characterization, that allows
us to deal with the diameter-two case separately from the general case,
namely:

######  Proposition 3 ([76]).

Let $G=(V,E)$ be an absolute retract of $k$-chromatic graphs for some $k\geq
3$, and let $c$ be a corresponding proper $k$-coloring. Then, $diam(G)\leq 2$
if and only if for every $1\leq i\leq k$, there exists a $z_{i}\in V$ with
$z_{i}v\in E$ for all $v\in V$ s.t. $c(v)\neq i$.

######  Corollary 2.

If $G=(V,E)$ is an absolute retract of $k$-chromatic graphs for some $k\geq
3$, then we can decide whether $diam(G)\leq 2$ in linear time.

###### Proof.

By Proposition 2, a proper $k$-coloring $c:V\to\\{1,\ldots,k\\}$ can be
computed in linear time. Then, we apply the criterion of Proposition 3. For
that, for each colour $i$ we choose as our candidate vertex for $z_{i}$ a
maximum-degree vertex of colour $i$. ∎

Thus, in what follows, we focus on the case $diam(G)\geq 3$. For that, we use
in combination to Theorem 4 yet another characterization of absolute retracts
(we refer the reader to [10] for other characterizations, leading to
polynomial-time recognition algorithms):

######  Theorem 5 ([10]).

Let $k\geq 3$. The graph $G=(V,E)$ is an absolute retract of $k$-chromatic
graphs if and only if the following conditions hold for any proper
$k$-coloring $c:V\to\\{1,2,\ldots,k\\}$:

  1. 1.

For each colour $i$, any family of balls intersects in colour $i$ whenever
each pair of them does.

  2. 2.

Every maximal clique of $G$ has cardinality exactly $k$.

  3. 3.

For each colour $i$ and any two non-adjacent vertices $u$ and $v$ such that:
$c(v)\neq i$, and either $c(u)\neq i$ or $d_{G}(u,v)\geq 3$, there is a
neighbour $x$ of $v$ on a shortest $uv$-path s.t. $c(x)=i$.

Let $G=(V,E)$ be equipped with a proper $k$-coloring $c$. For every colour
$i$, let $V_{i}:=\\{v\in V\mid c(v)=i\\}$ be called a colour class. We define,
for every $v\in V_{i}$, $e_{i}(v):=\max\\{d_{G}(u,v)\mid u\in V_{i}\\}$. A
vertex $v\in V_{i}$ is $i$-peripheral if it maximizes $e_{i}(v)$. Finally, let
$d_{i}:=\max\\{e_{i}(v)\mid v\in V_{i}\\}$. We now generalize Lemma 2, as
follows:

######  Lemma 20.

Let $G=(V,E)$ be an absolute retract of $k$-chromatic graphs for some $k\geq
3$, and let $c$ be a corresponding proper $k$-coloring. Then, $\max_{1\leq
i\leq k}d_{i}\leq diam(G)\leq 1+\max_{1\leq i\leq k}d_{i}$. Moreover, if
$diam(G)\geq 3$, then we have $diam(G)=1+\max_{1\leq i\leq k}d_{i}$ if and
only if:

  * •

either $\max_{1\leq i\leq k}d_{i}=2$;

  * •

or, for some $i\neq j$ s.t. $d_{i}=d_{j}$ is maximized, there is some
$i$-peripheral vertex whose all neighbours coloured $j$ are $j$-peripheral.

###### Proof.

Clearly, we have $\max_{1\leq i\leq k}d_{i}\leq diam(G)$. In order to prove
that we also have $diam(G)\leq 1+\max_{1\leq i\leq k}d_{i}$, it suffices to
prove that each colour class $V_{i}$ is a dominating set of $G$. For that,
consider any vertex $v\in V\setminus V_{i}$. Let $K$ be a maximal clique
containing $v$. By Theorem 5, we have $|K|=k$, and therefore, $K\cap
V_{i}\neq\emptyset$. In particular, $N_{G}(v)\cap V_{i}\neq\emptyset$, as
desired.

In what follows, $diam(G)\geq 3$. Then, if $\max_{1\leq i\leq k}d_{i}=2$, we
must have $diam(G)=1+\max_{1\leq i\leq k}d_{i}=3$. From now on, we assume
$diam(G)\geq\max_{1\leq i\leq k}d_{i}\geq 3$.

Let us first assume $diam(G)=1+\max_{1\leq i\leq k}d_{i}$. Consider some
peripheral vertex $v$ of $G$, and let $c(v)=i$. Since $V_{i}$ is a dominating
set of $G$, $e_{G}(v)\leq 1+e_{i}(v)\leq 1+d_{i}$. In particular, we must have
$d_{i}$ is maximized and $v$ is $i$-peripheral (otherwise,
$e_{G}(v)<diam(G)$). We pick some $u\in V$ such that $d_{G}(u,v)=diam(G)$, and
let $c(u)=j$. Note that $j\neq i$ (otherwise, $d_{G}(u,v)\leq d_{i}<diam(G)$).
Let $x\in N_{G}(v)\cap V_{j}$ be arbitrary. Observe that we always have
$d_{G}(u,v)\leq 1+d_{G}(u,x)\leq 1+e_{j}(x)\leq 1+d_{j}$. As a result,
$d_{j}=d_{i}$ is maximized, and any neighbour $x$ of vertex $v$ with $c(x)=j$
is $j$-peripheral.

Conversely, suppose by contradiction this above necessary condition for having
$diam(G)=1+\max_{1\leq i\leq k}d_{i}$ is not sufficient on its own for the
absolute retracts of $k$-chromatic graphs. Without loss of generality, amongst
all the absolute retracts of $k$-chromatic graphs, $G$ is a minimum counter-
example for which the condition holds and $diam(G)=\max_{1\leq i\leq k}d_{i}$.
For some $i\neq j$ such that $d_{i}=d_{j}$ is maximized, let $v$ be a
$i$-peripheral vertex whose all neighbours coloured $j$ are $j$-peripheral,
and let $u\in N_{G}(v)$ be such that $c(u)=j$. Then,
$e_{G}(u)=d_{j}=d_{i}=diam(G)$. Observe that $u$ cannot be adjacent to all the
vertices coloured $i$ (otherwise, $d_{i}=2<3$). Therefore, by Theorem 4, $u$
is covered and $G^{\prime}=G\setminus u$ is an absolute retract of
$k$-chromatic graphs. Let
$V_{1}^{\prime},V_{2}^{\prime},\ldots,V_{k}^{\prime}$ be the colour classes of
$G^{\prime}$ (induced by the coloring $c$ restricted on $V\setminus\\{u\\}$).
Observe that for $p\neq j$ we have $V_{p}^{\prime}=V_{p}$, while
$V_{j}^{\prime}=V_{j}\setminus\\{u\\}$. Furthermore, let
$d_{1}^{\prime},d_{2}^{\prime},\ldots,d_{k}^{\prime}$ be the largest distances
between vertices in a same colour class of $G^{\prime}$. Since $G^{\prime}$ is
isometric, $d_{p}^{\prime}\leq d_{p}$ for all $p$. But, since
$V_{i}^{\prime}=V_{i}$, we get $d_{i}^{\prime}=d_{i}$, and therefore,
$\max_{p}d_{p}^{\prime}=\max_{p}d_{p}=d_{i}=diam(G)$. It implies
$diam(G^{\prime})=diam(G)=\max_{p}d_{p}^{\prime}$. By minimality of $G$, the
subgraph $G^{\prime}$ is not a counter-example. Hence, vertex $v$ must have
some neighbour $u^{\prime}\neq u$ coloured $j$ s.t.
$\max\\{d_{G}(u^{\prime},x)\mid x\in V_{j}\setminus\\{u\\}\\}\leq d_{i}-1$.
However, it implies
$e_{j}(u^{\prime})\leq\max\\{d_{G}(u^{\prime},u),d_{i}-1\\}=\max\\{2,d_{i}-1\\}=d_{i}-1$.
A contradiction. ∎

###  3.3 Computation of the $d_{i}$’s

Our strategy is as follows. First, we prove in Lemma 21 that we can reduce our
study to the case $k=3$. In Lemmas 22 and 25, respectively, we deal with the
cases $d_{i}={\cal O}(\sqrt{n})$ and $d_{i}=\Omega(\sqrt{n})$, respectively.

#### Reduction.

The next Lemma 21 allows us to reduce the general case to $k=3$.

######  Lemma 21.

Let $G=(V,E)$ be an absolute retract of $k$-chromatic graphs for some $k\geq
3$, and let $c$ be a corresponding proper $k$-coloring. For every distinct
colours $i_{1},i_{2},i_{3}$, the subgraph $H:=G[V_{i_{1}}\cup V_{i_{2}}\cup
V_{i_{3}}]$ is isometric. Moreover, $H$ is an absolute retract of
$3$-chromatic graphs.

###### Proof.

Suppose by contradiction $H$ is not isometric in $G$. Let $u,v\in V(H)$ be
such that no shortest $uv$-path of $G$ is contained in $H$, and $d_{G}(u,v)$
is minimum for this property. Since $H$ is induced, $d_{G}(u,v)>1$. But then,
let $j\in\\{i_{1},i_{2},i_{3}\\}\setminus\\{c(u),c(v)\\}$. By Theorem 5, there
is a neighbour $x$ of $v$ that is on a shortest $uv$-path of $G$ and such that
$c(x)=j$. In particular, $x\in V(H)$. Since $H$ is induced, we have $vx\in
E(H)$. However, by minimality of $d_{G}(u,v)$ we also have
$d_{H}(x,u)=d_{G}(x,u)$, and therefore $d_{H}(u,v)\leq
1+d_{H}(x,u)=1+d_{G}(x,u)=d_{G}(v,u)$. A contradiction.

Now, let us prove that $H$ is an absolute retract of $3$-chromatic graphs. For
that, it suffices to prove that $H$ satisfies the three properties stated in
Theorem 5. – Note that, since $c$ is the unique proper $k$-coloring of $G$,
the restriction of $c$ to $H$ is the unique proper $3$-coloring of this
subgraph. –

  1. 1.

Let $j\in\\{i_{1},i_{2},i_{3}\\}$ be fixed. Consider some family of balls in
$H$, denoted $N_{H}^{r_{1}}[v_{1}],N_{H}^{r_{2}}[v_{2}],\ldots,\\\
N_{H}^{r_{q}}[v_{q}]$. Let us assume these balls pairwise intersect in colour
$j$, i.e., for every $1\leq a,b\leq q$ we have $N_{H}^{r_{a}}[v_{a}]\cap
N_{H}^{r_{b}}[v_{b}]\cap V_{j}\neq\emptyset$. Since $H$ is a subgraph of $G$,
the balls
$N_{G}^{r_{1}}[v_{1}],N_{G}^{r_{2}}[v_{2}],\ldots,N_{G}^{r_{q}}[v_{q}]$ also
pairwise intersect in colour $j$ (in $G$). By Theorem 5, there exists a vertex
$z_{j}\in V_{j}\cap\left(\bigcap\\{N_{G}^{r_{a}}[v_{a}]\mid 1\leq a\leq
q\\}\right)$. Since $V_{j}\subseteq V(H)$, and $H$ is isometric in $G$, we get
$z_{j}\in V_{j}\cap\left(\bigcap\\{N_{H}^{r_{a}}[v_{a}]\mid 1\leq a\leq
q\\}\right)$.

  2. 2.

Let $K$ be a maximal clique of $H$. We have $K\subseteq K^{\prime}$ where
$K^{\prime}$ is a maximal clique of $G$. By Theorem 5, $|K^{\prime}|=k$. It
implies that every colour class intersects $K^{\prime}$. Hence,
$|K|=|K^{\prime}\cap(V_{i_{1}}\cup V_{i_{2}}\cup V_{i_{3}})|=3$.

  3. 3.

Finally, let $u,v\in V(H)$ and let $j\in\\{i_{1},i_{2},i_{3}\\}$ be such that
$c(v)\neq j$ and either $c(u)\neq j$ or $d_{H}(u,v)\geq 3$. Since $H$ is
isometric, either $c(u)\neq j$ or $d_{G}(u,v)\geq 3$. By Theorem 5, there
exists a neighbour $x$ of $v$ coloured $j$ that is on a shortest $uv$-path in
$G$. Since $x\in V(H)$ and $H$ is isometric, $x$ is also on a shortest
$uv$-path in $H$.

Overall, all three properties of Theorem 5 are satisfied by $H$. It implies
that $H$ is an absolute retract of $3$-chromatic graphs. ∎

#### Small-diameter case.

Next, we deal with the case when $d_{i}$ is sufficiently small.

######  Lemma 22.

Let $G=(V,E)$ be an absolute retract of $3$-chromatic graphs, and let $c$ be a
corresponding proper $3$-coloring. For each colour $i$ and $D\geq 2$, we can
compute in ${\cal O}(Dm)$ time the set $U_{i}:=\\{v\in V_{i}\mid e_{i}(u)\leq
D\\}$.

###### Proof.

It suffices to prove the result for $i=1$. For that, we generalize the
techniques used in Lemma 3. Specifically, for every $1\leq t\leq D$, the
objective is to compute a partition of $V_{1}$, denoted ${\cal P}_{t}$,
subject to the following property: for each colour $i$, the $|{\cal P}_{t}|$
subsets $B_{t}[A,i]:=V_{i}\cap\left(\bigcap\\{N_{G}^{t}[a]\mid a\in
A\\}\right)$, for all $A\in{\cal P}_{t}$, must be pairwise disjoint and, if
$i\neq 1$ or $t\geq 2$, these sets must also be nonempty. Being given any such
partition ${\cal P}_{D}$, we observe that $U_{1}\neq\emptyset$ if and only if
${\cal P}_{D}=(V_{1})$ and, if it is the case, then $U_{1}=B_{D}[V_{1},1]$.

The algorithm. For the base case $t=1$, let $Y:=V_{1}$. While
$Y\neq\emptyset$, we select some vertex $x\in V_{2}$ such that $|N_{G}(x)\cap
Y|$ is maximized, we add $N_{G}(x)\cap Y$ as a new group in ${\cal P}_{1}$,
then we set $Y:=Y\setminus N_{G}(x)$. Finally, we enumerate all groups
$A\in{\cal P}_{1}$, and we scan the neighbourhoods of all vertices $a\in A$ in
order to compute the sets $B_{1}[A,i]$ for each colour $i$ (note that
$B_{1}[A,1]=A$ if $|A|=1$ and $B_{1}[A,1]=\emptyset$ otherwise).

At step $t+1$, for each group $A\in{\cal P}_{t}$, let us define:

$W(A,1):=N_{G}(B_{t}[A,2])\cap V_{1},$ $W(A,2):=N_{G}(B_{t}[A,3])\cap V_{2},$
$W(A,3):=N_{G}(B_{t}[A,2])\cap V_{3}.$

Let ${\cal F}:={\cal P}_{t}$. While ${\cal F}\neq\emptyset$, we proceed as
follows. We pick some $v\in V_{1}$ such that $\\#\\{A\in{\cal F}\mid v\in
W(A,1)\\}$ is maximized. Let $A^{\prime}:=\bigcup\\{A\in{\cal F}\mid v\in
W(A,1)\\}$. We add $A^{\prime}$ to ${\cal P}_{t+1}$, for each colour $i$ we
set $B_{t+1}[A^{\prime},i]:=\bigcap\\{W(A,i)\mid A\in{\cal F},\ v\in
W(A,1)\\}$, and we set ${\cal F}:={\cal F}\setminus\\{A\in{\cal F}\mid v\in
W(A,1)\\}$.

Correctness. We first consider the base case $t=1$. Clearly, the sets
$B_{1}[A,1]$ (equal to either $A$, if it is a singleton, and to the empty set
otherwise) are pairwise disjoint. Since at every step, in order to create a
new group, we pick a vertex of $V_{2}$ with a maximum number of unselected
vertices in $V_{1}$, it follows by construction that the sets $B_{1}[A,2]$ are
nonempty. By maximality of the vertex $V_{2}$ selected at each step, it also
follows that all these sets $B_{1}[A,2]$ are pairwise disjoint (this is
exactly the same argument as the one used for Claim 2, in Lemma 3). The next
claim shows that both properties (i.e., being nonempty and pairwise disjoint)
also hold for the sets $B_{1}[A,3]$.

######  Claim 3.

For $A\subseteq V_{1}$, the neighbour-sets $N_{G}(a),\ a\in A$ intersect in
colour $2$ if and only if they intersect in colour $3$.

Proof. Let us assume the balls $N_{G}[a],\ a\in A$ intersect in colour $2$
(resp., in colour $3$). In particular, the vertices of $A$ are pairwise at
distance two. By the third property of Theorem 5, the balls $N_{G}[a],\ a\in
A$ pairwise intersect in colour $3$ (resp., in colour $2$), and therefore the
claim now follows from the first (Helly-type) property of this Theorem 5.
$\diamond$

From now on, we consider the inductive step (i.e., from $t$ to $t+1$). We need
the following claim for our analysis:

######  Claim 4.

For each colour $i$, $t\geq 1$ and $A\in{\cal P}_{t}$, we have
$W(A,i)=V_{i}\cap\left(\bigcap\\{N_{G}^{t+1}[a]\mid a\in A\mid\\}\right)$.

Proof. By construction, $W(A,i)\subseteq
V_{i}\cap\left(\bigcap\\{N_{G}^{t+1}[a]\mid a\in A\\}\right)$. Conversely, let
$u\in\bigcap\\{N_{G}^{t+1}[a]\mid a\in A\\}$ be such that $c(u)=i$. Let $j$ be
the least colour available amongst $\\{2,3\\}\setminus\\{i\\}$ (i.e., $j=2$ if
$i\neq 2$ and $j=3$ otherwise). We prove as a subclaim that, for every $a\in
A$, the balls $N_{G}^{t}[a]$ and $N_{G}[u]$ intersect in colour $j$. For that,
we need to consider three cases:

  * •

Case $u=a$. This can only happen if $i=1$. Then, $N_{G}[u]\subseteq
N_{G}^{t}[u]=N_{G}^{t}[a]$. Since $u$ has at least one neighbour coloured $j$,
the balls $N_{G}^{t}[a]$ and $N_{G}[u]$ trivially intersect in colour $j$.

  * •

Case $ua\in E$. By Theorem 5, every maximal clique of $G$ has cardinality $3$.
It implies that $u,a$ have a common neighbour coloured $j$.

  * •

Case $d_{G}(u,a)\geq 2$. By Theorem 5, there exists a neighbour $x$ of $u$ on
a shortest $au$-path such that $c(x)=j$.

Furthermore, since $B_{t}[A,j]\neq\emptyset$, the balls $N_{G}^{t}[a],\ a\in
A$, also pairwise intersect in colour $j$. By Theorem 5, there exists a $x\in
N_{G}(u)\cap B_{t}[A,j]$. In order to conclude the proof, we just need to
observe that $u\in N_{G}(B_{t}[A,j])\cap V_{i}=W(A,i)$. $\diamond$

When a new set $A^{\prime}$ is created, as the union of sets in some nonempty
family ${\cal Q}\subseteq{\cal P}_{t}$, we define for each colour $i$,
$B_{t+1}[A^{\prime},i]=\bigcap\\{W(A,i)\mid A\in{\cal Q}\\}$. By the above
Claim 4,
$B_{t+1}[A^{\prime},i]=V_{i}\cap\left(\bigcap\\{N_{G}^{t+1}[a^{\prime}]\mid
a^{\prime}\in A^{\prime}\mid\\}\right)$, as desired. It now remains to prove
that all sets $B_{t+1}[A^{\prime},i],\ A^{\prime}\in{\cal P}_{t+1}$ are
nonempty and pairwise disjoint. Observe that in order to create a new group,
we repeatedly pick a vertex $v\in V_{1}$ with a maximum number of unselected
groups $A\in{\cal P}_{t}$ such that $v\in W(A,1)$. To ensure that all groups
$A\in{\cal P}_{t}$ are eventually selected, we prove that:

######  Claim 5.

For each $t\geq 1$ and $A\in{\cal P}_{t}$, we have $W(A,1)\neq\emptyset$.

Proof. Let $x\in B_{t}[A,2]$. Since $G$ is an absolute retract, $N_{G}(x)\cap
V_{1}\neq\emptyset$. We are now done as we have by construction $N_{G}(x)\cap
V_{1}\subseteq W(A,1)$. $\diamond$

By maximality of the vertex of $V_{1}$ selected at each step, the sets
$B_{t+1}[A^{\prime},1],\ A^{\prime}\in{\cal P}_{t+1}$ are nonempty and
pairwise disjoint. Finally, the next claim shows that both properties also
hold for the sets $B_{t+1}[A^{\prime},i]$, for any colour $i$:

######  Claim 6.

For each colour $i\neq 1$, $A\subseteq V_{1}$ and $t\geq 2$, the balls
$N_{G}^{t}[a],\ a\in A$ intersect in colour $1$ if and only if they also
intersect in colour $i$.

Proof. First assume that the balls $N_{G}^{t}[a],\ a\in A$ intersect in colour
$1$. Let $a,a^{\prime}\in A$ and let $v\in N_{G}^{t}[a]\cap
N_{G}^{t}[a^{\prime}]$ such that $c(v)=1$. W.l.o.g., $a\neq v$. For
$j\in\\{2,3\\}\setminus\\{i\\}$, by Theorem 5 there exists a neighbour $x$ of
$v$ on a shortest $av$-path such that $c(x)=j$. We divide our analysis into
three cases:

  * •

Case $xa^{\prime}\notin E$. By Theorem 5, there exists a neighbour $y$ of $x$
on a shortest $xa^{\prime}$-path such that $c(y)=i$. Note that $y\in
N_{G}^{t}[a]\cap N_{G}^{t}[a^{\prime}]$.

  * •

Case $xa,xa^{\prime}\in E$. By Claim 3, the neighbour-sets $N_{G}(a),\
N_{G}(a^{\prime})$ intersect in colour $i$. Since $t\geq 2$, so do the balls
$N_{G}^{t}[a],\ N_{G}^{t}[a^{\prime}]$.

  * •

Case $xa\notin E,\ xa^{\prime}\in E$. By Theorem 5, there exists a neighbour
$y$ of $x$ on a shortest $ax$-path such that $c(y)=i$. Note that $y\in
N_{G}^{t-2}[a]\cap N_{G}^{2}[a^{\prime}]\subseteq N_{G}^{t}[a]\cap
N_{G}^{t}[a^{\prime}]$.

Overall, the balls $N_{G}^{t}[a],\ a\in A$ pairwise intersect in colour $i$,
and therefore by Theorem 5 there is a vertex coloured $i$ in their common
intersection.

Conversely, assume that the balls $N_{G}^{t}[a],\ a\in A$ intersect in colour
$i$. Let $a,a^{\prime}\in A$ and let $u\in N_{G}^{t}[a]\cap
N_{G}^{t}[a^{\prime}]$ such that $c(u)=i$. Here also, we divide our analysis
into several cases:

  * •

Case $ua,ua^{\prime}\notin E$. Let $j\in\\{2,3\\}\setminus\\{i\\}$. By Theorem
5 (applied twice) there exist $x,y\in N_{G}(u)$ that are on a shortest
$au$-path and a shortest $a^{\prime}u$-path respectively, such that
$c(x)=c(y)=j$. If $x=y$ then, any neighbour $z\in N_{G}(x)$ coloured $1$ is in
$N_{G}^{t}[a]\cap N_{G}^{t}[a^{\prime}]$. Otherwise, $d_{G}(x,y)=2$. By
Theorem 5, there is a shortest $xy$-path whose internal node $z$ has colour
$1$. Here also, $z\in N_{G}^{t}[a]\cap N_{G}^{t}[a^{\prime}]$.

  * •

Case $ua,ua^{\prime}\in E$. In this situation, $d_{G}(a,a^{\prime})=2$, and
the balls $N_{G}^{2}[a]\subseteq N_{G}^{t}[a]$ and
$N_{G}^{2}[a^{\prime}]\subseteq N_{G}^{t}[a^{\prime}]$ intersect in colour
$1$.

  * •

Case $ua\in E,\ ua^{\prime}\notin E$ (The case $ua\notin E,\ ua^{\prime}\in E$
is symmetrical to this one). If $d_{G}(a,a^{\prime})\leq t$ then, the balls
$N_{G}^{t}[a]$ and $N_{G}^{t}[a^{\prime}]$ intersect in colour $1$. Otherwise,
$d_{G}(a^{\prime},u)=t$ and $d_{G}(a,a^{\prime})=t+1$. If furthermore
$d_{G}(u,a^{\prime})=t\geq 3$ then, by Theorem 5, there exists a neighbour $x$
of $u$ on a shortest $a^{\prime}u$-path such that $c(x)=1$. In this situation,
$x\in N_{G}^{2}[a]\cap N_{G}^{t-1}[a^{\prime}]\subseteq N_{G}^{t}[a]\cap
N_{G}^{t}[a^{\prime}]$. Thus, we are left considering the special subcase
$t=2$. Let $j\in\\{2,3\\}\setminus\\{i\\}$, and let $v\in
N_{G}(a^{\prime})\cap N_{G}(u)$. Observe that we have $c(v)=j$. Furthermore,
by Theorem 5, vertices $a$ and $u$ must have a common neighbour $y$ coloured
$j$ (i.e., the third vertex in a maximal clique containing $a$ and $u$). By
construction, $d_{G}(y,v)=2$. Then, again by Theorem 5, there exists a common
neighbour $z\in N_{G}(y)\cap N_{G}(v)$ such that $c(y)=1$. In this situation,
$y\in N_{G}^{2}[a]\cap N_{G}^{2}[a^{\prime}]\subseteq N_{G}^{t}[a]\cap
N_{G}^{t}[a^{\prime}]$.

Overall, the balls $N_{G}^{t}[a],\ a\in A$ pairwise intersect in colour $1$,
and therefore by Theorem 5 there is a vertex coloured $1$ in their common
intersection. $\diamond$

Complexity. We revisit the approach taken in Lemma 3. For the base case $t=1$
we compute in ${\cal O}(m)$ time, for each vertex of $V_{2}$, its number of
neighbours in $V_{1}$. We create an array of $|V_{1}|$ lists, numbered from
$1$ to $|V_{1}|$. Each vertex $u\in V_{2}$ is put in the list numbered
$|N_{G}(u)\cap V_{1}|$. It takes ${\cal O}(n)$ time. Then, we scan the lists
in decreasing order (i.e., from $|V_{1}|$ downto $1$), going to the next list
each time the current one is empty. When the current list is nonempty, we pick
any vertex $u$ of this list in order to create the next subset $A\in{\cal
P}_{1}$. Note that $A$ can be constructed in ${\cal O}(|N_{G}(u)|)$ time.
Since each vertex $u$ gets used for the creation of at most one group
(otherwise, there would exist $A,A^{\prime}\in{\cal P}_{1}$ such that
$B_{1}[A,2]\cap B_{1}[A^{\prime},2]\neq\emptyset$), the total running time in
order to create all the groups of ${\cal P}_{1}$ is in ${\cal O}(n+m)$.
Furthermore, after a group $A$ is created, we need to actualize the number of
unselected vertices in $V_{1}$ for each $x\in V_{2}$ (discarding all such
vertices whose all neighbours in $V_{1}$ are already selected). For that, we
first scan $N_{G}(a),a\in A$ in order to update, for each $x\in V_{2}$, its
number of unselected vertices in $V_{1}$. Then, if each vertex of $V_{2}$
keeps a pointer to its position in the unique list in which it is contained,
we can update the list contents in ${\cal O}(\sum_{a\in A}|N_{G}(a)|)$ time
(maximum number of vertices of $V_{2}$ that need to be moved). Overall, this
phase also takes total ${\cal O}(n+m)$ time. Finally, since ${\cal P}_{1}$ is
a partition of $V_{1}$, for each colour $i$ we can create the sets
$B_{1}[A,i],i\in A$ in ${\cal O}(m)$ time, simply by scanning the neighbour-
sets of each vertex of $V_{1}$. In order to complete our complexity analysis,
it remains to prove that each inductive step (from $t$ to $t+1$) also requires
${\cal O}(m)$ time. For that, since by the hypothesis the sets $B_{t}[A,i],\
A\in{\cal P}_{t}$ are pairwise disjoint, we can compute the sets $W(A,i)$ in
total linear time. Then, we proceed as for the first case (see also Lemma 3),
but we now consider the vertices of $V_{1}$ rather than $V_{2}$, and for these
vertices, we keep track of the number of sets $W(A,i)$ they belong to rather
than keeping track of their degrees. We get a running time proportional to
$\sum_{A\in{\cal P}_{t}}W(A,i)={\cal O}(n+m)$. ∎

#### Large-diameter case.

Finally, we address the case when $d_{i}$ is large. For that, we start with a
simple intermediate lemma. Recall that, for every two vertices $u$ and $v$ and
any $\ell\leq d(u,v)$, we can define the slice $L(u,\ell,v):=\\{x\in
I(u,v)\mid d(u,x)=\ell\\}$.

######  Lemma 23.

Let $G=(V,E)$ be an absolute retract of $k$-chromatic graphs for some $k\geq
3$, and let $c$ be a corresponding proper $k$-coloring. For each colour $i$
and $u,v\in V_{i}$ such that $u\neq v$ and $d_{G}(u,v)\neq 3$, there exists a
$x\in L(u,2,v)$ coloured $i$.

###### Proof.

If $d_{G}(u,v)=2$ then, $x=v$. Otherwise, $d_{G}(u,v)\geq 4$. By Theorem 5,
for any $j\neq i$ there exists a neighbour $y$ of $u$ coloured $j$ on a
shortest $uv$-path. Since $d_{G}(y,v)\geq 3$, again by Theorem 5, there exists
a neighbour $x$ of $y$ coloured $i$ on a shortest $yv$-path, and so, on a
shortest $uv$-path. ∎

A function is called unimodal if every local minimum is also a global minimum.
It is known that the eccentricity function of a Helly graph is unimodal [36],
and this property got used in [40] in order to compute all the eccentricities
in this graph class in subquadratic time. Next, we prove that a similar, but
weaker property holds for each colour class of absolute retracts, namely:

######  Lemma 24.

Let $G=(V,E)$ be an absolute retract of $k$-chromatic graphs for some $k\geq
3$, and let $c$ be a corresponding proper $k$-coloring. For each colour $i$
and any $u\in V_{i}$ s.t. $e_{i}(u)\geq(d_{i}+5)/2\geq 7$, there exists a
$u^{\prime}\in V_{i}$ s.t. $d_{G}(u,u^{\prime})=2$ and
$e_{i}(u^{\prime})=e_{i}(u)-2$.

###### Proof.

Let $X_{i}=\\{x\in V_{i}\mid d_{G}(u,x)\geq 4\\}$. By Lemma 23, for every
$x\in X_{i}$, the balls $N_{G}^{2}[u]$ and $N_{G}^{e_{i}(u)-2}[x]$ intersect
in colour $i$. Furthermore, let $x,x^{\prime}\in X_{i}$ be arbitrary. If
$d_{G}(x,x^{\prime})\leq e_{i}(u)-2$ then the balls $N_{G}^{e_{i}(u)-2}[x]$
and $N_{G}^{e_{i}(u)-2}[x^{\prime}]$ intersect in colour $i$. Otherwise, let
$\ell:=d_{G}(x,x^{\prime})-(e_{i}(u)-2)$, and let $2t\in\\{\ell,\ell+1\\}$ be
even. We prove by finite induction the existence of vertices
$x_{0},x_{1},\ldots,x_{t}\in I_{G}(x,x^{\prime})$ s.t., for every $0\leq p\leq
t$, we have $d_{G}(x,x_{p})=2p$ and $c(x_{p})=i$. For the base case $p=0$, we
have $x_{0}=x$. For $0<p\leq t$, we observe that:

$\displaystyle d_{G}(x_{p-1},x^{\prime})$
$\displaystyle=d_{G}(x,x^{\prime})-2(p-1)=d_{G}(x,x^{\prime})-2p+2$
$\displaystyle\geq d_{G}(x,x^{\prime})-2t+2\geq
d_{G}(x,x^{\prime})-(\ell+1)+2$
$\displaystyle=d_{G}(x,x^{\prime})-\ell+1=e_{i}(u)-1>3.$

Then, the existence of $x_{p}$ follows from Lemma 23 (applied to the pair
$x_{p-1},x^{\prime}$). Furthermore,

$\displaystyle 2t$ $\displaystyle\leq\ell+1=d_{G}(x,x^{\prime})-e_{i}(u)+3\leq
d_{i}-e_{i}(u)+3$ $\displaystyle\leq
d_{i}-(d_{i}+5)/2+3=(d_{i}+1)/2=(d_{i}+5)/2-2$ $\displaystyle\leq e_{i}(u)-2.$

Thus, in this situation, $x_{2t}\in N_{G}^{e_{i}(u)-2}[x]\cap
N_{G}^{e_{i}(u)-2}[x^{\prime}]$. Overall, we obtain that the balls
$N_{G}^{2}[u]$ and $N_{G}^{e_{i}(u)-2}[x],\ x\in X_{i}$ pairwise intersect in
colour $i$. By Theorem 5, there exists a $u^{\prime}\in
N_{G}^{2}[u]\cap\left(\bigcap\\{N_{G}^{e_{i}(u)-2}[x]\mid x\in
X_{i}\\}\right)$ such that $c(u^{\prime})=i$. Note that $u^{\prime}\neq u$
because there must be a $x\in X_{i}$ s.t. $d_{G}(u,x)=e_{i}(u)\geq 4$. We
obtain that $d_{G}(u,u^{\prime})=2$ and that, for every $x\in V_{i}\setminus
X_{i}$ we have $d_{G}(u^{\prime},x)\leq 2+d_{G}(u,x)\leq 5$. As a result,
$e_{i}(u^{\prime})\leq\max\\{5,e_{i}(u)-2\\}=e_{i}(u)-2$. Since
$d_{G}(u,u^{\prime})=2$, this must be an equality. ∎

We end up applying this almost-unimodality property to the computation of the
$d_{i}$’s (assuming these values to be at least in $\Omega(\sqrt{n})$):

######  Lemma 25.

Let $G=(V,E)$ be an absolute retract of $k$-chromatic graphs for some $k\geq
3$, let $c$ be a corresponding proper $k$-coloring, and let $i$ be such that
$d_{i}\geq 8D+5=\omega(\log{n})$. Then, with high probability, we can compute
in total $\tilde{\cal O}(mn/D)$ time the value $d_{i}$ and the $i$-peripheral
vertices.

###### Proof.

We modify Algorithm 1 as follows.

The algorithm. We set $p=\alpha\frac{\log{n}}{D}$, for some sufficiently large
constant $\alpha$. Then, let $U_{i}(p)$ contain every $v\in V_{i}$
independently with probability $p$. For all $v\in V_{i}$, let
$\bar{e}_{i}(v):=\min\\{d_{G}(u,v)+e_{i}(u)\mid u\in U_{i}(p),d_{G}(u,v)\leq
D\\}$ (with the understanding that, if no vertex of $U_{i}(p)$ is at a
distance $\leq D$ from $v$, then $\bar{e}_{i}(v)=0$). We output
$d_{i}=\max\\{\bar{e}_{i}(v)\mid v\in V_{i}\\}$, and we identify as
$i$-peripheral all vertices $v\in V_{i}$ such that $\bar{e}_{i}(v)$ is
maximized.

Complexity. Since we have to perform a breadth-first search from every vertex
of $U_{i}(p)$, the running time of the algorithm is in ${\cal
O}(m|U_{i}(p)|)$. Let us prove that with high probability,
$|U_{i}(p)|=\tilde{\cal O}(n/D)$. First note that we have $\mathbb{E}\left[\
|U_{i}(p)|\ \right]=\tilde{\Theta}(|V_{i}|/D)$. We claim to have
$|V_{i}|=\Omega(D)$. In order to see that, consider $x,y\in V_{i}$ s.t.
$d_{G}(x,y)=d_{i}$. Recall that $d_{i}=\Omega(D)$. Thus, by applying Lemma 23
$\Omega(D)$ times, we get the existence of a shortest $xy$-path with
$\Omega(D)$ vertices coloured $i$. The latter proves, as claimed,
$|V_{i}|=\Omega(D)$. Then, $\mathbb{E}\left[\ |U_{i}(p)|\
\right]=\Omega(\log{n})$. By Chernoff bounds, we have $|U_{i}(p)|=\tilde{\cal
O}(|V_{i}|/D)=\tilde{\cal O}(n/D)$ with high probability.

Correctness. Let $v\in V_{i}$ be arbitrary. We divide our analysis into two
cases.

  * •

Case $e_{i}(v)<(d_{i}+5)/2+2D$. For any $u\in U_{i}(p)$ s.t. $d_{G}(u,v)\leq
D$, $e_{i}(u)<(d_{i}+5)/2+3D$. Therefore,
$\bar{e}_{i}(v)<(d_{i}+5)/2+4D=d_{i}/2+(8D+5)/2\leq d_{i}$.

  * •

Case $e_{i}(v)\geq(d_{i}+5)/2+2D$. In particular, we always fall in this case
if $v$ is $i$-peripheral. Then, by applying Lemma 24 $D$ times, we get the
existence of vertices $x_{0}=v,x_{1},x_{2},\ldots,x_{D}$ such that, for every
$j>0$, $d_{G}(x_{j-1},x_{j})=2$ and $e_{i}(x_{j})=e_{i}(x_{j-1})-2$. Observe
that we have $d_{G}(v,x_{j})\leq 2j$ and $e_{i}(x_{j})=e_{i}(v)-2j$, and
therefore $d_{G}(v,x_{j})=2j$. It implies that, if $x_{j}\in U_{i}(p)$ for
some $j$, $\bar{e}_{i}(v)=e_{i}(v)$. Let us prove this happens with high
probability. Indeed:

$\displaystyle\mathbb{P}r[U_{i}(p)\cap\\{x_{0},x_{1},\ldots,x_{D}\\}=\emptyset]<(1-p)^{D}=(1-p)^{\frac{\alpha\log{n}}{p}}\leq
n^{-\alpha}.$

Summarizing both cases above, for all $i$-peripheral vertices $v$ we have
$\bar{e}_{i}(v)=e_{i}(v)=d_{i}$, whereas for every $v\in V_{i}$ that is not
$i$-peripheral, $\bar{e}_{i}(v)<d_{i}$. ∎

###  3.4 Main result

We end up gathering all previous results in this section, in order to prove
the following:

######  Theorem 6.

If $G=(V,E)$ is an absolute retract of $k$-chromatic graphs, for some $k\geq
3$, then we can compute its diameter with high probability in $\tilde{\cal
O}(m\sqrt{n})$ time.

###### Proof.

We may assume $diam(G)>1$ (trivial case). By Corollary 2, we can decide in
linear time whether $diam(G)\leq 2$. Thus, from now on, let us assume
$diam(G)\geq 3$. We compute a proper $k$-coloring of $G$, that takes linear-
time according to Proposition 2. Then, by Lemma 20, we can compute $diam(G)$
in linear time if, for each colour $i$, we are given $d_{i}$ and the
corresponding $i$-peripheral vertices. In order to compute this information,
let $V_{1},V_{2},\ldots,V_{k}$ be the colour classes. Up to repeating $V_{1}$
($=V_{k+1}$) and $V_{2}$ ($=V_{k+2}$) at most once we may assume the number of
colour to be a multiple of three, and then we partition the colour classes in
disjoint triples $V_{i}\cup V_{i+1}\cup V_{i+2}$. By Lemma 21, each subgraph
$H_{i}:=G[V_{i}\cup V_{i+1}\cup V_{i+2}]$ is isometric in $G$ and is an
absolute retract of $3$-chromatic graphs. Therefore, we may restrict ourselves
to $H_{i}$ in order to compute the values $d_{i},d_{i+1},d_{i+2}$. Let
$n_{i}:=|V(H_{i})|$ and $m_{i}:=|E(H_{i})|$. By construction,
$\sum_{i}n_{i}=\Theta(n)$ and $\sum_{i}m_{i}=\Theta(m)$. Hence, if for each
$i$ our computations require $\tilde{\cal O}(m_{i}\sqrt{n_{i}})$ time, the
total running time is in $\tilde{\cal O}(m\sqrt{n})$. Let us prove it is the
case for $H_{1}$ (and so, by symmetry, for every $i$). Since there are only
three colour classes in $H_{1}$, it is sufficient to prove that we can compute
$d_{1}$ and all the $1$-peripheral vertices in $\tilde{\cal
O}(m_{1}\sqrt{n_{1}})$ time. For that, we first compute $D:=e_{1}(v)$ for some
arbitrary $v\in V_{1}$. It takes ${\cal O}(m_{1})$ time and, by the triangular
inequality, it is a $2$-approximation of $d_{1}$. There are now two cases. If
$D\leq 16\sqrt{n_{1}}+10$ then, we compute by one-sided binary search the
smallest $t$ such that $\forall v\in V_{1},\ e_{1}(v)\leq t$, that is exactly
$d_{1}$. Note that at each step of the binary search we apply Lemma 22, that
results in a running time in $\tilde{\cal O}(m_{1}d_{1})=\tilde{\cal
O}(m_{1}D)=\tilde{\cal O}(m_{1}\sqrt{n_{1}})$. Furthermore, we can compute all
the $1$-peripheral vertices within the same amount of time, simply with one
more call to Lemma 22 (for $d_{1}-1$). Otherwise, $d_{1}\geq D/2\geq
8\sqrt{n_{1}}+5$, and we apply Lemma 4. With high probability, the running
time is in $\tilde{\cal O}(m_{1}\sqrt{n_{1}})$. ∎

##  4 Split graphs

The graphs studied in the two previous Sec. 2 and 3 are exactly the absolute
retracts of the class of all (irreflexive) graphs. In this section, we show
that by considering the absolute retracts of more restricted graph classes, we
may derive negative results about faster diameter computation. Specifically,
$G=(V,E)$ is a split graph if its vertex-set $V$ can be partitioned into a
clique $K$ and a stable set $S$. In what follows, we always denote such a
bipartition by $K+S$. We also use the standard notations $\omega(G)$ and
$\alpha(G)$ for, respectively, the clique number (maximum cardinality of a
clique) and the independence number (maximum cardinality of a stable set) of
$G$.

Let us recall the following hardness result about the diameter problem on
split graphs:

######  Lemma 26 ([15]).

For any $\epsilon>0$, there exists a $c(\epsilon)$ s.t., under SETH, we cannot
compute the diameter in ${\cal O}(n^{2-\epsilon})$ time on the split graphs of
order $n$ and clique-number at most $c(\epsilon)\log{n}$.

Our main result in this section is that this above hardness result also holds
for the absolute retracts of split graphs (Theorem 8). For that, we need a few
preparatory lemmas, namely:

######  Lemma 27 ([57]).

Let $G=(K+S,E)$ be a split graph. Exactly one of the following conditions
holds:

  1. 1.

$|K|=\omega(G)$ and $|S|=\alpha(G)$ (in this case the partition $K+S$ is
unique);

  2. 2.

$|K|=\omega(G)-1$ and $|S|=\alpha(G)$ (in this case there exists an $y\in S$
s.t. $K+\\{y\\}$ is complete);

  3. 3.

$|K|=\omega(G)$ and $|S|=\alpha(G)-1$ (in this case there exists an $x\in K$
s.t. $S+\\{x\\}$ is stable).

Recall that $G=(V,E)$ is a complete split graph if there exists a partition of
its vertex-set into a clique $K$ and a stable set $S$ s.t. every vertex of $S$
is adjacent to every vertex of $K$. In particular, a complete split graph has
diameter at most two.

######  Theorem 7 ([66]).

A split graph is an absolute retract of split graphs if and only if it is a
complete split graph or it has a unique partition of its vertex-set into a
clique and a stable set.

We are now ready to prove the main result of this section, namely:

######  Theorem 8.

There is a linear-time reduction from the diameter problem on split graphs to
the same problem on the absolute retracts of split graphs.

In particular, for any $\epsilon>0$, there exists a $c(\epsilon)$ s.t., under
SETH, we cannot compute the diameter in ${\cal O}(n^{2-\epsilon})$ time on the
absolute retracts of split graphs of order $n$ and clique-number at most
$c(\epsilon)\log{n}$.

###### Proof.

Let $G=(V,E)$ be a split graph. First, we check in linear time whether
$diam(G)=0$ (i.e., $G$ is a singleton) or $diam(G)=1$ (i.e., $G$ is a complete
graph). From now on, let us assume $diam(G)\geq 2$. Since $G$ is a split
graph, computing the diameter is equivalent to deciding whether $diam(G)=3$.
For that, we compute a partition of $V$ into a clique $K$ and a stable set
$S$. It can be done in linear time [57]. For every vertex $v$, let
$deg(v):=|N(v)|$. We apply the following pruning rules until no more vertex
can be removed:

  * •

If there exists a $x\in K$ s.t. $deg(x)=|K|-1$, then we remove $x$ from $G$.

  * •

If there exists a $y\in S$ s.t. $deg(y)=|K|$, then we remove $y$ from $G$.

Complexity. Let us explain how both rules above can be applied exhaustively in
total linear time. For that, we maintain an array of $n-1$ lists, numbered
from $1$ to $n-1$, so that each vertex of $S$ of degree $i$ must be contained
into the $i^{th}$ such list. We proceed similarly for the vertices of $K$ (but
in a separate array of lists). Note that such a data structure can be
initialized in linear time, simply by computing the degree sequence of the
graph. If we further store, for each vertex, a pointer to its position in the
unique list in which it is contained, then every time we remove a vertex $v$,
we can update the structure in a time proportional to $deg(v)$. The latter
results in a total update time in ${\cal O}(m)$. Finally, if at each step we
maintain the cardinality $|K|$ of the clique $K$, then in order to check
whether one of the two pruning rules applies, we are left testing whether at
most two lists of our data structure are nonempty.

Correctness. In order to prove correctness of these above pruning rules, let
us first define a super-simplicial vertex as any vertex $v$ s.t.
$N(v)=K\setminus\\{v\\}$. Note that if $x\in K$ is s.t. $deg(x)=|K|-1$ then,
$N(x)=K\setminus\\{x\\}$, and so, $x$ is super-simplicial. In the same way if
$y\in S$ is s.t. $deg(y)=|K|$ then, $N(y)=K$, and so, $y$ is super-simplicial.
Summarizing the above, we can only prune super-simplicial vertices. Now, we
claim that, for a split graph $G$ and a super-simplicial vertex $v$ of $G$, we
have $diam(G)=3$ if and only if $diam(G\setminus\\{v\\})=3$. Indeed, since
$G\setminus\\{v\\}$ is an isometric subgraph of $G$,
$diam(G\setminus\\{v\\})=3$ implies $diam(G)\geq 3$, hence (since $G$ is a
split graph) $diam(G)=3$. Conversely, if $diam(G)=3$ then, there exist
$y,y^{\prime}\in S$ s.t. $d(y,y^{\prime})=3$. In order to prove that
$diam(G\setminus\\{v\\})=3$, it suffices to prove that none of $y$ and
$y^{\prime}$ can be a super-simplicial vertex. That is indeed the case
because, since $K$ is a dominating set of $G$, any super-simplicial vertex has
eccentricity at most two.

Finally, let $G^{\prime}$ be the resulting subgraph after no more vertex can
be removed. Observe that we have reduced the computation of $diam(G)$ to the
computation of $diam(G^{\prime})$. We shall prove that there exists a unique
partition of $V(G^{\prime})$ into a clique $K^{\prime}$ and a stable set
$S^{\prime}$. By Theorem 7, this will imply that $G^{\prime}$ is an absolute
retract of split graphs. Let $K^{\prime}$ and $S^{\prime}$ be a partition of
$V(G^{\prime})$ into a clique and a stable set, and suppose for the sake of
contradiction this partition is not unique. By Lemma 27, either there exists
$y\in S^{\prime}$ s.t. $K^{\prime}+\\{y\\}$ is complete, or there exists $x\in
K^{\prime}$ s.t. $S^{\prime}+\\{x\\}$ is a stable set. In the former case,
$deg(y)=|K^{\prime}|$, while in the latter case, $deg(x)=|K^{\prime}|-1$. But
then, we could still have applied one of our two pruning rules above, a
contradiction. ∎

##  5 Planar graphs

Our last (non-algorithmic) section is about the absolute retracts of planar
graphs The latter have been characterized in [61], assuming the Four-color
conjecture. Since this is now a theorem [3], the characterization of absolute
retracts of planar graphs is complete:

######  Theorem 9 ([61]).

A planar graph $G$ is an absolute retract of planar graphs if and only if it
is maximal planar and, in an embedding of $G$ in the plane, any triangle
bounding a face of $G$ belongs to a subgraph of $G$ isomorphic to $K_{4}$.

To our best knowledge, there has been no relation uncovered between the
absolute retracts of planar graphs and other important planar graph
subclasses. We make a first step in this direction. Specifically, the
Apollonian networks are a subclass of planar graphs that can be defined
recursively, as follows. The triangle $K_{3}$ is an Apollonian network. If $G$
is an Apollonian network, and $f$ a triangular face in a plane embedding of
$G$, then the graph $G^{\prime}$, obtained by adding a new vertex adjacent to
the three ends of $f$, is also an Apollonian network. The Apollonian networks
of order at least four (all Apollonian networks but the triangle) have some
important alternative characterizations, namely they are exactly the maximal
planar chordal graphs of order at least four [71], the planar $3$-trees [13],
and the uniquely $4$-colorable planar graphs [54].

######  Proposition 4.

Every Apollonian network with at least four vertices is an absolute retract of
planar graphs.

###### Proof.

Let $G$ be an Apollonian network of order at least four. In particular, $G$ is
maximal planar. Consider any triangular face $f$ in a plane embedding of $G$.
We also have that $G$ is a $3$-tree, and so, all its maximal cliques have four
vertices. In particular, there exists a vertex adjacent to all three vertices
of $f$. By Theorem 9, $G$ is an absolute retract of planar graphs. ∎

However, this above inclusion is strict (e.g., see Fig. 1 for a counter-
example). Indeed, our main result in this section is as follows:

Figure 1: An absolute planar retract of treewidth $\geq 5$.

######  Theorem 10.

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

###### Proof.

Let $G=(V,E)$ be a connected planar graph. The result is trivial if $|V|\leq
2$. From now on, we assume $|V|\geq 3$. We first prove the existence of a
biconnected planar graph $H_{1}$ in which $G$ isometrically embeds. If $G$ is
already biconnected, then we set $H_{1}:=G$. Otherwise, let $u$ be a cut-
vertex of $G$. In any fixed planar embedding of $G$, consider a clock-wise
ordering of $N_{G}(u)$. There must be two consecutive neighbours $x,y$ in
different connected components of $G\setminus u$. We add a new vertex $z\notin
V$ such that $N(z)=\\{u,x,y\\}$. Since $x,y$ are consecutive in the clock-wise
ordering of $N_{G}(u)$, the resulting graph $G^{\prime}:=G+u$ is still planar.
It is also easy to check that $G$ isometrically embeds in $G^{\prime}$ because
$u,x,y$ are pairwise at distance at most two in $G$. Overall, by iterating
this above operation, we obtain the desired biconnected planar graph $H_{1}$
in which $G$ isometrically embeds.

Note that because $H_{1}$ is biconnected, in any plane embedding of $H_{1}$,
the boundary of each face is a simple cycle [35, Proposition 4.2.6]. Then, we
claim that $H_{1}$ is an isometric subgraph of some planar $H_{2}$ such that,
in some plane embedding of $H_{2}$ all the faces have length at most five. In
order to prove the claim, fix a plane embedding of $H_{1}$ and let the simple
cycle $C$ be the boundary of some face of length $\geq 6$ (if no such face
exists then, we are done by setting $H_{2}:=H_{1}$). Pick some path $[u,v,w]$
of length two on the cycle $C$. Let $C^{\prime}$ be obtained from $C$ by
contracting $[u,v,w]$ to a single vertex $x$. We add a copy of $C^{\prime}$ in
the face of which $C$ is a boundary, we add an edge between $x$ and all of
$u,v,w$, and finally we add an edge between every $y\in C\setminus\\{u,v,w\\}$
and its copy in $C^{\prime}$. Note that doing so, we replace the face bounded
by $C$ by a new face bounded by $C^{\prime}$ and by some new triangular and
quadrangular faces. Let $H_{1}^{\prime}$ be the resulting planar graph. We
prove as an intermediate subclaim that $H_{1}$ isometrically embeds in
$H_{1}^{\prime}$. For that, fix a shortest-path in $H_{1}^{\prime}$ between
some two vertices $a,b\in V(H_{1})$. Assume there is a subpath
$P^{\prime}=[c_{1}^{\prime},\ldots,c_{p}^{\prime}]$ fully in $C^{\prime}$
(otherwise, we are done). There is a natural mapping between the latter and
the path $P$ of $C$ that is obtained by uncontracting the path $[u,v,w]$. Note
that the length of $P$ is at most the length of $P^{\prime}$ plus two.
Furthermore, let $x,y\in C$ be the respective neighbours of
$c_{1}^{\prime},c_{p}^{\prime}$ on the shortest $ab$-path. By construction,
$x,y\in V(P)$. Hence, we may replace $[x,P^{\prime},y]$ by $P$ on the shortest
$ab$-path. By repeating this operation until there is no more vertex of
$C^{\prime}$ on the shortest $ab$-path, we prove as claimed that $H_{1}$
isometrically embeds in $H_{1}^{\prime}$. Overall, we repeat the above
operations until there is no more face of length $\geq 6$ in the plane
embedding. Doing so, we obtain $H_{2}$.

We further claim that $H_{2}$ is an isometric subgraph of some plane
triangulation $H_{3}$. This is easily achieved by adding, in the middle of
each face, a new vertex adjacent to all the vertices of the boundary. Note
that $H_{2}$ isometrically embeds in $H_{3}$ because all its faces have length
at most five, and so, weak diameter at most two.

Finally, let us prove that every plane triangulation $H_{3}$ isometrically
embeds in some absolute planar retract $H_{4}$. The construction is the same
as in the previous step, namely, we add in the middle of each (triangular)
face a new vertex adjacent to all the vertices of the boundary. Doing so,
since each face of $H_{4}$ shares exactly one edge with a triangular face of
$H_{3}$, we satisfy the following property: any triangle bounding a face of
$H_{4}$ belongs to a subgraph isomorphic to $K_{4}$. Furthermore, $H_{4}$ is a
plane triangulation of order $\geq|V|\geq 3$, and so, it is maximal planar
[35, Propositions 4.2.8 and 4.4.1]. By Theorem 9, $H_{4}$ is an absolute
planar retract. ∎

We stress that the proof of Theorem 10 is constructive, and that it leads to a
polynomial-time algorithm in order to construct an absolute planar retract in
which the input planar graph $G$ isometrically embeds. In contrast to our
result, the smallest Helly graph in which a graph $G$ isometrically embeds may
be exponential in its size [59].

## References

  * [1] A. Abboud, V. Vassilevska Williams, and J. R. Wang.  Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs.  pages 377–391. SIAM, 2016.
  * [2] R. Albert, H. Jeong, and A.-L. Barabási.  Diameter of the world-wide web.  nature, 401(6749):130–131, 1999.
  * [3] K. Appel and W. Haken.  Every planar map is four colorable.  Bulletin of the American mathematical Society, 82(5):711–712, 1976\.
  * [4] H.-J. Bandelt.  Retracts of hypercubes.  Journal of graph theory, 8(4):501–510, 1984.
  * [5] H.-J. Bandelt and V. Chepoi.  Metric graph theory and geometry: a survey.  Contemporary Mathematics, 453:49–86, 2008.
  * [6] H.-J. Bandelt, A. Dählmann, and H. Schütte.  Absolute retracts of bipartite graphs.  Discrete Applied Mathematics, 16(3):191–215, 1987.
  * [7] H.-J. Bandelt, M. Farber, and P. Hell.  Absolute reflexive retracts and absolute bipartite retracts.  Discrete Applied Mathematics, 44(1-3):9–20, 1993.
  * [8] H.-J. Bandelt and E. Pesch.  Dismantling absolute retracts of reflexive graphs.  European Journal of Combinatorics, 10(3):211–220, 1989.
  * [9] H.-J. Bandelt and E. Pesch.  A Radon theorem for Helly graphs.  Archiv der Mathematik, 52(1):95–98, 1989.
  * [10] H.-J. Bandelt and E. Pesch.  Efficient characterizations of $n$-chromatic absolute retracts.  Journal of Combinatorial Theory, Series B, 53(1):5–31, 1991.
  * [11] H.-J. Bandelt and E. Prisner.  Clique graphs and Helly graphs.  Journal of Combinatorial Theory, Series B, 51(1):34–45, 1991.
  * [12] C. Beeri, R. Fagin, D. Maier, and M. Yannakakis.  On the desirability of acyclic database schemes.  Journal of the ACM (JACM), 30(3):479–513, 1983.
  * [13] T. Biedl and L. Vélàzquez.  Drawing planar $3$-trees with given face areas.  Computational Geometry, 46(3):276–285, 2013.
  * [14] J. A. Bondy and U. S. R. Murty.  Graph theory, volume 244 of Graduate Texts in Mathematics.  Springer-Verlag London, 2008.
  * [15] 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\.
  * [16] M. Borassi, P. Crescenzi, and L. Trevisan.  An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 920–939. SIAM, 2017.
  * [17] N. Bousquet and S. Thomassé.  VC-dimension and Erdős–Pósa property.  Discrete Mathematics, 338(12):2302–2317, 2015.
  * [18] A. Brandstädt.  Classes of bipartite graphs related to chordal graphs.  Discrete Applied Mathematics, 32(1):51–60, 1991.
  * [19] A. Brandstädt, F. Dragan, V. Chepoi, and V. Voloshin.  Dually chordal graphs.  SIAM Journal on Discrete Mathematics, 11(3):437–455, 1998.
  * [20] K. Bringmann, T. Husfeldt, and M. Magnusson.  Multivariate Analysis of Orthogonal Range Searching and Graph Distances.  Algorithmica, pages 1–24, 2020.
  * [21] P. Buneman.  A characterisation of rigid circuit graphs.  Discrete Mathematics, 9(3):205–212, 1974.
  * [22] S. Cabello.  Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs.  ACM Transactions on Algorithms (TALG), 15(2):1–38, 2018.
  * [23] J. Chalopin, V. Chepoi, A. Genevois, H. Hirai, and D. Osajda.  Helly groups.  Technical Report arXiv:2002.06895, arXiv, 2020.
  * [24] G. Chang and G. Nemhauser.  The $k$-domination and $k$-stability problems on sun-free chordal graphs.  SIAM Journal on Algebraic Discrete Methods, 5(3):332–345, 1984\.
  * [25] 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.
  * [26] V. Chepoi.  On distances in benzenoid systems.  Journal of chemical information and computer sciences, 36(6):1169–1172, 1996.
  * [27] V. Chepoi and F. Dragan.  A linear-time algorithm for finding a central vertex of a chordal graph.  In ESA, pages 159–170. Springer, 1994.
  * [28] V. Chepoi, F. Dragan, B. Estellon, M. Habib, and Y. Vaxès.  Diameters, centers, and approximating trees of $\delta$-hyperbolic geodesic spaces and graphs.  In Symposium on Computational Geometry (SocG), pages 59–68. ACM, 2008.
  * [29] V. Chepoi, F. Dragan, and Y. Vaxès.  Center and diameter problems in plane triangulations and quadrangulations.  In Symposium on Discrete Algorithms (SODA’02), pages 346–355, 2002\.
  * [30] V. Chepoi, B. Estellon, and Y. Vaxès.  Covering planar graphs with a fixed number of balls.  Discrete & Computational Geometry, 37(2):237–244, 2007.
  * [31] D. Corneil, F. Dragan, M. Habib, and C. Paul.  Diameter determination on restricted graph families.  Discrete Applied Mathematics, 113(2-3):143–166, 2001.
  * [32] D. Coudert, G. Ducoffe, and A. Popa.  Fully polynomial FPT algorithms for some classes of bounded clique-width graphs.  ACM Transactions on Algorithms (TALG), 15(3):1–57, 2019.
  * [33] P. Damaschke.  Computing giant graph diameters.  In International Workshop on Combinatorial Algorithms (IWOCA), pages 373–384. Springer, 2016.
  * [34] J. De Rumeur.  Communications dans les réseaux de processeurs.  Masson Paris, 1994.
  * [35] R. Diestel.  Graph Theory.  Graduate Texts in Mathematics. Springer, 2010.  $4th$ edition.
  * [36] F. Dragan.  Centers of graphs and the Helly property.  PhD thesis, Moldova State University, 1989.
  * [37] F. Dragan.  Domination in quadrangle-free Helly graphs.  Cybernetics and Systems Analysis, 29(6):822–829, 1993.
  * [38] F. Dragan.  Almost diameter of a house-hole-free graph in linear time via LexBFS.  Discrete applied mathematics, 95(1-3):223–239, 1999.
  * [39] F. Dragan and A. Brandstädt.  r-dominating cliques in graphs with hypertree structure.  Discrete Mathematics, 162(1-3):93–108, 1996.
  * [40] F. Dragan, G. Ducoffe, and H. Guarnera.  Fast deterministic algorithms for computing all eccentricities in (hyperbolic) helly graphs.  Manuscript in preparation.
  * [41] F. Dragan and H. Guarnera.  Obstructions to a small hyperbolicity in Helly graphs.  Discrete Mathematics, 342(2):326 – 338, 2019.
  * [42] F. Dragan and H. Guarnera.  Helly-gap of a graph and vertex eccentricities.  Technical Report arXiv:2005.01921, arXiv, 2020.
  * [43] F. Dragan and V. Voloshin.  Incidence graphs of biacyclic hypergraphs.  Discrete Applied Mathematics, 68(3):259–266, 1996.
  * [44] 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.
  * [45] G. Ducoffe.  A New Application of Orthogonal Range Searching for Computing Giant Graph Diameters.  In Symposium on Simplicity in Algorithms (SOSA), 2019.
  * [46] G. Ducoffe.  Distance problems within Helly graphs and $k$-Helly graphs.  Technical Report arXiv:2011.00001, arXiv preprint, 2020.
  * [47] G. Ducoffe.  Optimal diameter computation within bounded clique-width graphs.  Technical Report arXiv:2011.08448, arXiv, 2020.
  * [48] G. Ducoffe and F. Dragan.  A story of diameter, radius and Helly property.  2020\.  To appear in Networks.
  * [49] G. Ducoffe, M. Habib, and L. Viennot.  Fast diameter computation within split graphs.  In International Conference on Combinatorial Optimization and Applications, pages 155–167. Springer, 2019.
  * [50] G. Ducoffe, M. Habib, and L. Viennot.  Diameter computation on $H$-minor free graphs and graphs of bounded (distance) VC-dimension.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1905–1922. SIAM, 2020.
  * [51] D. Eppstein.  Subgraph isomorphism in planar graphs and related problems.  pages 283–309, 2002.
  * [52] M. Farber.  Characterizations of strongly chordal graphs.  Discrete Mathematics, 43(2-3):173–189, 1983.
  * [53] A. Farley and A. Proskurowski.  Computation of the center and diameter of outerplanar graphs.  Discrete Applied Mathematics, 2(3):185–191, 1980.
  * [54] T. Fowler.  Unique Coloring of Planar Graphs.  PhD thesis, Georgia Institute of Technology, Mathematics Department, 1998\.
  * [55] F. Gavril.  The intersection graphs of subtrees in trees are exactly the chordal graphs.  Journal of Combinatorial Theory, Series B, 16(1):47–56, 1974.
  * [56] 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 Symposium on Discrete Algorithms (SODA), pages 495–514. SIAM, 2018.
  * [57] M. Golumbic.  Algorithmic graph theory and perfect graphs, volume 57.  Elsevier, 2004.
  * [58] M. Golumbic and C. Goss.  Perfect elimination and chordal bipartite graphs.  Journal of Graph Theory, 2(2):155–163, 1978.
  * [59] H. Guarnera, F. Dragan, and A. Leitert.  Injective hulls of various graph classes.  Technical Report arXiv:2007.14377, arXiv, 2020.
  * [60] P. Hell.  Rétractions de graphes.  PhD thesis, Thèse (Ph. D.: Mathématiques)–Université de Montréal. 1972., 1972.
  * [61] P. Hell.  Absolute planar retracts and the four color conjecture.  Journal of Combinatorial Theory, Series B, 17(1):5–10, 1974.
  * [62] P. Hell.  Absolute retracts in graphs.  In Graphs and Combinatorics, pages 291–301. Springer, 1974.
  * [63] P. Hell and I. Rival.  Absolute retracts and varieties of reflexive graphs.  Canadian journal of mathematics, 39(3):544–567, 1987.
  * [64] J. Isbell.  Six theorems about injective metric spaces.  Commentarii Mathematici Helvetici, 39(1):65–76, 1964.
  * [65] D. S. Johnson and M. R. Garey.  Computers and intractability: A guide to the theory of NP-completeness.  WH Freeman, 1979.
  * [66] S. Klavžar.  Absolute retracts of split graphs.  Discrete Mathematics, 134(1-3):75–84, 1994.
  * [67] J. Klisowski.  A survey of various modifications of the notions of absolute retracts and absolute neighborhood retracts.  In Colloquium Mathematicum, volume 46, pages 23–35. Institute of Mathematics Polish Academy of Sciences, 1982.
  * [68] T. Kloks and Y.-L. Wang.  On retracts, absolute retracts, and foldings in cographs.  Optimization Letters, 12(3):535–549, 2018.
  * [69] M. Lin and J. Szwarcfiter.  Faster recognition of clique-Helly and hereditary clique-Helly graphs.  Information Processing Letters, 103(1):40–43, 2007.
  * [70] C. Loten.  Absolute retracts and varieties generated by chordal graphs.  Discrete mathematics, 310(10-11):1507–1519, 2010.
  * [71] L. Markenzon, C. M. Justel, and N. Paciornik.  Subclasses of $k$-trees: Characterization and recognition.  Discrete Applied Mathematics, 154(5):818–825, 2006.
  * [72] J. Matousek.  Bounded VC-dimension implies a fractional Helly theorem.  Discrete & Computational Geometry, 31(2):251–255, 2004.
  * [73] 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.
  * [74] E. Pesch.  Minimal extensions of graphs to absolute retracts.  Journal of graph theory, 11(4):585–598, 1987.
  * [75] E. Pesch.  Products of absolute retracts.  Discrete mathematics, 69(2):179–188, 1988.
  * [76] E. Pesch and W. Poguntke.  A characterization of absolute retracts of $n$-chromatic graphs.  Discrete mathematics, 57(1-2):99–104, 1985.
  * [77] N. Polat.  Convexity and fixed-point properties in Helly graphs.  Discrete Mathematics, 229(1-3):197–211, 2001.
  * [78] N. Polat.  On constructible graphs, locally Helly graphs, and convexity.  Journal of Graph Theory, 43(4):280–298, 2003.
  * [79] L. Roditty and V. Vassilevska Williams.  Fast approximation algorithms for the diameter and radius of sparse graphs.  In Proceedings of the forty-fifth annual ACM symposium on Theory of computing (STOC), pages 515–524, 2013.
  * [80] R. Tarjan and M. Yannakakis.  Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs.  SIAM Journal on computing, 13(3):566–579, 1984.
  * [81] J. R. Walter.  Representations of rigid cycle graphs.  PhD thesis, Wayne State University, Department of Mathematics, 1972.
  * [82] D. Watts and S. Strogatz.  Collective dynamics of ‘small-world’ networks.  Nature, 393(6684):440–442, 1998.