# Leanness Computation: Small Values and Special Graph Classes

David Coudert, Samuel Coulomb, Guillaume Ducoffe

► To cite this version:

David Coudert, Samuel Coulomb, Guillaume Ducoffe. Leanness Computation: Small Values and Special Graph Classes. Discrete Mathematics and Theoretical Computer Science, 2024, 26 (2), pp.22. 10.46298/dmtcs.12544 . hal-04281128v3

HAL Id: hal-04281128

https://hal.science/hal-04281128v3

Submitted on 3 Jul 2024

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Leanness Computation: Small Values and Special Graph Classes

David Coudert<fnref n="1" />* Samuel Coulomb<fnref n="2" /> Guillaume Ducoffe<fnref n="3" />†

revisions 13th Nov. 2023, 31st May 2024; accepted 3rd June 2024.

Let $u$ and $v$ be vertices in a connected graph $G = (V, E)$. For any integer $k$ such that $0 \le k \le |d_G(u, v)|$, the $k$-slice $S_k(u, v)$ contains all vertices $x$ on a shortest $uv$-path such that $|d_G(u, x) - k| = k$. The leanness of $G$ is the maximum diameter of a slice. This metric graph invariant has been studied under different names, such as „interval thinness” and „fellow traveler property”. Graphs with leanness equal to 0, a.k.a. *geodetic graphs*, also have received special attention in Graph Theory. The practical computation of leanness in real-life complex networks has been studied recently (Mohammed et al., *COMPLEX NETWORKS*’21). In this paper, we give a finer-grained complexity analysis of two related problems, namely: deciding whether the leanness of a graph $G$ is at most some small value $\ell$; and computing the leanness on specific graph classes. We obtain improved algorithms in some cases, and time complexity lower bounds under plausible hypotheses.

**Keywords:** Leanness; Geodetic graphs; SETH-based lower bounds; Graph algorithms.

## 1 Introduction

The graph parameter *Leanness*, which is the main topic of this work, arises from Metric and Geometric Graph Theory Bandelt and Chepoi (2008). For undefined graph terminology, see Bondy and Murty (2008). Unless stated otherwise, all graphs considered are finite, simple (they have neither loops nor multiple edges), undirected, unweighted and connected. Roughly, the leanness of a graph $G$ is the smallest integer $\ell$ such that, for every source vertex $s$ and every destination vertex $t$, two same-speed travelers on shortest $st$-paths always stay at distance at most $\ell$ to each other. See Sec. 2 for a formal definition of leanness, and for the required graph notations and terminology for this work. In what follows, let $\lambda(G)$ denote the leanness of a given graph $G$.

<footnote n="1">¹ Université Côte d'Azur, CNRS, Inria, I3S, Sophia Antipolis, France</footnote>

<footnote n="2">² École Normale Supérieure, Paris, France</footnote>

<footnote n="3">³ National Institute for Research and Development in Informatics & University of Bucharest, București, România</footnote>

<footnote>*This work was supported by the French government, through the UCAJEDI Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-15-IDEX-01.</footnote>

<footnote>†This work was supported by a grant of the Romanian Ministry of Research, Innovation and Digitalization, CCCDI - UEFISCDI, project number PN-III-P2-2.1-PED-2021-2142, within PNCDI III.</footnote>
**Related work.** To our best knowledge, leanness of graphs has been first studied in Group Theory, under the insightful name of fellow traveler property Epstein (1992). Although the word problem is notoriously undecidable for general groups Novikov (1955), it was shown in Epstein (1992) that it can be solved in quadratic time on so-called automatic groups. A beautiful combinatorial characterization of automatic groups is given in Epstein (1992), which implies their (infinite) Cayley graph satisfies the fellow traveler property (i.e., it has bounded leanness).

Hyperbolicity is a metric tree-likeness parameter, first introduced by Gromov Gromov (1987), which for graphs is tightly related to leanness. A metric space $(X, d)$ is called $\delta$-hyperbolic if it satisfies the following four-point condition for every $u, v, x, y \in X$: the two largest distance-sums amongst

$$d(u, v) + d(x, y), d(u, x) + d(v, y) \text{ and } d(u, y) + d(v, x)$$

must differ by at most $2\delta$. The hyperbolicity of $(X, d)$ is the infimum of all values $\delta$ such that $(X, d)$ is $\delta$-hyperbolic. For a graph $G$, we denote by $\delta(G)$ its hyperbolicity. The value $\delta(G)$ is a lower bound on the smallest additive distortion for embedding $G$ into an edge-weighted tree Gromov (1987), with both values differing by at most some logarithmic factor Chepoi et al. (2008); Gromov (1987). Moreover, there is empirical evidence that some complex networks have very small hyperbolicity Kennedy et al. (2016). In this respect, it has been argued in Kennedy et al. (2016) that hyperbolicity helps in better classifying complex networks, while it also explains some of their observed properties Chepoi et al. (2017).

On one hand, it can be easily verified from the definition that $\lambda(G) \le 2\delta(G)$ for every graph $G$. Therefore, bounded hyperbolicity implies bounded leanness$^{(i)}$. However, on the other hand, cycles $C_{4n+3}$ satisfy $\lambda(C_{4n+3}) = 0$ whereas $\delta(C_{4n+3}) = n$. Papasoglu proved a deeper relationship between hyperbolicity and leanness in geodesic metric spaces Papasoglu (1995), which can be restated as follows for graphs: let $H$ be the graph obtained from a graph $G$ by subdividing once every edge; there exists a doubly-exponential function $f$ such that, if the leanness of $H$ is at most $\ell$, then $G$ must be $f(\ell)$-hyperbolic. In particular, even though the hyperbolicity of $G$ can be arbitrarily larger than its leanness, the hyperbolicity of $G$ and the leanness of $H$ are functionally equivalent. Even more strongly, the authors in Mohammed et al. (2021) reported that all real-life networks $G$ from Cohen et al. (2015) satisfy $\lambda(G) = 2\delta(G)$. In the same way, it follows from (Chepoi et al., 2008, Proposition 10) that in modular graphs, pseudo-modular graphs and their respective subclasses, the leanness and the hyperbolicity can only differ by some small constant factor. For example, it was proved in Dragan and Guarnera (2019) that $\lambda(G) \le 2\delta(G) \le \lambda(G) + 1$ for every Helly graph $G$ (a particular case of pseudo-modular graphs). Helly graphs are one of the most studied classes of graphs in Metric Graph Theory Bandelt and Chepoi (2008), due to their connections with hyperconvex metric spaces.

According to Mohammed et al. (2021), computing the leanness of a graph is a good heuristic for computing its hyperbolicity (and it always outputs a lower bound on the real value). However, while there has been substantial work toward practical hyperbolicity computation Borassi et al. (2015); Cohen et al. (2017, 2015); Coudert et al. (2022a,b), comparatively little has been done for leanness computation. In Mohammed et al. (2021), an algorithm in $O(n^2m)$ time and $O(n^2)$ space was proposed. We are not aware of any previous studies on the leanness in some graph classes (for such studies on the hyperbolicity, see Brinkmann et al. (2001); Chepoi et al. (2008); Dragan and Guarnera (2019); Koolen and Moulton (2002); Wu and Zhang (2011)).

<footnote>(i) We note that leanness is often called interval thinness in prior works on hyperbolicity.</footnote>
Graphs with leanness equal to zero are exactly the graphs such that there exists only one shortest path between every two vertices. They have been studied on their own under the different name of geodetic graphs Ore (1962). Different constructions of geodetic graphs have been proposed in the literature Plesník (1977). Since their introduction by Ore in 1962, it has been asked repeatedly for a full characterization of these graphs. An algebraic characterization was proved in Nebeský (1998). Combinatorial characterizations are known only for restricted subclasses, such as planar geodetic graphs Stemple and Watkins (1968). Recently, Bodwin characterized the path systems that can be realized as unique shortest paths in a graph with arbitrary real edge weights Bodwin (2019).

**Our Contributions.** We address the complexity of computing the leanness of a graph, under two natural restrictions. First, in Sec. 3, we consider the recognition of graphs with leanness at most some constant $\ell$. It is folklore that geodetic graphs can be recognized in polynomial time, by using a variation of breadth-first search (BFS). We present a different $\mathcal{O}(n^\omega)$-time algorithm for this problem, where $\omega < 2.371552$ Vassilevska Williams et al. (2024) denotes the exponent for square matrix multiplication$^{(ii)}$. By doing so, we improve the state of the art. The existence of an almost linear-time algorithm remains an open problem. We complement this result with conditional quadratic-time lower bounds for the recognition of graphs with leanness at most one (at most two, resp.).

Sec. 4, 5, 6 are devoted to the computation of leanness in restricted graph classes. Different types of grids are analyzed in Sec. 4, partly because of their relationship to hyperbolicity in subclasses of weakly modular graphs Chalopin et al. (2020); Dragan and Guarnera (2019). Other subclasses of planar graphs are considered in Sec. 5, namely outerplanar and bicyclic graphs. Finally, in Sec. 6, we study the cographs, chordal graphs, distance-hereditary graphs and bisplit graphs. As already noted in Mohammed et al. (2021), the leanness is bounded on all these classes. We prove that the leanness can be computed in linear time on all these classes, except for bisplit graphs. Furthermore, under the Strong Exponential-Time Hypothesis (SETH) Impagliazzo and Paturi (2001), there is no subquadratic-time algorithm for computing the leanness of bisplit graphs.

## 2 Definitions and notations

We now introduce the required notations and terminology for this paper. Recall that we only consider finite, undirected, unweighted and connected graphs. The graph $G = (V, E)$ has $n = |V|$ vertices and $m = |E|$ edges. We denote $N(u)$ the set of neighbors of vertex $u \in V$. Given two vertices $u, v \in V$, a *uv-path* of length $\ell \ge 0$ is a sequence of pairwise different vertices $(u = v_0, v_1, \ldots, v_\ell = v)$ such that $\{v_i, v_{i+1}\} \in E$ for every $i$. The *distance* $d(u, v)$ is the minimum length of a *uv-path* in $G$. The *eccentricity* ecc$(u)$ is the maximum distance between vertex $u$ and any other vertex $v \in V$, i.e., ecc$(u) = \max_{v \in V} d(u, v)$. The *diameter* diam$(G)$ is the maximum eccentricity of the graph, i.e., $\text{diam}(G) = \max_{u \in V} \text{ecc}(u)$.

For a pair $(x, y)$ of vertices of $G$, the interval $I(x, y)$ is the set of vertices that lay on any shortest $xy$-path, i.e., $I(x, y) = \{u \in V : d(x, y) = d(x, u) + d(u, y)\}$. An interval can be divided into a set of *slices* $S_k(x, y)$, $k = 0, 1, \ldots$, $d(x, y)$, such that $S_k(x, y) = \{u \in I(x, y) : d(x, u) = k\}$. We observe that the slices of an interval $I(x, y)$ can be constructed in time $\mathcal{O}(n)$ if the distance matrix of the graph is given, or in time $\mathcal{O}(n+m)$ otherwise. The diameter $\text{diam}(S_k(x, y))$ of a slice is defined

<footnote>(ii) The $\tilde{\mathcal{O}}(\cdot)$ notation suppresses polylogarithmic factors.</footnote>
as $\max_{u,v \in S_k(x,y)} d(u, v)$. Let $\lambda(x, y) = \max_{0 \le k \le d(x,y)} \text{diam}(S_k(x, y))$. We call the interval $I(x, y)$
$\ell$-lean if and only if $\lambda(x, y) \le \ell$ (see Fig. 1 for an illustration).

**Definition 1.** The leanness $\lambda(G)$ of a graph $G = (V, E)$ is defined as

$$
\lambda(G) = \max_{x,y \in V} \lambda(x,y).
$$

<figure><img src="image_2.png" /><figcaption>**Fig. 1:** An $\ell$-lean interval.</figcaption></figure>

Roughly, the leanness of a graph measures the maximum distance between two shortest paths with
same end-vertices. Clearly, we have $0 \le \lambda(G) \le \text{diam}(G)$ for every graph $G$. These bounds are sharp.
In particular, $\lambda(G) = 0$ if and only if there exists a unique shortest path between every two vertices of $G$.
Graphs with leanness equal to zero are called *geodetic graphs*. Examples of geodetic graphs are cliques,
trees and odd cycles.

Let $x, y$ be two vertices on different biconnected components of $G$. Then, all shortest $xy$-paths must cross some cut-vertex $z$. In this situation, every slice of interval $I(x, y)$ must be a slice of $I(x, z)$, or a slice of $I(z, y)$. Therefore, $\lambda(x, y) = \max\{\lambda(x, z), \lambda(z, y)\}$. See Fig. 2 for an illustration. It follows from this observation that $\lambda(G)$ always equals the maximum leanness of its biconnected components. Furthermore, computing the biconnected components of a graph $G$ can be done in linear time Hopcroft and Tarjan (1973). As a result, we can always assume in what follows that the graphs considered are biconnected.

<figure><img src="image_3.png" /><figcaption>Fig. 2: A cut-vertex *z* inside some interval *I*(*x*, *y*).</figcaption></figure>

A vertex pair $(x, y)$ is called a *far-apart pair* if and only if for every vertex $z$, we have $d(x, z) < d(x, y) + d(y, z)$, and similarly $d(y, z) < d(y, x) + d(x, z)$. The following observation will be often used in our analyzes:

**Lemma 1.** For every graph $G = (V, E)$, there exists a far-apart pair $(x, y)$ s.t. $\lambda(G) = \lambda(x, y)$.

**Proof:** Let $(x, y) \in V^2$ be such that $\lambda(G) = \lambda(x, y)$ and $d(x, y)$ is maximized. Suppose by contradiction that $(x, y)$ is not far-apart. By symmetry, we may assume the existence of some vertex $z$ such that
$d(x, z) = d(x, y) + d(y, z)$. Then, every slice of $I(x, y)$ is also a slice of $I(x, z)$, and so, $\lambda(x, y) \le \lambda(x, z)$. However, since $d(x, z) > d(x, y)$, the latter contradicts the maximality of $d(x, y)$. $\square$

The leanness of a graph $G$ can be computed in $O(n^4)$ time and $O(n^2)$ space as follows: we precompute the distance matrix of $G$, then we iterate over all 4-tuples of vertices. A dynamic programming algorithm is presented in Mohammed et al. (2021), that decreases the running time to $O(n^2m)$. In what follows, we give a finer-grained complexity analysis for the recognition of graphs with small leanness, and for the computation of leanness in special graph classes.

# 3 Recognition of graphs with small leanness

In this section, we address the recognition of graphs with leanness at most two. A new algorithm is presented for deciding whether a graph is geodetic (Sec. 3.1). In Sec. 3.2, we prove conditional time complexity lower bounds for the recognition of graphs with leanness at most one (at most two, resp.).

## 3.1 Geodetic graphs

It is folklore that geodetic graphs can be recognized in polynomial time as follows:

* We consider each vertex $u$ sequentially, and we compute a BFS with start vertex $u$. By doing so, we computed the distances $d(u, v)$, for every vertex $v$. Then, if $d(u, v) > 1$, we check whether there exists a unique neighbour $w \in N(v)$ such that $d(u, w) = d(u, v) - 1$.

We summarize this discussion as follows:

**Theorem 2.** *There is a combinatorial $O(nm)$-time algorithm for deciding whether a graph is geodetic.*

Clearly, $O(nm) = O(n^3)$ for any graph. We now present a different algorithm that runs in $\tilde{O}(n^\omega)$ time, where $\omega < 2.371552$ Vassilevska Williams et al. (2024) stands for the exponent of square matrix multiplication.

**Theorem 3.** *There is an $\tilde{O}(n^\omega)$-time algorithm for deciding whether a graph is geodetic.*

**Proof:** We start pre-computing the distance matrix of $G$. This can be done in time $\tilde{O}(n^\omega)$ by using Seidel's algorithm Seidel (1995). The remaining steps of our algorithms, presented next, can be regarded as an adaptation of Seidel's algorithm to leanness computation.

First, we check all vertex pairs $(u, v)$ such that $d(u, v)$ is a power of two. For that, we consider each power $2^i$, for $i = 1, 2, \dots, \lfloor \log n \rfloor$, sequentially. Let $A_i$ be the $(n \times n)$-dimensional matrix such that $A_i[x, y] = 1$ if and only if $d(x, y) = 2^{i-1}$, and $A_i[x, y] = 0$ otherwise. – We note that $A_1$ is just the usual adjacency matrix of $G$. – Let $B_i = (A_i)^2$. If there exists some pair $(u, v)$ such that $d(u, v) = 2^i$ and $B_i[u, v] > 1$, then we reject. Indeed, we claim that in this situation $G$ is not geodetic. This is because $B_i[u, v] > 1$ implies the existence of two vertices $w, w' \in S_{2^{i-1}}(u, v)$, where $S_{2^{i-1}}(u, v) = \{x \in I(u, v) : d(u, x) = 2^{i-1}\}$ is a slice of the interval $I(u, v)$, and so, of two shortest uv-paths.

Conversely, we claim that if we never reject during this phase, then there exists a unique shortest uv-path for every pair $(u, v)$ such that $d(u, v)$ is a power of two. Indeed, suppose by contradiction the existence of a pair $(u, v)$ such that $d(u, v) = 2^i$ and there exist two shortest uv-paths. Without loss of generality, exponent $i$ is minimized. Since we assume $B_i[u, v] = 1$, there exists a unique $w \in S_{2^{i-1}}(u, v)$. But then, let $k$ be such that $0 < k < 2^i$ and $|S_k(u, v)| > 1$. Note that $k \neq 2^{i-1}$. Therefore, either $k < 2^{i-1}$ and
there exist two shortest *uw*-paths, or $k > 2^{i-1}$ and there exist two shortest *wv*-paths. In either case, the latter contradicts the minimality of exponent *i* since we have $d(u, w) = d(w, v) = 2^{i-1}$.

Second, we again consider each power $2^i$, for $i = 1, 2, \dots, \lfloor \log n \rfloor$, sequentially. Then, we consider all pairs $(u, v)$ such that $d(u, v) = (2j + 1)2^{i-1}$, for some integer $j \ge 1$. These are exactly the pairs $(u, v)$ such that $2^{i-1}$ divides $d(u, v)$ but $2^i$ does not divide $d(u, v)$. If there exists such a pair $(u, v)$ such that $|S_{2^{i-1}}(u, v)| > 1$, then $G$ is not geodetic, and so, we reject. Otherwise (no such a pair exists for every $i$), we accept. This above condition, for every $i$, can be verified as follows:

1. Let $G_i$ be the graph whose adjacency matrix equals $A_i$. – In particular, $G_1 = G$. – Note that $G_i$ is a priori not connected. All connected components of $G_i$ must be considered separately.

2. We compute all distances in $G_i$ by using Seidel's algorithm. In what follows, let $d_i(u, v)$ denote the distance between two vertices that are in a same connected component of $G_i$. Note that if $d(u, v) = (2j + 1)2^{i-1}$, then $d_i(u, v) = 2j + 1$. Furthermore, all shortest *uv*-paths of $G_i$ are subsets of shortest *uv*-paths of $G$ (the latter might be false for other pairs $(u', v')$ such that $2^{i-1}$ does not divide $d(u', v')$).

3. For $r = 0, 1, 2$, let $C_{i,r}$ be the $(n \times n)$-dimensional matrix such that $C_{i,r}[x, y] = 1$ if and only if $x, y$ are in a same connected component of $G_i$ and $d_i(x, y) = r \pmod 3$, otherwise $C_{i,r}[x, y] = 0$. We show next that it is sufficient to compute the three matrix products $A_i C_{i,r}$ in order to verify the condition. Specifically, for every pair $(u, v)$ such that $d(u, v) = (2j + 1)2^{i-1}$, we claim that $|S_{2^{i-1}}(u, v)| > 1$ if and only if, for the unique $r \in \{0, 1, 2\}$ such that $2j = r \pmod 3$, we have $(A_i C_{i,r})[u, v] > 1$. This is because the vertices of $S_{2^{i-1}}(u, v)$ are exactly the neighbours of $u$ in $G_i$ that lie on some shortest *uv*-path. These are exactly the neighbours $w$ of $u$ in $G_i$ s.t. $d_i(w, v) = d_i(u, v) - 1 = 2j \pmod 3$.

At each step $i$, we call Seidel's algorithm once, and compute $O(1)$ matrix products. Since there are $\tilde{O}(1)$ steps, the running time of the algorithm is in $\tilde{O}(n^\omega)$.

Finally, let us prove correctness of this algorithm. Suppose by contradiction the existence of two shortest *uv*-paths, for some pair $(u, v)$. Recall that $d(u, v)$ cannot be a power of two. Therefore, $d(u, v) = (2j + 1)2^{i-1}$, for some $i, j \ge 1$. Without loss of generality, exponent $i$ is maximized. There exists a unique $w \in S_{2^{i-1}}(u, v)$ because otherwise we would have rejected during the second phase of the algorithm. Furthermore, since $d(u, w) = 2^{i-1}$, there exists a unique shortest *uw*-path. This implies the existence of two shortest *wv*-path, and $d(w, v) = 2^i j$ is not a power of two. But then, $2^i j = (2t + 1)2^{i+s-1}$, for some $s, t \ge 1$, thus contradicting the maximality of exponent $i$. $\square$

The existence of an almost linear-time algorithm is left as an intriguing open question.

## 3.2 Time complexity lower bounds

We were unsuccessful in establishing lower bounds for the recognition of geodetic graphs. However, in what follows, we do prove conditional lower bounds for the recognition of graphs with leanness at most one (at most two, resp.).

Let $\mathcal{H} = (X, R)$ be a 3-uniform hypergraph (i.e., $R \subseteq \binom{V}{3}$). A 4-hyperclique in $\mathcal{H}$ is a vertex subset $X = \{x_1, x_2, x_3, x_4\}$ such that every 3-subset of $X$ is a hyperedge. The so-called 3-uniform
4-hyperclique hypothesis posits that detecting a 4-hyperclique in a 3-uniform hypergraph of $n$ nodes requires $n^{4-o(1)}$ time Lincoln et al. (2018). Evidence for this conjecture is that its refutation would imply faster algorithms for well-studied problems such as MAX-3-SAT Williams (2005).

**Proposition 4.** *Under the 3-uniform 4-hyperclique hypothesis, the recognition of $n$-vertex graphs $G$ s.t. $\lambda(G) \le 1$ requires $\Omega(n^{2-o(1)})$ time. The result holds even if $G$ has $O(n^{3/2})$ edges.*

**Proof:** It was proved in Dalirrooyfard and Vassilevska Williams (2022) that detecting an induced $C_4$ in an $n$-vertex $O(n^{3/2})$-edge graph $G$ requires $\Omega(n^{2-o(1)})$ time under the 3-uniform 4-hyperclique hypothesis. Let $G'$ be obtained from $G$ by adding a universal vertex. Then, $\lambda(G') \le 1$ if and only if $G$ is $C_4$-free. $\square$

The **STRONG EXPONENTIAL-TIME HYPOTHESIS (SETH)** posits that for every $\varepsilon > 0$, there exists some integer $k$ such that $k$-SAT cannot be solved in $(2 - \varepsilon)^n$ time Impagliazzo and Paturi (2001). SETH-based lower bounds have gained momentum in the nascent field of „Fine-Grained Complexity in P”. These conditional lower bounds are often achieved via an intermediate problem called **DISJOINTSET**. In the latter problem, we are given two families of $n$ sets and the goal is to determine whether there exists two disjoint sets, with one set in each family. Under the SETH, it was proved in Borassi et al. (2016); Williams (2005) that **DISJOINTSET** requires $\Omega(n^{2-o(1)})$ time, even if the universe of both families only contains $n^{o(1)}$ elements. We will come back to the SETH in Sec. 6.4.

**Proposition 5.** *Under the SETH, the recognition of $n$-vertex graphs $G$ s.t. $\lambda(G) \le 2$ requires $\Omega(n^{2-o(1)})$ time. The result holds even if $G$ has $n^{1+o(1)}$ edges.*

**Proof:** Under the SETH, deciding whether an $n$-vertex graph $G = (V, E)$ has diameter two or three requires $\Omega(n^{2-o(1)})$ time, even if $G$ only has $n^{1+o(1)}$ edges (such a graph can be constructed from any instance of **DISJOINTSET**) Borassi et al. (2016). Let $G'$ be constructed from $G$ as follows:

* The vertex set of $G'$ is $V \cup V_x \cup V_y \cup \{x, y, z\}$ where $V_x, V_y$ are disjoint copies of $V$;

* $N(x) = V_x, N(y) = V_y$, and $N(z) = V_x \cup V_y$;

* $V_x$ and $V_y$ are independent sets;

* $G'[V] = G$;

* finally, for every $v \in V$, we add two edges $\{v_x, v\}$, $\{v, v_y\}$.

Note that we can construct $G'$ from $G$ in $n^{1+o(1)}$ time. Furthermore, it was proved in (Borassi et al., 2016, Sec. 3.3) that $\delta(G') = \text{diam}(G)/2$, where $\delta(G')$ denotes the hyperbolicity of $G'$ (see Sec. 1). Recall that $\lambda(G') \le 2\delta(G')$, and so, $\lambda(G') \le \text{diam}(G)$. This is in fact an equality because $V \subseteq S_2(x, y)$ and $G$ is an isometric sugraph of $G'$. As a result, $\lambda(G') \le 2$ iff $\text{diam}(G) = 2$, which, under SETH, requires $\Omega(n^{2-o(1)})$ time to decide. $\square$

# 4 Grid variants

In this section, we establish closed-form formulas for the leanness of different types of grids. We refer to Fig. 3, 4, 5, 7 for illustrations. We stress that grids often appear as an obstruction to small hyperbolicity or leanness in various graph classes. For example, it follows from (Chalopin et al., 2020, Proposition 9.10) that for median graphs $G$, $\lambda(G) \le 2\ell$ if and only if every isometric square grid of $G$ has side at most $\ell$.
## Square grids

The $p \times q$ grid is the graph $G = (V, E)$, where $V = \llbracket 0, p-1 \rrbracket \times \llbracket 0, q-1 \rrbracket$ and $E = \{(u, v) \in V^2 : |u_1 - v_1| + |u_2 - v_2| = 1\}$. The distance between two vertices $u$ and $v$ is the Manhattan distance $d(u, v) = |u_1 - v_1| + |u_2 - v_2|$.

<figure><img src="image_4.png" /><figcaption>Fig. 3: The 4 × 5 grid.</figcaption></figure>

**Proposition 6.** The $p \times q$ grid $G$ has leanness $\lambda(G) = 2 \min\{p, q\} - 2$.

**Proof:** Without loss of generality, suppose $p \le q$. The only far-apart pairs are the two pairs of opposite corners $\{x, y\} = \{(0, 0), (p-1, q-1)\}$ and $\{x', y'\} = \{(0, q-1), (p-1, 0)\}$. By Lemma 1, $\lambda(G) = \max\{\lambda(x, y), \lambda(x', y')\}$. Because of symmetry, they both have the same leanness, so we just need to find the leanness of one of them, say $\{x, y\}$. Let $k$ be such that $0 \le k \le p+q-2$.

$$S_k(x, y) = \{(i, j) \in V : i + j = k\} = \{(i, k - i) : 0 \le i < p, 0 \le k - i < q\}$$

Let $u = (i, k - i)$ and $v = (j, k - j)$ be two vertices in the slice $S_k(x, y)$.

$$d(u, v) = |j - i| + |k - i - (k - j)| = 2|j - i| \le 2(p - 1)$$

Hence, $\lambda(G) \le 2(p-1)$. Then, taking $u = (p-1, 0)$ and $v = (0, p-1)$, we do have $u, v \in S_k(x, y)$ and $d(u, v) = 2(p-1)$, so $\lambda(G) \ge 2(p-1)$. Thus, we have proven that $\lambda(G) = 2(p-1)$. $\square$

## Cylinder grids

The cylinder grid of size $p \times q$ is given by connecting the two sides of size $p$ from the $p \times q$ grid. Formally, it means adding the edges $\{(k, 0), (k, q-1)\} : 0 \le k < p\}$. It can also be seen as replacing $\llbracket 0, q-1 \rrbracket$ with $\mathbb{Z}/q\mathbb{Z}$.

**Proposition 7.** The $p \times q$ cylinder grid has leanness

$$\lambda = \begin{cases} \min\{2(p-1), q-1\} & \text{if } q \text{ is odd} \\ \min\{q, 2\left\lfloor \frac{2(p-1)+q}{4} \right\rfloor\} & \text{if } q \text{ is even} \end{cases}$$
**Proof:** By Lemma 1 we only need to consider far-apart pairs. It was proved in (Coudert and Ducoffe, 2016, Lemma 55) that the set of far-apart pairs is $\{(0, i), (p-1, j)\} : 0 \le i, j < q, j - i \equiv \pm \lfloor \frac{q}{2} \rfloor \pmod q\}$. Because of symmetry, we may only look at one of them, say $\{x, y\} = \{(0, 0), (p-1, \lfloor \frac{q}{2} \rfloor)\}$.

If $q$ is odd, then the graph induced by $I(x, y)$ is the $p \times \frac{q+1}{2}$ grid. By Proposition 6, we get $\lambda(G) = \min\{2p, q+1\} - 2 = \min\{2(p-1), q-1\}$.

If $q$ is even, then the graph induced by $I(x, y)$ is the whole graph $G$. Furthermore, $G$ is bipartite. Then, any two vertices in a same slice will always be in the same partite set, and therefore the distance between such vertices must be even. As the diameter of $G$ is $p-1+\frac{q}{2}$, we obtain that $\lambda(G) \le 2\lfloor \frac{p-1+q/2}{2} \rfloor$.

Let $u = (u_1, u_2)$ and $v = (v_1, v_2)$ be two vertices on a same slice $S_k(x, y)$. Note that $k = d(x, u) = u_1 + \min\{u_2, q - u_2\} \le u_1 + \frac{q}{2}$. In particular, $k - \frac{q}{2} \le u_1 \le k$. Hence,

$$d(u, v) = |u_1 - v_1| + \max\{|u_2 - v_2|, q - |u_2 - v_2|\} \le |u_1 - v_1| + q/2 \le q.$$

Altogether combined, we obtain $\lambda(G) \le \min\{q, 2\lfloor \frac{p-1+q/2}{2} \rfloor\}$.

We end up proving the above is always an equality. If $\frac{q}{2} \le p-1$, then $u = (\frac{q}{2}, 0)$ and $v = (0, \frac{q}{2})$ are in $S_{q/2}(x, y)$, and $d(u, v) = q$. Else, $p-1 \le r = \lfloor \frac{p-1+q/2}{2} \rfloor \le \frac{q}{2}$, vertices $u = (0, q-r)$ and $v = (p-1, r-p+1)$ are in $S_r(x, y)$, and $d(u, v) = 2r$. $\square$

## Torus grids

The torus grid of size $p \times q$ is obtained from the $p \times q$ cylinder grid by adding all edges in $\{(0, k), (p-1, k)\} : 0 \le k < q\}$.

<figure><img src="image_5.png" /><figcaption>Fig. 4: A torus grid.</figcaption></figure>

**Proposition 8.** The $p \times q$ torus grid has leanness

$$\lambda = \begin{cases} \min\{p, q\} - 1 & \text{if } p \text{ and } q \text{ are odd} \\ \min\{q, 2\lfloor \frac{p+q}{4} \rfloor\} & \text{if } p \text{ is odd and } q \text{ is even} \\ \min\{p, 2\lfloor \frac{p+q}{4} \rfloor\} & \text{if } p \text{ is even and } q \text{ is odd} \\ 2\lfloor \frac{p+q}{4} \rfloor & \text{if } p \text{ and } q \text{ are even} \end{cases}$$
**Proof:** A pair $\{(i, j), (k, l)\}$ is far-apart if and only if $k - i \equiv \pm \lfloor \frac{p}{2} \rfloor \pmod{p}$ and $l - j \equiv \pm \lfloor \frac{q}{2} \rfloor \pmod{q}$. By Lemma 1, it is enough to find the leanness of one of these pairs, say the pair $\{x, y\} = \{(0, 0), (\lfloor \frac{p}{2} \rfloor, \lfloor \frac{q}{2} \rfloor)\}$.

If $p$ and $q$ are odd, then the graph induced by $I(x, y)$ is the $\frac{p+1}{2} \times \frac{q+1}{2}$ grid. By Proposition 6, $\lambda(G) = \min\{p+1, q+1\} - 2 = \min\{p, q\} - 1$.

If $p$ is odd and $q$ is even, then the graph induced by $I(x, y)$ is the $\frac{p+1}{2} \times q$ cylinder grid. By Proposition 7, $\lambda(G) = \min\{q, 2\lfloor \frac{p+q-1}{4} \rfloor\}$. Note that $\lfloor \frac{p+q-1}{4} \rfloor = \lfloor \frac{p+q}{4} \rfloor$ because $p+q$ is odd. The case when $p$ is even and $q$ is odd is dealt with similarly.

Finally, assume both $p$ and $q$ are even. Then, $\text{diam}(G) = (p+q)/2$. Furthermore, $G$ is bipartite. Since every slice of $I(x, y)$ must be fully contained in one partite set, the diameter of each slice must be even. Hence $\lambda(G)$ must be even, and so, $\lambda(G) \le 2\lfloor \frac{p+q}{4} \rfloor$. Without loss of generality we assume from now on $p \le q$. Let $u = (0, q - \lfloor \frac{p+q}{4} \rfloor)$ and $v = (\frac{p}{2}, \lfloor \frac{p+q}{4} \rfloor - \frac{p}{2})$. Observe that $u, v \in S_{\lfloor \frac{p+q}{4} \rfloor}(x, y)$. Therefore, $\lambda(G) \ge \lambda(x, y) \ge \text{d}(u, v) = 2\lfloor \frac{p+q}{4} \rfloor$. $\square$

## King's grids

The King's grid of size $p \times q$ is obtained from the $p \times q$ grid by adding both diagonals in every square, i.e., by adding all edges in $\{(i, j), (i+1, j+1)\} : 0 \le i < p-1, 0 \le j < q-1\} \cup \{(i, j), (i-1, j+1)\} : 0 < i < p, 0 \le j < q-1\}$. It is an example of Helly graph.

<figure><img src="image_6.png" /><figcaption>Fig. 5: A King's grid.</figcaption></figure>

**Proposition 9.** The $p \times q$ King's grid has leanness $\lambda = \begin{cases} p-2 & \text{if } p=q \text{ are even} \\ \min\{p, q\}-1 & \text{otherwise} \end{cases}$

**Proof:** Recall the definition of hyperbolicity in Sec. 1. We denote $\delta(G)$ the hyperbolicity of the King's grid $G$ of size $p \times q$. By (Dragan and Guarnera, 2019, Theorem 2), we have $2\delta(G) - 1 \le \lambda(G) \le 2\delta(G)$. Furthermore, if $\lambda(G) = 2\delta(G) - 1$, then necessarily $\delta(G)$ is an integer and $G$ contains an isometric $H_3^{\delta(G)-1}$ (see Dragan and Guarnera (2019) and Figure 6 for the definition of the graphs $H_1^k, H_2^k$ and $H_3^k$).

Without loss of generality, $p \le q$. We first consider the case $p < q$. There are two subcases, depending on the parity of $p$:

* Subcase $p$ is even. The maximum $k$ s.t. $G$ contains an isometric $H_1^k$ ($H_2^k$ and $H_3^k$, resp.) are $k = \frac{p}{2} - 1$ ($k = \frac{p}{2} - 1$ and $k = \frac{p}{2} - 2$, resp.). By (Dragan and Guarnera, 2019, Theorem 3), we obtain $\delta(G) = \frac{p-1}{2}$. Since $\delta(G)$ is not an integer, we get $\lambda(G) = 2\delta(G) = p-1$.
<figure><img src="image_7.png" /><figcaption>**Fig. 6:** The graphs $H_1^k$, $H_2^k$ and $H_3^k$ from Dragan and Guarnera (2019). They isometrically embed in the King's grids of respective sizes $(2k+1) \times (2k+1)$, $(2k+2) \times (2k+3)$ and $(2k+4) \times (2k+4)$.</figcaption></figure>

* Subcase $p$ is odd. The maximum $k$ s.t. $G$ contains an isometric $H_1^k$ ($H_2^k$ and $H_3^k$, resp.) are $k = \frac{p-1}{2}$ ($k = \frac{p-1}{2} - 1$ and $k = \frac{p-1}{2} - 2$, resp.). By (Dragan and Guarnera, 2019, Theorem 3), we obtain $\delta(G) = \frac{p-1}{2}$. Since $G$ does not contain an isometric $H_3^{\frac{p-1}{2}-1}$, we get $\lambda(G) = 2\delta(G) = p-1$.

Finally, let us assume $p = q$. If $p = q = 2$, then $G$ is a clique, and so, $\delta(G) = \lambda(G) = 0$. Thus, from now on we assume $p \ge 3$. Again, there are two subcases, depending on the parity of $p = q$:

* Subcase $p = q$ is even. The maximum $k$ s.t. $G$ contains an isometric $H_1^k$ ($H_2^k$ and $H_3^k$, resp.) are $k = \frac{p}{2} - 1$ ($k = \frac{p}{2} - 2$ and $k = \frac{p}{2} - 2$, resp.). By (Dragan and Guarnera, 2019, Theorem 3), we obtain $\delta(G) = \frac{p}{2} - 1$. In particular, $\lambda(G) \le p - 2$. Since the $(p-1) \times q$ King's grid is an isometric subgraph of $G$ with leanness $p-2$, $\lambda(G) \ge p - 2$.

* Subcase $p = q$ is odd. The maximum $k$ s.t. $G$ contains an isometric $H_1^k$ ($H_2^k$ and $H_3^k$, resp.) are $k = \frac{p-1}{2}$ ($k = \frac{p-1}{2} - 1$ and $k = \frac{p-1}{2} - 2$, resp.). By (Dragan and Guarnera, 2019, Theorem 3), we obtain $\delta(G) = \frac{p-1}{2}$. Since $G$ does not contain an isometric $H_3^{\frac{p-1}{2}-1}$, we get $\lambda(G) = 2\delta(G) = p-1$.

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

## Triangular grids

Lastly, the triangular grid of size $p \times q$ is obtained from the $p \times q$ grid by adding all edges in $\{(i, j), (i+1, j+1)\} : 0 \le i < p-1, 0 \le j < q-1\}$.

**Proposition 10.** The $p \times q$ triangular grid has leanness $\lambda = \min\{p, q\} - 1$.

**Proof:** Recall the definition of the hyperbolicity $\delta(G)$ in Sec. 1. As proved in (Coudert and Ducoffe, 2016, Lemma 51), $\delta(G) = \min\{p,q\}-1$. Hence, $\lambda(G) \le 2\delta(G) = \min\{p,q\} - 1$. Without loss of generality, $p \le q$. Let $x = (p-1, 0)$, $y = (0, q-1)$ and $u = (0, 0)$, $v = (p-1, p-1)$. Notice that $d(x, y) = p+q-2$. Furthermore, we have $u, v \in S_{p-1}(x, y)$. As a result, $\lambda(G) \ge \lambda(x, y) \ge d(u, v) = p-1$. $\square$

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

# 5 Planar graphs

In this section, we analyze the leanness for subclasses of planar graphs.
<figure><img src="image_10.png" /><figcaption>Fig. 7: A triangular grid.</figcaption></figure>

**5.1 Outerplanar graphs**

An outerplanar graph is a planar graph in which all vertices belong to the outer face. Notice that outerplanar graphs form a hereditary class. Hence, we may restrict our study on leanness to biconnected outerplanar graphs. We refer to Syslo (1979) for basic properties of outerplanar graphs. In particular, the weak dual graph of a biconnected outerplanar graph (that is obtained from its classic dual graph by removing the universal vertex corresponding to the outer face) is a tree.

We start with an important lemma for what follows:

**Lemma 11.** In a biconnected outerplanar graph, every slice is contained in a face.

**Proof:** Let $x, y \in V$ be arbitrary, and let $u, v \in S_k(x, y)$ for some $k$ s.t. $0 < k < d(x, y)$. Suppose by contradiction there is no face containing both $u$ and $v$. Then, there exists some cut-edge $\{a, b\} \in E$ such that $u$ and $v$ are in two different connected components of $G - \{a, b\}$. Denote by $x = u_0, u_1, \cdots, u_l = y$ and $x = v_0, v_1, \cdots, v_l = y$ two shortest $xy$-paths with $u = u_k$ and $v = v_k$. The path $u_k u_{k-1} \cdots u_1 x v_1 v_2 \cdots v_k$ must go through $a$ or $b$, so, there exists some $p$ such that $0 \le p < k$ and $\{u_p, v_p\} \cap \{a, b\} \ne \emptyset$. W.l.o.g. suppose $u_p = a$. Similarly, there exists some $q$ such that $k < q \le l$ and $\{u_q, v_q\} \cap \{a, b\} \ne \emptyset$. Then, $\min\{d(u_p, u_q), d(u_p, v_q)\} \le d(a, b) = 1$. However, since we have $p < k < q$, $d(u_p, v_q) \ge d(u_p, u_q) = q - p \ge 2$. A contradiction. Hence, there must be a face containing both $u$ and $v$. $\square$

The concept of extraction is now introduced:

**Definition 2.** Let $G$ be a biconnected outerplanar graph and $C$ be one of its faces. The extraction of $C$, denoted $\tilde{C}$, is a copy of $C$ where every edge $\{u, v\}$ of $C$ is turned into a triangle if $u$ and $v$ are equidistant to some vertex in $G - (C - \{u, v\})$.

<figure><img src="image_11.png" /><figcaption>Fig. 8: Extraction of face $C$ (the red face).</figcaption></figure>
This concept was first introduced in Cohen et al. (2017), but under the different name of „sunshine graph”. In (Cohen et al., 2017, Lemma 27), a linear-time algorithm is presented in order to compute the respective extractions of all faces in a biconnected outerplanar graph.

**Theorem 12.** Let $\mathcal{F}$ denote the set of all (inner) faces in a biconnected outerplanar graph $G$. Then, the leanness of $G$ is $\lambda(G) = \max_{C \in \mathcal{F}} \lambda(\hat{C})$.

**Proof:** Let $x = u_0, u_1, \cdots u_{l-1}, u_l = y$ and $x = v_0, v_1, \cdots v_{l-1}, v_l = y$ be two shortest xy-paths for some $x, y \in V$. We pick some $k$ such that $0 < k < d(x, y)$ and $d(u_k, v_k)$ is maximized. By Lemma 11, vertices $u_k$ and $v_k$ are contained in a face $C$. Let us prove that $d(u_k, v_k) \le \lambda(\hat{C})$. For convenience, in what follows, for every $w \in C$, we denote by $\hat{w}$ its copy in $\hat{C}$. Consider minimal indices $i$ and $j$ such that $u_i, v_j \in C$. We set vertex $x'$ and index $p$ as follows:

* If $u_i = v_j$, then $i = d(u_0, u_i) = d(v_0, v_j) = j$. We set $x' = \hat{u}_i$ and $p = i$.

* Else if $i = j$, vertices $u_{i-1}$ and $v_{i-1}$ are not in $C$, by minimality of $i$ and $j$. Therefore, there is a face $C' \ne C$ containing $u_{i-1}$ and $v_{i-1}$. Note that $C \cap C' = \{u_i, v_j\}$ must be a cut-edge. Since vertex $x$ is equidistant to $u_i, v_j$ and it is a vertex of $G - (C - \{u_i, v_j\})$, edge $\{u_i, v_j\}$ has been replaced in $\hat{C}$ by a triangle. We set $x'$ as the third vertex in this triangle, $x' \ne \hat{u}_i, \hat{v}_j$, and we set $p = i - 1$.

* Otherwise, we may assume wlog that $i < j$. As in the previous case, it follows from the minimality of $i, j$ that there exists some face $C' \ne C$ such that $u_{i-1}, v_{j-1} \in C'$ and $C \cap C' = \{u_i, v_j\}$ is a cut-edge. In particular, we get $j = i + 1$. Then, $x, u_1, \dots, u_i, v_j, v_{j+1}, \dots, y$ is also a shortest path. We set $x' = \hat{u}_i$ and $p = j - 1 = i$.

By reverting the two shortest xy-paths, we can define vertex $y' \in \hat{C}$ and index $q$ in a similar way as above. By doing so, we get the two shortest paths $x', \hat{u}_{p+1}, \cdots \hat{u}_k, \cdots \hat{u}_{q-1}, y'$ and $x', \hat{v}_{p+1}, \cdots \hat{v}_k, \cdots \hat{v}_{q-1}, y'$ in $\hat{C}$. As a result, $\lambda(\hat{C}) \ge \lambda(x', y') \ge d_{\hat{C}}(\hat{u}_k, \hat{v}_k) = d_G(u_k, v_k)$. This implies $\lambda(G) \le \max_{C \in \mathcal{F}} \lambda(\hat{C})$.

Conversely, let $x', y' \in \hat{C}$ be arbitrary, for some face $C$ of $G$. Let us call triangle vertex any vertex $w \in \hat{C}$ such that $\hat{u}\hat{v}w$ is a triangle and $\{u, v\} \in E(C)$. Observe that any internal vertex in a shortest path is not a triangle vertex. In particular, the vertices in $I(x', y') \setminus \{x', y'\}$ cannot be triangle vertices. If $x'$ is a triangle vertex, and $N(x') = \{\hat{u}_1, \hat{v}_1\}$, then there exists a vertex $x$ of $G - (C - \{u_1, v_1\})$ that is equidistant to $u_1, v_1$. We replace edge $x'\hat{u}_1(x'\hat{v}_1, \text{resp.})$ by a shortest $xu_1$-path in $G$ (a shortest $xv_1$-path, resp.). We proceed similarly for $y'$ if it is a triangle vertex. By doing so, all shortest $x'y'$-paths in $\hat{C}$ can be extended into shortest xy-paths in $G$. Furthermore, every slice $S_{k'}(x', y')$, $0 < k' < d_{\hat{C}}(x', y')$, must be contained in some slice $S_k(x, y)$ in $G$. As a result, $\lambda(\hat{C}) \le \lambda(G)$. $\square$

We complete Theorem 12 with a closed-form formula for the leanness of extractions. Namely:

**Lemma 13.** Let $C$ be a face of length $4p + r$, $0 \le r \le 3$, in a biconnected outerplanar graph $G$.

* If $r$ is odd, then $\lambda(\hat{C}) = \begin{cases} 0 & \text{if } C = \hat{C} \\ 2p + \lfloor \frac{r}{2} \rfloor & \text{otherwise.} \end{cases}$

* If $r = 2$, then $\lambda(\hat{C}) = \begin{cases} 2p + 1 & \text{if there are two diametrically opposed triangles in } \hat{C} \\ 2p & \text{otherwise.} \end{cases}$
• Else, $\lambda(\hat{C}) = 2p$.

**Proof:** By Lemma 11, $\lambda(\hat{C})$ is at most the maximum diameter of its faces. Therefore, $\lambda(\hat{C}) \le \text{diam}(C)$. If $r=0$, then $\lambda(\hat{C}) \ge \lambda(C) = \text{diam}(C) = 2p$. Thus from now on we assume $r > 0$. If furthermore $C = \hat{C}$, then

$$ \lambda(\hat{C}) = \lambda(C) = \begin{cases} 0 & \text{if } r \text{ is odd} \\ 2p & \text{otherwise.} \end{cases} $$

Therefore, we also assume for the remainder of the proof $C \neq \hat{C}$.

First we assume $r$ is odd. Let $uvx$ be some triangle in $\hat{C}$ that replaces edge $\{u, v\} \in E(C)$. Since $C$ is odd, there exists a unique $y \in C$ such that $d(y, u) = d(y, v) = \text{diam}(C) = 2p + \lfloor \frac{r}{2} \rfloor$. Then, $I(x, y) = \{x\} \cup C$. Furthermore, $S_{p+1}(x, y)$ is reduced to some diametral pair of $C$. Hence, $\lambda(\hat{C}) \ge \text{diam}(C) = 2p + \lfloor \frac{r}{2} \rfloor$ in this case.

Assume $r=2$. As before, let $uvx$ be some triangle in $\hat{C}$ that replaces edge $\{u, v\} \in E(C)$. A vertex $y$ of $C$ cannot be equidistant to $u, v$ because $C$ is bipartite. Therefore, for every $y$ of $C$, $\lambda(x, y) \le \lambda(C)$. Now, let $yu'v'$ be some triangle in $\hat{C}$ that replaces edge $\{u', v'\} \in E(C)$. Without loss of generality, $G - \{\{u, v\}, \{u', v'\}\}$ is made of a $uu'$-path and a $vv'$-path. If $d(u, u') < d(v, v')$, then $\lambda(x, y) = \lambda(u, u') \le \lambda(C)$. Otherwise, $d(u, u') = d(v, v') = 2p$. In the latter situation, $I(x, y) \setminus \{x, y\} = C$. Furthermore, $S_p(x, y)$ is reduced to some diametral pair of $C$. Hence, $\lambda(\hat{C}) \ge \text{diam}(C) = 2p+1$ in this case. $\square$

**Corollary 14.** *The leanness of an outerplanar graph can be computed in linear time.*

## 5.2 Bicyclic graphs

A bicyclic graph is a graph with $m=n+1$ edges. Bicyclic graphs form a subclass of planar graphs. Furthermore, the nontrivial biconnected components of a bicyclic graph can only be of two different types, namely: they are either a cycle, or the union of three internally disjoint ab-paths for some vertices $a, b$.

For non-cycle biconnected components, the following lemma explains how to compute their leanness:

**Lemma 15.** Let $G = (V, E)$ be the union of 3 disjoint ab-paths of respective lengths $f \le g \le h$. Then, we can compute $\lambda(G)$ in linear time.

**Proof:** Notice $G$ contains three cycles $C_1, C_2, C_3$ of respective lengths $f + g \le f + h \le g + h$. Furthermore, $C_1, C_2$ must be isometric. This implies $\lambda(G) \ge \max\{\lambda(C_1), \lambda(C_2)\}$. We next give a closed-form formula for this lower bound:

$$ \textbf{Claim 1.} \max\{\lambda(C_1), \lambda(C_2)\} = \begin{cases} 2 \left\lfloor \frac{f+h}{4} \right\rfloor & \text{if } f, h \text{ are of same parity} \\ 2 \left\lfloor \frac{f+g}{4} \right\rfloor & \text{if } f \text{ and } g \text{ have a parity different from the parity of } h \\ 0 & \text{otherwise.} \end{cases} $$

Let us first consider $f, h$ to be of same parity. Then, $\lambda(C_2) = 2 \lfloor \frac{f+h}{4} \rfloor$ because $C_2$ is even. If $f$ and $g$ are of different parity, then $\lambda(C_1) = 0$ because $C_1$ is odd; otherwise, $\lambda(C_1) = 2 \lfloor \frac{f+g}{4} \rfloor \le \lambda(C_2)$.
Assume now $f, h$ are of different parity. Then, $\max\{\lambda(C_1), \lambda(C_2)\} = \lambda(C_1)$ because $C_2$ is odd. In particular, $\lambda(C_1) = 2\lfloor\frac{f+g}{4}\rfloor$ if $f, g$ are of same parity, else $\lambda(C_1) = 0$. ◦

Case $f = g = h$. In order to compute $\lambda(G)$, by Lemma 1, it suffices to consider far-apart pairs $(x, y)$ of $G$. For any $(x, y) \neq (a, b)$, let $x, y \in C_i$ for some $i$. Since $(x, y)$ must be far-apart, $d(x, y) = \text{diam}(C_i) = f$. In particular, $\{x, y\} \cap \{a, b\} = \emptyset$. Furthermore, $I(x, y) \subseteq C_i$ because there is no shortest $xy$-path that goes by $a, b$. Hence, $\lambda(x, y) \le \lambda(C_i) = 2\lfloor\frac{f}{2}\rfloor$. Since we also have $\lambda(a, b) = 2\lfloor\frac{f}{2}\rfloor$, it follows that $\lambda(G) = \lambda(a, b) = 2\lfloor\frac{f}{2}\rfloor$.

Case $f < h$. Recall that $\lambda(G) \ge \max\{\lambda(C_1), \lambda(C_2)\}$. Conversely, we prove that for most pairs $x, y$ of vertices we have $\lambda(x, y) \le \max\{\lambda(C_1), \lambda(C_2)\}$.

**Claim 2.** For $x, y \in V$, $\lambda(x, y) \le \max\{\lambda(C_1), \lambda(C_2)\}$ if one of the following conditions hold:

1. $x, y \in C_1$;

2. $x, y \in C_2$;

3. $x \in C_1 \setminus C_2$, and $\min\{d(x, a), d(x, b)\} < \frac{g-f}{2}$;

4. $d(x, a) + d(a, y) \neq d(x, b) + d(b, y)$.

In particular, $\lambda(G) = \max\{\lambda(C_1), \lambda(C_2)\}$ if $g, h$ are of different parity.

If $x, y \in C_1$ then $\lambda(x, y) \le \lambda(C_1)$ because $C_1$ is a convex subgraph of $G$. In particular, $\lambda(a, b) \le \lambda(C_1)$. Assume now $x, y \in C_2$. Either $I(x, y) \subseteq C_2$, or $f = g$ and there exists a shortest $xy$-path that goes by $a, b$. Hence, $\lambda(x, y) \le \max\{\lambda(C_2), \lambda(a, b)\} \le \max\{\lambda(C_1), \lambda(C_2)\}$.

Since $C_1, C_2$ cover $G$, up to symmetries, we are left considering the pairs $x, y$ such that $x \in C_1 \setminus C_2$, $y \in C_2 \setminus C_1$. In particular, $x$ is on the second shortest ab-path, of length $g$, while $y$ must be on the longest ab-path, of length $h$. Assume $d(x, a) < \frac{g-f}{2}$, or equivalently, $g - d(x, a) > f + d(x, a)$. Then, every shortest xb-path must go by $a$. This implies every shortest $xy$-path must go through vertex $a$, so, $\lambda(x, y) = \max\{\lambda(x, a), \lambda(y, a)\} \le \max\{\lambda(C_1), \lambda(C_2)\}$. In the same way, assuming $d(x, b) < \frac{g-f}{2}$, we get $\lambda(x, y) = \max\{\lambda(x, b), \lambda(y, b)\} \le \max\{\lambda(C_1), \lambda(C_2)\}$.

Assume $d(x, a) + d(a, y) \neq d(x, b) + d(b, y)$. Without loss of generality, $d(x, a) + d(y, a) < d(x, b) + d(y, b)$. Then again, every shortest $xy$-path must go by $a$, so, $\lambda(x, y) = \max\{\lambda(x, a), \lambda(y, a)\} \le \max\{\lambda(C_1), \lambda(C_2)\}$. Finally, note that if none of the four conditions of our claim hold, then $g + h = d(x, a) + d(y, a) + d(x, b) + d(y, b)$ must be even. ◦

The two above claims imply a closed-form formula for $\lambda(G)$ if $g, h$ are of different parity, namely:

$$ \lambda(G) = \begin{cases} 2 & \text{if } f \text{ and } h \text{ have a parity different from the parity of } g \\ 2 & \text{if } f \text{ and } g \text{ have a parity different from the parity of } h. \end{cases} $$

From now on, we assume $g, h$ to be of same parity.

**Claim 3.** Let $(x_{\text{lim}}, y_{\text{lim}})$ be the unique pair of vertices in $(C_1 \setminus C_2) \times (C_2 \setminus C_1)$ so that $d(x_{\text{lim}}, a) = \lfloor\frac{g-f}{2}\rfloor$ and $d(x_{\text{lim}}, y_{\text{lim}}) = \frac{g+h}{2}$. Then, $\lambda(G) = \max\{\lambda(C_1), \lambda(C_2), \lambda(x_{\text{lim}}, y_{\text{lim}})\}$.
Assume the existence of a pair $(x, y)$ such that $\lambda(x, y) > \max\{\lambda(C_1), \lambda(C_2)\}$ (else, we are done). We deduce from the previous claim that, up to symmetries:

* $x \in C_1 \setminus C_2$, $y \in C_2 \setminus C_1$;

* $\frac{g-f}{2} \le \min\{d(x, a), d(x, b)\} \le \max\{d(x, a), d(x, b)\} \le \frac{g+f}{2}$;

* $d(x, y) = \frac{g+h}{2}$.

By symmetry, we may further assume $d(x, a) \le d(x, b)$. Then, $\frac{g-f}{2} \le d(x, a) \le \frac{g}{2}$.

There are at most three shortest xy-paths, namely: one going by a and not by b, one going by b but not by a, and one going by both a and b. Furthermore, the shortest xy-path that goes by a, b exists if and only if $d(x, b) = g - d(x, a) = f + d(x, a)$ (the other two shortest paths always exist, because $a, b \in I(x, y)$, and they cover $C_3$).

Assume for what follows $d(x, a) > \lfloor \frac{g-f}{2} \rfloor$. Then, there are two shortest xy-paths. Let $k$ be such that $0 < k < d(x, y)$ and $\text{diam}(S_k(x, y))$ is maximized. We have that $S_k(x, y) = \{u, v\}$, with $u, a$ and $v, b$ being on a same shortest xy-path respectively. Let us pick $x' \in S_1(x, a)$, $y' \in S_1(y, b)$. Note that $x'$, $y'$ are unique. Furthermore, we still have $\frac{g-f}{2} \le d(x', a) \le \frac{g}{2}$ and $d(x', y') = \frac{g+h}{2}$. Observe that $u'$, $v'$ are unique. Furthermore, we still have $u' \in S_k(x', y')$ where $u' \in S_1(u, y)$, $v' \in S_1(v, x)$. Since all induced $u'v'$-paths in $G$ are at least as long as the corresponding induced uv-paths, $\lambda(x', y') \ge d(u', v') \ge d(u, v) = \lambda(x, y)$. ◇

The remainder of the proof consists in computing $\lambda(x_{\text{lim}}, y_{\text{lim}})$. For that, let $P_a$ be the shortest $x_{\text{lim}}y_{\text{lim}}$-path that goes by a and does not go by b. Let $P_b$ be defined similarly. For every $k$ such that $0 < k < \frac{g+h}{2}$, let $u_k \in P_a$, $v_k \in P_b$ be at distance $k$ to $x_{\text{lim}}$, and let $d_k = d(u_k, v_k)$.

**Claim 4.** $\lambda(x_{\text{lim}}, y_{\text{lim}}) \le \max\{\lambda(C_1)\} \cup \{d_k : 0 < k < (g+h)/2\}$.

The claim is trivial if there are only two shortest $x_{\text{lim}}y_{\text{lim}}$-paths. So, assume $d(x_{\text{lim}}, a) = \frac{g-f}{2}$, and let $P_{ab}$ be the shortest $x_{\text{lim}}y_{\text{lim}}$-path that goes by a, b. For $k$ such that $\frac{g-f}{2} < k < \frac{g+f}{2}$, let $w_k \in P_{ab}$ be at distance $k$ to $x_{\text{lim}}$. Observe that $v_k, w_k \in S_k(x_{\text{lim}}, b)$, so, $d(v_k, w_k) \le \lambda(x_{\text{lim}}, b) \le \lambda(C_1)$. Furthermore, $d(u_k, v_k) \ge d(u_k, w_k)$ because all induced $u_k v_k$-paths are at least as long as the corresponding $u_k w_k$-paths. Hence, $\text{diam}(S_k(x_{\text{lim}}, y_{\text{lim}})) \le \max\{\lambda(C_1), d_k\}$. ◇

In order to compute $d_k$, we need to consider the ab-paths that contain $u_k, v_k$.

* Assume $k \le d(x_{\text{lim}}, a)$. Then, $u_k, v_k$ both lie on the second ab-path, of length $g$. We have $d_k = \min\{2k, f + g - 2k\}$. Since the function $t \mapsto \min\{2t, f + g - 2t\}$ is maximized at $t = (f + g)/4$, we get

$$d_k \le l_1 = \begin{cases} 2d(x_{\text{lim}}, a) = 2\left\lfloor\frac{g-f}{2}\right\rfloor & \text{if } d(x_{\text{lim}}, a) \le \left\lfloor\frac{g+f}{4}\right\rfloor \\ \max\left(2\left\lfloor\frac{f+g}{4}\right\rfloor, f+g-2\left\lfloor\frac{f+g}{4}\right\rfloor\right) & \text{else.} \end{cases}$$

* Assume $d(x_{\text{lim}}, a) < k \le d(x_{\text{lim}}, b)$. Now, $u_k$ is on the third ab-path, of length $h$. We have $d_k = \min\{2k, g+h-2k, f+g-2d(x_{\text{lim}}, a)\} = \min\{2k, g+h-2k, f+g-2\left\lfloor\frac{g-f}{2}\right\rfloor\}$. Since
the function $t \mapsto \min\{2t, g+h-2t\}$ is maximized at $t = \frac{g+h}{4}$, we get

$$d_k \le l_2 = \begin{cases} \min\left\{2 d(x_{\text{lim}}, b), f + g - 2 \left\lfloor \frac{g-f}{2} \right\rfloor\right\} & \text{if } d(x_{\text{lim}}, b) \le \left\lfloor \frac{g+h}{4} \right\rfloor \\ \min\left\{2 \left\lfloor \frac{g+f}{2} \right\rfloor, f + g - 2 \left\lfloor \frac{g-f}{2} \right\rfloor\right\} & \\ \min\left\{\max\left(2 \left\lfloor \frac{g+h}{4} \right\rfloor, g+h-2 \left\lfloor \frac{g+h}{4} \right\rfloor\right), f + g - 2 \left\lfloor \frac{g-f}{2} \right\rfloor\right\} & \text{else.} \end{cases}$$

* Otherwise, $k > d(x_{\text{lim}}, b)$. Now, $v_k$ is also on the third ab-path. We have $d_k = \min\{2k - g + f, g+h-2k\}$. Since the function $t \mapsto \min\{2t - g + f, g+h-2t\}$ is maximized at $t = \frac{2g+h-f}{4}$, we get

$$d_k \le l_3 = \begin{cases} g+h-2d(x_{\text{lim}}, b) = g+h-2\left\lfloor\frac{g+f}{2}\right\rfloor & \text{if } d(x_{\text{lim}}, b) \ge \left\lfloor\frac{2g+h-f}{4}\right\rfloor \\ \max\left(2\left\lfloor\frac{2g+h-f}{4}\right\rfloor - g+f, g+h-2\left\lfloor\frac{2g+h-f}{4}\right\rfloor\right) & \text{else.} \end{cases}$$

Finally, $\lambda(x_{\text{lim}}, y_{\text{lim}}) = \max\{l_1, l_2, l_3\}$. $\square$

**Corollary 16.** The leanness of a bicyclic graph can be computed in linear time.

# 6 Other classes

In this last section, we consider some nonplanar graph classes. Unlike the graphs in Sec. 4 & 5, all graphs considered in what follows have bounded leanness. We obtain linear-time algorithms for computing their leanness, for all graph classes considered except for bisplit graphs. For the latter class, a conditional quadratic lower bound, up to sub-polynomial factors, is proved assuming the SETH (see Sec. 6.4).

## 6.1 Chordal graphs

Recall that a graph is chordal if and only if every induced cycle has length three. A block graph is a graph whose biconnected components are cliques. Note that block graphs are a subclass of both chordal graphs and geodetic graphs.

**Proposition 17.** For a chordal graph $G = (V, E)$, we have

$$\lambda(G) = \begin{cases} 0 & \text{if } G \text{ is a block graph} \\ 1 & \text{else.} \end{cases}$$

In particular, the leanness of a chordal graph can be computed in linear time.

**Proof:** It has been proved in Chang and Nemhauser (1984) that every slice in a chordal graph $G$ is a clique. Hence, $\lambda(G) \le 1$. Furthermore, a necessary condition for having $\lambda(G) = 0$ is that $G$ must be diamond-free. Diamond-free chordal graphs are exactly the block graphs Bandelt and Mulder (1986), so, they are geodetic graphs. $\square$
## 6.2 Cographs

Cographs can be recursively defined as follows:

* the one-vertex graph is a cograph;

* the disjoint union of two cographs is also a cograph;

* and the complement of a cograph is also a cograph.

The join of two graphs $G_1, G_2$, denoted $G_1 \oplus G_2$, is obtained by adding all possible edges between $V(G_1)$ and $V(G_2)$. Notice that the join of two cographs is also a cograph. In fact, every connected cograph with $n > 1$ vertices must be the join of two cographs.

An equivalent definition of cographs is that they are exactly the $P_4$-free graphs Corneil et al. (1981). Therefore, $\lambda(G) \le \text{diam}(G) \le 2$ for every cograph $G$. Next, we present a characterization of the leanness on cographs, that can be verified in linear time.

**Proposition 18.** For a cograph $G = (V, E)$, we have

$$ \begin{cases} \lambda(G) \le 1 & \text{if } G \text{ is chordal} \\ \lambda(G) = 2 & \text{otherwise.} \end{cases} $$

**Proof:** Since $G$ is $P_4$-free, every induced cycle in $G$ has length at most four. So, if $G$ is $C_4$-free, then $G$ is chordal, so $\lambda(G) \le 1$. Otherwise, $\lambda(G) \ge \lambda(C_4) = 2$. Since we also have $\lambda(G) \le \text{diam}(G) \le 2$, we obtain $\lambda(G) = 2$. $\square$

Recall that chordal graphs can be recognized in linear time Tarjan and Yannakakis (1984). Therefore:

**Corollary 19.** The leanness of a cograph can be computed in linear time.

## 6.3 Distance-hereditary graphs

A graph is called distance-hereditary if every induced subgraph is also isometric (i.e., distance-preserving). Our next result shows that the leanness of distance-hereditary graphs can be characterized in the exact same way as for cographs.

**Proposition 20.** For a distance-hereditary graph $G = (V, E)$, we have

$$ \begin{cases} \lambda(G) \le 1 & \text{if } G \text{ is chordal} \\ \lambda(G) = 2 & \text{otherwise.} \end{cases} $$

In particular, the leanness of $G$ can be computed in linear time.

**Proof:** For every $k \ge 5$, we have $\text{diam}(P_{k-1}) = k - 2 > \lfloor \frac{k}{2} \rfloor = \text{diam}(C_k)$. This implies that every induced cycle in a distance-hereditary graph $G$ must have length at most four. In particular, if $G$ is $C_4$-free, then it is chordal, so, $\lambda(G) \le 1$. Otherwise, $\lambda(G) \ge 2$. In order to complete the proof, we show that $\lambda(G) \le 2$ for every distance-hereditary graph $G$. By contradiction, let $G = (V, E)$ be a minimum-size distance-hereditary graph such that $\lambda(G) \ge 3$. There is no degree-one vertex $v \in V$ because otherwise $\lambda(G) = \lambda(G \setminus v)$, thus contradicting the minimality of $G$. By (Bandelt and Mulder, 1986, Theorem 1),
there exist twin vertices $u, v$ in $G$, i.e., we have $N(u) \setminus \{v\} = N(v) \setminus \{u\}$. However, in this situation $\lambda(G) \le \max\{\lambda(G \setminus v), d(u, v)\} \le \max\{\lambda(G \setminus v), 2\}$. The latter either contradicts the minimality of $G$, or that $\lambda(G) \ge 3$. $\square$

We stress that distance-hereditary graphs are a superclass of cographs. Hence, our result for distance-hereditary graphs subsumes the one for cographs. Nevertheless, the proof for cographs is, in our opinion, slightly simpler.

## 6.4 Lower bound on bisplit graphs

A *split graph* is a graph where the vertices can be bipartitioned in a clique and a stable set. A *bisplit graph* is a graph where the vertices can be bipartitioned in a biclique (i.e., complete bipartite subgraph) and an independent set. We stress that split graphs (bisplit graphs, resp.) have diameter at most three (at most four, resp.). Hence, the leanness of split graphs and bisplit graphs is bounded. Furthermore, split graphs are a special case of chordal graphs, so, their leanness can be computed in linear time. Perhaps surprisingly, we prove next that the situation is different for bisplit graphs.

Recall the Strong Exponential-Time Hypothesis (SETH) and the DISJOINTSET problem were introduced in Sec. 3.2.

**Theorem 21.** Under the SETH, deciding whether a bisplit graph $G = (V, E)$ has leanness 2 or 4 requires $\Omega(n^{2-o(1)})$ time. The result holds even if $G$ has $n^{1+o(1)}$ edges.

**Proof:** Let $A, B \subset \mathcal{P}(C)$ be some instance of DISJOINTSET, where $A, B$ are families of $n$ sets over come common universe $C$, $|C| = n^{o(1)}$. Recall that our objective is to decide whether there exist $a, \in A, b \in B$ such that $a \cap b = \emptyset$.

The graph $G = (V, E)$ is constructed as follows (see Fig. 9).

* $V = A \cup B \cup C \cup C' \cup \{u, v, x, y, z\}$, where $C'$ is a disjoint copy of $C$ and $u, v, x, y, z$ are fresh new vertices. For every $c \in C$, let us denote $c'$ the corresponding element in $C'$;

* For every set $a \in A$ and every element $c \in C$, we add the two edges $ac, ac'$ if and only if $c \in a$. We proceed similarly for every set $b \in B$ and every element $c \in C$;

* We add all possible edges between: $u$ and $A$, $v$ and $B$, $x$ and $C$, $y$ and $C'$;

* Finally, vertex $z$ is adjacent to $u, v$ and to every vertex of $C \cup C'$.

<figure><img src="image_12.png" /><figcaption>**Fig. 9:** Reduction from DISJOINTSET.</figcaption></figure>
Note that we can construct $G$ from $A, B, C$ in $n^{1+o(1)}$ time. Furthermore, $G$ is a bisplit graph: $\{x, y\} \cup A \cup B$ is an independent set, and there is a complete bipartite subgraph with respective partite sets $\{z\}$ and $\{u, v\} \cup C \cup C'$. The graph $G$ is also bipartite: its partite sets are $\{x, y, z\} \cup A \cup B$ and $\{u, v\} \cup C \cup C'$. Therefore, $\lambda(G)$ must be even. Furthermore, $\lambda(G) \le \text{diam}(G) \le 2\text{ecc}(z) = 4$. Hence, we are left deciding whether $\lambda(G) = 2$ or $\lambda(G) = 4$.

Assume there exist $a \in A, b \in B$ such that $a \cap b = \emptyset$. By construction of $G$, $S_2(x, y) = A \cup B \cup \{z\}$. Therefore, $\lambda(G) \ge \lambda(x, y) \ge d(a, b) = 4$. Conversely, assume that $a \cap b \ne \emptyset$ for every $a \in A, b \in B$. Then, $x, y$ is the only pair of vertices such that $d(x, y) = 4$. Since we have $\lambda(x, y) = \text{diam}(S_2(x, y)) = \text{diam}(A \cup B \cup \{z\}) = 2$, it follows that $\lambda(G) = 2$. $\square$

## References

H.-J. Bandelt and V. Chepoi. Metric graph theory and geometry: a survey. *Contemporary Mathematics*, 453:49–86, 2008.

H.-J. Bandelt and H. M. Mulder. Distance-hereditary graphs. *Journal of Combinatorial Theory, Series B*, 41(2):182–208, 1986. doi: 10.1016/0095-8956(86)90043-2.

G. Bodwin. On the structure of unique shortest paths in graphs. In *Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms*, SODA, pages 2071–2089. SIAM, 2019. doi: 10.5555/3310435.3310560.

J. A. Bondy and U. S. R. Murty. *Graph Theory*. Graduate Texts in Mathematics. Springer, 2008. ISBN 978-1-84628-970-5. doi: 10.1007/978-1-84628-970-5.

M. Borassi, D. Coudert, P. Crescenzi, and A. Marino. On Computing the Hyperbolicity of Real-World Graphs. In *23rd Annual European Symposium on Algorithms (ESA)*, volume 9294 of *Lecture Notes in Computer Science*, pages 215–226, Patras, Greece, Sept. 2015. Springer. doi: 10.1007/978-3-662-48350-3\_19.

M. Borassi, P. Crescenzi, and M. Habib. Into the square: On the complexity of some quadratic-time solvable problems. *Electron. Notes Theor. Comput. Sci.*, 322:51–67, 2016. doi: 10.1016/j.entcs.2016.03.005.

G. Brinkmann, J. H. Koolen, and V. Moulton. On the hyperbolicity of chordal graphs. *Annals of Combinatorics*, 5(1):61–69, 2001. doi: 10.1007/s00026-001-8007-7.

J. Chalopin, V. Chepoi, H. Hirai, and D. Osajda. *Weakly modular graphs and nonpositive curvature*, volume 268 of *Memoirs of the AMS*. American Mathematical Society, 2020. ISBN 978-1-4704-4362-7.

G. J. Chang and G. L. Nemhauser. The k-domination and k-stability problems on sun-free chordal graphs. *SIAM Journal on Algebraic Discrete Methods*, 5(3):332–345, 1984. doi: 10.1137/0605034.

V. Chepoi, F. F. Dragan, B. Estellon, M. Habib, and Y. Vaxès. Diameters, centers, and approximating trees of $\delta$-hyperbolic geodesic spaces and graphs. In *Proceedings of the 24th ACM Symposium on Computational Geometry, College Park, MD, USA, June 9-11, 2008*, pages 59–68. ACM, 2008. doi: 10.1145/1377676.1377687.
V. Chepoi, F. F. Dragan, and Y. Vaxès. Core congestion is inherent in hyperbolic networks. In *Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms*, SODA '17, pages 2264–2279, Barcelona, Spain, 2017. doi: 10.5555/3039686.3039835.

N. Cohen, D. Coudert, and A. Lancin. On computing the Gromov hyperbolicity. *ACM Journal of Experimental Algorithmics*, 20(1):18, 2015. doi: 10.1145/2780652.

N. Cohen, D. Coudert, G. Ducoffe, and A. Lancin. Applying clique-decomposition for computing Gromov hyperbolicity. *Theoretical Computer Science*, 690:114–139, 2017. doi: 10.1016/j.tcs.2017.06.001.

D. G. Corneil, H. Lerchs, and L. S. Burlingham. Complement reducible graphs. *Discrete Applied Mathematics*, 3(3):163–174, 1981. doi: 10.1016/0166-218X(81)90013-5.

D. Coudert and G. Ducoffe. Data center interconnection networks are not hyperbolic. *Theoretical Computer Science*, 639:72–90, 2016. doi: 10.1016/j.tcs.2016.05.025.

D. Coudert, A. Nusser, and L. Viennot. Enumeration of far-apart pairs by decreasing distance for faster hyperbolicity computation. *ACM Journal of Experimental Algorithmics*, 27(1.15):29, Dec. 2022a. doi: 10.1145/3569169.

D. Coudert, A. Nusser, and L. Viennot. Hyperbolicity Computation through Dominating Sets. In *ALENEX 2022 - SIAM Symposium on Algorithm Engineering and Experiments*, pages 78–90, Alexandria, VA, United States, Jan. 2022b. doi: 10.1137/1.9781611977042.7.

M. Dalirrooyfard and V. Vassilevska Williams. Induced cycles and paths are harder than you think. In *2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)*, pages 531–542. IEEE, 2022. doi: 10.1109/FOCS54457.2022.00057.

F. F. Dragan and H. M. Guarnera. Obstructions to a small hyperbolicity in Helly graphs. *Discrete Mathematics*, 342(2):326–338, 2019. ISSN 0012-365X. doi: 10.1016/j.disc.2018.10.017.

D. B. Epstein. *Word processing in groups*. CRC Press, 1992. doi: 10.1201/9781439865699.

M. Gromov. Hyperbolic groups. In *Essays in Group Theory*, volume 8 of *Mathematical Sciences Research Institute Publications*, pages 75–263. Springer, New York, 1987. ISBN 978-1-4613-9588-1. doi: 10.1007/978-1-4613-9586-7_3.

J. Hopcroft and R. E. Tarjan. Algorithm 447: efficient algorithms for graph manipulation. *Communications of the ACM*, 16(6):372–378, 1973. doi: 10.1145/362248.362272.

R. Impagliazzo and R. Paturi. On the complexity of $k$-SAT. *Journal of Computer and System Sciences*, 62(2):367–375, 2001. doi: 10.1006/jcss.2000.1727.

W. S. Kennedy, I. Saniee, and O. Narayan. On the hyperbolicity of large-scale networks and its estimation. In *IEEE International Conference on Big Data*, pages 3344–3351. IEEE Computer Society, Dec. 2016. doi: 10.1109/BigData.2016.7840994.

J. H. Koolen and V. Moulton. Hyperbolic bridged graphs. *European Journal of Combinatorics*, 23(6): 683–699, 2002. doi: 10.1006/eujc.2002.0591.
A. Lincoln, V. Vassilevska Williams, and R. R. Williams. Tight hardness for shortest cycles and paths in sparse graphs. In *Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms*, pages 1236–1252. SIAM, 2018. doi: 1721.1/125617.

A. O. Mohammed, F. F. Dragan, and H. M. Guarnera. Fellow travelers phenomenon present in real-world networks. In *Complex Networks & Their Applications X - Volume 1, Proceedings of the Tenth International Conference on Complex Networks and Their Applications, COMPLEX NETWORKS 2021*, volume 1015 of *Studies in Computational Intelligence*, pages 194–206. Springer, 2021. doi: 10.1007/978-3-030-93409-5\_17.

L. Nebeský. An algebraic characterization of geodetic graphs. *Czechoslovak Mathematical Journal*, 48: 701–710, 1998.

P. S. Novikov. On the algorithmic unsolvability of the word problem in group theory. *Trudy Matematicheskogo Instituta imeni VA Steklova*, 44:3–143, 1955.

O. Ore. Theory of graphs. In *Colloquium Publications*. American Mathematical Society, 1962.

P. Papasoglu. Strongly geodesically automatic groups are hyperbolic. *Inventiones mathematicae*, 121: 323–334, 1995. doi: 10.1007/BF01884301.

J. Plesník. Two constructions of geodetic graphs. *Mathematica Slovaca*, 27(1):65–71, 1977.

R. Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs. *Journal of computer and system sciences*, 51(3):400–403, 1995. doi: 10.1006/jcss.1995.1078.

J. G. Stemple and M. E. Watkins. On planar geodetic graphs. *Journal of Combinatorial Theory*, 4(2): 101–117, 1968. doi: 10.1016/S0021-9800(68)80035-3.

M. M. Syslo. Characterizations of outerplanar graphs. *Discrete Mathematics*, 26(1):47–53, 1979. doi: 10.1016/0012-365X(79)90060-8.

R. E. 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. doi: 10.1137/0213035.

V. Vassilevska Williams, Y. Xu, Z. Xu, and R. Zhou. New Bounds for Matrix Multiplication: from Alpha to Omega. In *ACM-SIAM Symposium on Discrete Algorithms, SODA*, pages 3792–3835, 2024. doi: 10.1137/1.9781611977912.134.

R. Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. *Theoretical Computer Science*, 348(2-3):357–365, 2005. doi: 10.1016/j.tcs.2005.09.023.

Y. Wu and C. Zhang. Hyperbolicity and chordality of a graph. *The electronic journal of combinatorics*, 18(1):P43, 2011. doi: 10.37236/530.