# Constraining $f(T,B)$ Teleparallel Gravity From Energy Conditions

Snehasish Bhattacharjee<EMAIL_ADDRESS>Department of
Astronomy, Osmania University, Hyderabad, 500007, India

###### Abstract

Abstract: $f(T,B)$ teleparallel gravity is a recently proposed straightforward
generalization of the popular $f(T)$ teleparallel gravity by the incorporation
of a boundary term
$B=\frac{2}{e}\partial_{i}(eT^{i})=\bigtriangledown_{i}T^{i}$ where $T$ denote
the torsion scalar ftb13 . In this work, I investigate the viability of some
well motivated $f(T,B)$ teleparallel gravity models of the forms $f=\alpha
B^{n}+\beta T^{m}$, $f=\alpha B^{n}T^{m}$ and $f=\alpha\log(B)+\beta T$ where
$\alpha,\beta,n$ and $m$ are free parameters from the inequalities imposed the
the weak energy condition. I use the recent estimates of Hubble, deceleration,
jerk and snap parameters in finding corners in parameter spaces for the
cosmological models for which the energy density remain positive and the weak
energy condition ( i.e, $\rho+p\geq 0$, where $p$ and $\rho$ represent
respectively the cosmological pressure and energy density) attains a minute
positive value, as this implies the EoS parameter $\omega=p/\rho\simeq-1$ and
therefore consistent with an accelerating universe.

Keywords: modified gravity; energy conditions; cosmography; observational
constraints

##  I Introduction

Cosmological observations indicate the universe is accelerating observations .
Understanding what fuels this late-time acceleration is one of the most
important problems in theoretical physics. Additionally, the formation of
large scale structures requires the presence of supplementary non-dissipative
matter in high abundance. These cosmological entities together account for
about 95% of the energy budget of the universe but hitherto has no
observational evidence to support their holy presence. Several candidates to
expound these phenomena have been reported but none as popular as dark matter
and dark energy.
The physics governing dark energy has very little theoretical motivation since
it possesses a negative EoS parameter and thus create a repulsive
gravitational force which is in total contrast with the usual attractive
nature of gravity. Interestingly, there are two ways to circumvent this
problem: Firstly, one can introduce extra scalar fields which possess a
negative EoS parameter adhered to general relativity and secondly, modify
general relativity at high energy scales which results in some kind of dark
energy effects purely geometrical in nature (see ref3 ; ref4 ; ref5  for some
recent interesting results in modified gravity theories).
Amongst numerous modified gravity theories, teleparallel gravity theory has
gained significant prominence in addressing the late-time acceleration ftb17 ;
mandal ; cap2 . Recently, teleparallel gravity has been applied and yielded
interesting results in gravitational baryogenesis fqt ; baryo/2020 .
Cosmography in $f(T)$ gravity was studied in cap1 . In ftb13 ; no , the simple
$f(T)$ teleparallel gravity was generalized through the introduction of a new
Lagrangian $f(T,B)$, where $B$ is a boundary term related to the divergence of
torsion scalar $T$. Thermodynamical studies in $f(T,B)$ gravity were reported
in ftb . Interestingly for $f(-T+B)$, the field equations correspond to that
of $f(R)$ gravity cap3 . In this work, I am interested in constraining some
widely used $f(T,B)$ gravity models in a flat FRW spacetime with the energy
conditions. Particularly, I first presume the cosmic fluid obeys the equation
of state of the form $p=\omega\rho$ where $p$, $\rho$ and $\omega$ represent
respectively the cosmological pressure, energy density and EoS parameter. I
then find corners in parameter spaces for which the energy density remains
positive and the weak energy condition is slightly greater than zero as this
implies $\omega\simeq-1$ and therefore consistent with latest Planck
measurements planck .
Energy conditions are crucial for understanding the physics of singularities
and classical black holes thermodynamics (see hawking  for more details). One
can construct the energy conditions from the Raychaudhuri equation for an
expanding universe, where the attractive nature of gravity indicate
$R_{ij}\kappa^{i}\kappa^{j}\geq 0$, where $R_{ij}$ represents the Ricci tensor
and $\kappa^{i}$ any null vector. In general relativity, one obtains
$T_{ij}\kappa^{i}\kappa^{j}\geq 0$, where $T_{ij}$ represents the stress
energy momentum tensor. This inequality is commonly known as the null energy
condition. The weak energy condition postulates that the local energy density
is always positive and therefore $T_{ij}U^{i}U^{j}\geq 0$, for all timelike
vectors $U^{i}$. In this paper, I focus on the case where the cosmic fluid is
perfect and therefore the weak energy condition can be re-written in
simplified form as $\rho\geq 0$ and $\rho+p\geq 0$. Energy conditions have
been extensively used to constrain $f(R)$ gravity ecfr , $f(T)$ gravity ecft ,
$f(G)$ gravity ecfg , $f(R,G)$ gravity ecfrg  and $f(R,T)$ gravity ecfrt .
However, as far as I know, no studies aimed at constraining $f(T,B)$ gravity
has been made so far. Since this is a newly constructed modified gravity
theory, the constraints imposed by energy conditions would be very useful in
understanding the efficiency and applicability of this modified gravity in
cosmology.
The manuscript is organized as follows: In Section II, I summarize the
$f(T,B)$ teleparallel gravity. In Section III I describe the and obtain
expressions of the energy conditions from the $f(T,B)$ gravity Friedmann
equations. In Section IV I present some well motivated $f(T,B)$ gravity models
and put constraints on the parameter spaces for which the weak energy
condition attains a small positive value and in Section V I present the
conclusions and final remarks.

##  II  $f(T,B)$ Gravity

In this section I shall briefly discuss teleparallel $f(T)$ gravity and its
extension to $f(T,B)$ gravity. In this theory, the tetrads $e^{a}_{i}$ are the
dynamical variables which form an orthonormal basis for the tangent space at
each point $x^{i}$ of the spacetime manifold no . Therefore, $e^{m}_{i}$ along
with their inverses $U^{i}_{n}$ follow:

$e^{m}_{i}E_{n}^{i}=\delta^{m}_{n},\hskip
18.06749pte^{n}_{j}E_{n}^{j}=\delta^{j}_{i}.$ (1)

From these relations, the metric $g_{ij}$ can be written as

$g_{ij}=e^{a}_{i}e^{b}_{j}\eta_{ab},$ (2)

where $\eta_{ab}$ represents the Minkowski metric. In teleparallel gravity,
the geometry is coupled with a torsion and is globally curvature less. To
achieve this, the torsion tensor is defined as

$T^{a}_{ij}=\partial_{i}e^{a}_{j}-\partial_{j}e^{a}_{j}.$ (3)

Furthermore, the contorsion tensor reads

$T^{\epsilon}{}_{ij}-T_{ij}{}^{\epsilon}+T_{i}{}^{\epsilon}{}_{j}=2F_{i}{}{\epsilon}{}_{j}$
(4)

and also the following tensor

$2C_{\epsilon}{}^{ij}=F_{\epsilon}{}^{ij}-\partial^{i}_{\epsilon}T^{i}+\partial^{j}_{\epsilon}T^{j}.$
(5)

The joint term $C_{\epsilon}{}^{ij}T^{\epsilon}{}_{ij}$ is called the torsion
scalar $T$. Remarkably the Ricci scalar $R$ can be defined as

$R=-T+\frac{2}{e}\partial_{i}(eT^{i})=-T+B.$ (6)

Where $B$ is nothing but a boundary term defined as
$B=\frac{2}{e}\partial_{i}(eT^{i})=\bigtriangledown_{i}T^{i}$. Thus
teleparallel gravity coupled with $B$ reproduces the exact field equations as
in general relativity.
With that reasoning, the authors in ftb13  introduced the $f(T,B)$
teleparallel gravity in which the action is defined as

$\mathcal{S}=\frac{1}{\kappa}\int d^{4}xef(T,B)+\mathcal{L}_{m}.$ (7)

Where $\mathcal{L}_{m}$ represents matter Lagrangian. Through the addition of
the boundary term $B$, $f(T)$ gravity becomes a generalized metric counterpart
of $f(R)$ gravity no  since for $f(T,B)=f(-T+B)=f(R)$.
Varying the action 7 with respect to the tetrad, I arrive at the following
field equation,

$16\pi e\Theta^{\lambda}_{a}=eBE^{\lambda}_{a}f_{B}+2eE^{\lambda}_{a}\square
f_{B}-2eE^{\sigma}_{a}\bigtriangledown^{\lambda}\bigtriangledown_{\sigma}f_{B}+4\partial_{i}(eS_{a}^{i\lambda})f_{T}\\\
+4e\left[\partial_{i}f_{B}+\partial_{i}f_{T}\right]S_{a}^{i\lambda}-4ef_{T}T^{\sigma}_{ia}S_{\sigma}^{\lambda
i}-efE^{\lambda}_{a}.$ (8)

In this work, I am interested in constraining some well motivated $f(T,B)$
gravity models in a flat FRW spacetime from the energy conditions.
To achieve this, I shall now assume a flat FLRW metric of the form

$ds^{2}=dt^{2}-a(t)^{2}\sum_{i=1}^{3}dr^{2}_{i}$ (9)

where $a(t)$ denote the scale factor. Since $f(T,B)$ gravity is not invariant
under Lorentz transformations, care must be taken when tetrads are chosen.
Undesirable cases like $f_{TT}=0$ appears when one considers a flat diagonal
FLRW tetrad in spherical polar coordinates no .
For the universe comprising predominantly of a perfect fluid, the Friedmann
equations reads

$\rho_{eff}(t)=\rho_{matter}-3H^{2}(3f_{B}+2f_{T})-3\dot{H}f_{B}+3H\dot{f_{B}}+\frac{1}{2}f$
(10)

and

$p_{eff}(t)=p_{matter}-\left[-(3f_{B}+2f_{T})(-3H^{2}+\dot{H})+\ddot{f_{B}}-2H\dot{f_{T}}+\frac{1}{2}f\right],$
(11)

where $\rho_{matter}$ and $p_{matter}$ are the energy density and pressure for
the matter fluid sources. The expressions of the energy density $\rho_{de}$
and pressure $p_{de}$ for the effective dark energy fluid in $f(T,B)$ gravity
can be written as

$\rho_{de}(t)=-3H^{2}(3f_{B}+2f_{T})-3\dot{H}f_{B}+3H\dot{f_{B}}+\frac{1}{2}f$
(12)

and

$p_{de}(t)=-\left[-(3f_{B}+2f_{T})(-3H^{2}+\dot{H})+\ddot{f_{B}}-2H\dot{f_{T}}+\frac{1}{2}f\right].$
(13)

##  III Energy Conditions

Energy conditions are linear relationships based on Raychaudhuri equation
comprising energy density and pressure employed to understand the nature of
timelike, lightlike and spacelike curves and commonly used in studies related
to singularities ft25 ; ft26 . The origin of these energy conditions is
independent of any theory of gravity and are purely geometrical in nature fte
; hawking . The energy conditions are defined as fte16 ; fte17

$NEC\Longleftrightarrow\rho_{eff}(t)+p_{eff}(t)\geq 0.$ (14)
$WEC\Longleftrightarrow\rho_{eff}(t)\geq 0\hskip 7.22743pt\text{and}\hskip
7.22743pt\rho_{eff}(t)+p_{eff}(t)\geq 0.$ (15)
$SEC\Longleftrightarrow\rho_{eff}(t)+3p_{eff}(t)\geq 0\hskip
7.22743pt\text{and}\hskip 7.22743pt\rho_{eff}(t)+p_{eff}(t)\geq 0.$ (16)
$DEC\Longleftrightarrow\rho_{eff}(t)\geq 0\hskip 7.22743pt\text{and}\hskip
7.22743pt\rho_{eff}(t)\pm p_{eff}(t)\geq 0.$ (17)

In cosmology, the higher derivatives of Hubble parameter $H=\frac{\dot{a}}{a}$
such as deceleration, jerk and snap parameters can be defined as

$q=\frac{-1}{H^{2}}\frac{\ddot{a}}{a},\hskip
10.84006ptj=\frac{1}{H^{3}}\frac{\dddot{a}}{a},\hskip
10.84006pts=\frac{1}{H^{4}}\frac{\ddddot{a}}{a},$ (18)

respectively.
Now, using Eq. 18, the derivatives of $H$ can be recast into following forms

$\dot{H}=-H^{2}(1+q)$ (19) $\ddot{H}=H^{3}(2+3q+j)$ (20)
$\dddot{H}=H^{4}(-3-5q-2j+s).$ (21)

The matter sector (i.e, $\rho_{matter}$ and $p_{matter}$) obey the energy
conditions and that the validation or violation of the energy conditions is
purely determined by the dark energy fluid (i.e, $\rho_{de}$ and $p_{de}$).
Therefore using Eqs. 19 \- 21 in Eqs. 10 & 11, the energy conditions (Eqs.
14-17) can be re-expressed as

$NEC\Longleftrightarrow-H^{2}(q+1)(3f_{B}+2f_{T})+3f_{B}H^{2}(q+1)-3\dot{f_{B}}H^{3}(q+1)\\\
-\ddot{f_{B}}H^{3}(j+3q+2)-2\dot{f_{T}}H^{3}(q+1)+0\geq 0.$ (22)
$WEC\Longleftrightarrow 0.5f-3H^{2}(-f_{B}(q-2)+\dot{f_{B}}H(q+1)+2f_{T})\geq
0,\hskip 18.06749pt\text{and}\\\
-H^{2}(q+1)(3f_{B}+2f_{T})+3f_{B}H^{2}(q+1)-3\dot{f_{B}}H^{3}(q+1)-\ddot{f_{B}}H^{3}(j+3q+2)-2\dot{f_{T}}H^{3}(q+1)+0\geq
0.$ (23) $SEC\Longleftrightarrow
3\left(\begin{multlined}-0.5f-H^{2}(q+1)(3f_{B}+2f_{T})+3H^{2}(3f_{B}+2f_{T})\\\
-\ddot{f_{B}}H^{3}(j+3q+2)-2\dot{f_{T}}H^{3}(q+1)\end{multlined}-0.5f-H^{2}(q+1)(3f_{B}+2f_{T})+3H^{2}(3f_{B}+2f_{T})\\\
-\ddot{f_{B}}H^{3}(j+3q+2)-2\dot{f_{T}}H^{3}(q+1)\right)\\\
+0.5f-3H^{2}(3f_{B}+2f_{T})+3f_{B}H^{2}(q+1)-3\dot{f_{B}}H^{3}(q+1)\geq
0,\hskip 18.06749pt\text{and}\\\
-H^{2}(q+1)(3f_{B}+2f_{T})+3f_{B}H^{2}(q+1)-3\dot{f_{B}}H^{3}(q+1)-\ddot{f_{B}}H^{3}(j+3q+2)-2\dot{f_{T}}H^{3}(q+1)+0\geq
0.$ (24) $DEC\Longleftrightarrow
0.5f-3H^{2}(-f_{B}(q-2)+\dot{f_{B}}H(q+1)+2f_{T})\geq 0,\hskip
18.06749pt\text{and}\\\
\left(0.5f-3H^{2}(-f_{B}(q-2)+\dot{f_{B}}H(q+1)+2f_{T})\right)\\\
\pm\left(H^{2}(-(3f_{B}(q-2)+H(\ddot{f_{B}}(j+3q+2)+2\dot{f_{T}}(q+1))+2f_{T}(q-2)))-0.5f\right)\geq
0.$ (25)

##  IV Constraints on $f(T,B)$ Gravity Models

In this section I shall constrain some well motivated $f(T,B)$ gravity models
from energy conditions. Note that current cosmological observations indicate
$\omega=p_{de}/\rho_{de}=-1.03\pm 0.03$ planck . Hence, the SEC should violate
under such conditions as $\rho_{de}+3\omega\rho_{de}<0$ at the present epoch.
Additionally, the WEC must assume values close to zero. Therefore, I focus
primarily on the values of the free parameters in $f(T,B)$ gravity models for
which the energy density remains positive and the WEC remains positive but
very close to zero. For the analysis, I shall use $H_{0}=0.692$,
$q_{0}=-0.545$, $j_{0}=0.776$, and $s_{0}=-0.192$ cap .

###  IV.1 Power Law Model: $f(T,B)=\alpha B^{n}+\beta T^{m}$

For the first case, I use the $f(T,B)$ gravity model of the form
$f(T,B)=\alpha B^{n}+\beta T^{m}$ introduced in no  where $\alpha,\beta,n$ and
$m$ are free parameters. For $n=1$, the model reduces to $f(T,B)=\alpha
B+\beta T^{m}$ which is equivalent to a power-law $f(T)$ gravity model since
$B$ is a boundary term and therefore any linear functional form of $B$ does
not introduce changes in the field equations. Note that since there are four
free parameters, constraints on the free parameters cannot be yielded
analytically. Therefore, I assume some rational values for which the WEC
remains positive but very close to zero.
The WEC for this model can be written as:

$WEC\Longleftrightarrow 0.5\left(\beta 6^{m}\left(H^{2}\right)^{m}+\alpha
6^{n}\left(3H^{2}-H^{2}(q+1)\right)^{n}\right)\\\ -3H^{2}\left(\beta
2^{m}3^{m-1}m\left(H^{2}\right)^{m-1}+\alpha
2^{n-1}3^{n}n\left(3H^{2}-H^{2}(q+1)\right)^{n-1}\right)\\\ +\alpha
H^{2}2^{n-1}3^{n}n(q+1)\left(3H^{2}-H^{2}(q+1)\right)^{n-1}\\\ +\alpha
H^{3}\left(-2^{n-1}\right)3^{n}(n-1)n(q+1)(6H-2H(q+1))\left(3H^{2}-H^{2}(q+1)\right)^{n-2}\geq
0,\hskip 7.22743pt\\\ \text{and}\\\ -H^{2}(q+1)\left(\beta
2^{m}3^{m-1}m\left(H^{2}\right)^{m-1}+\alpha
2^{n-1}3^{n}n\left(3H^{2}-H^{2}(q+1)\right)^{n-1}\right)\\\ +\alpha
H^{2}2^{n-1}3^{n}n(q+1)\left(3H^{2}-H^{2}(q+1)\right)^{n-1}\\\ +\beta
H^{4}\left(-2^{m+1}\right)3^{m-1}(m-1)m(q+1)\left(H^{2}\right)^{m-2}-\alpha
H^{3}6^{n-1}n(j+3q+2)\\\
\left(\begin{multlined}(n-2)(n-1)(6H-2H(q+1))^{2}\left(3H^{2}-H^{2}(q+1)\right)^{n-3}\\\
+(n-1)(6-2(q+1))\left(3H^{2}-H^{2}(q+1)\right)^{n-2}\end{multlined}(n-2)(n-1)(6H-2H(q+1))^{2}\left(3H^{2}-H^{2}(q+1)\right)^{n-3}\\\
+(n-1)(6-2(q+1))\left(3H^{2}-H^{2}(q+1)\right)^{n-2}\right)-\\\ \alpha
H^{3}2^{n-1}3^{n}(n-1)n(q+1)(6H-2H(q+1))\left(3H^{2}-H^{2}(q+1)\right)^{n-2}\geq
0.$ (26)

For this model, upon substituting $\alpha=5$, $\beta=-0.1$, $n=0.1$ and
$m=2.3$, the WEC $(\rho_{0}+p_{0})\simeq 0.09$ and therefore compatible with
current observational constraints.

###  IV.2 Mixed Power Law Model: $f(T,B)=\alpha B^{n}T^{m}$

For the second case, I use $f(T,B)=\alpha B^{n}T^{m}$ introduced in no  where
the authors adopted Noether Symmetry Approach to reconstruct the cosmological
solutions. In this model $\alpha\neq 0$, $m\neq 0$ and $n$ are free
parameters. The authors reported the constraint $n=1-m$ for which the
cosmological solution is given as $a(t)=a_{0}t^{(1+n)/3}$. Trivial cases like
$m=0$ should be avoided. For this model, I use the constraint on $n$ and $m$
reported in no  and check the viability of this cosmological model against
energy conditions.
The WEC for this model reads:

$WEC\Longleftrightarrow
0.5\alpha\left(H^{2}\right)^{m}6^{m+n}\left(3H^{2}-H^{2}(q+1)\right)^{n}\\\
+\alpha
n(q+1)\left(H^{2}\right)^{m+1}2^{m+n-1}3^{m+n}\left(3H^{2}-H^{2}(q+1)\right)^{n-1}\\\
-3H^{2}\left(\begin{multlined}\alpha
m\left(H^{2}\right)^{m-1}2^{m+n}3^{m+n-1}\left(3H^{2}-H^{2}(q+1)\right)^{n}\\\
+\alpha
n\left(H^{2}\right)^{m}2^{m+n-1}3^{m+n}\left(3H^{2}-H^{2}(q+1)\right)^{n-1}\end{multlined}\alpha
m\left(H^{2}\right)^{m-1}2^{m+n}3^{m+n-1}\left(3H^{2}-H^{2}(q+1)\right)^{n}\\\
+\alpha
n\left(H^{2}\right)^{m}2^{m+n-1}3^{m+n}\left(3H^{2}-H^{2}(q+1)\right)^{n-1}\right)\\\
-3H^{3}(q+1)\left(\begin{multlined}\alpha
Hmn\left(H^{2}\right)^{m-1}2^{m+n}3^{m+n-1}\left(3H^{2}-H^{2}(q+1)\right)^{n-1}\\\
+\alpha(n-1)n\left(H^{2}\right)^{m}(6H-2H(q+1))6^{m+n-1}\left(3H^{2}-H^{2}(q+1)\right)^{n-2}\end{multlined}\alpha
Hmn\left(H^{2}\right)^{m-1}2^{m+n}3^{m+n-1}\left(3H^{2}-H^{2}(q+1)\right)^{n-1}\\\
+\alpha(n-1)n\left(H^{2}\right)^{m}(6H-2H(q+1))6^{m+n-1}\left(3H^{2}-H^{2}(q+1)\right)^{n-2}\right)\geq
0,\hskip 21.68121pt\\\ \text{and}\\\ \left(\alpha
H\left(H^{2}\right)^{m}\left(-2^{m+n}\right)3^{m+n-1}\right)\left(-H^{2}(q-2)\right)^{n-1}\\\
\times\left(\begin{multlined}n(j+3q+2)\left(2m^{2}+m(4n-5)+2n^{2}-5n+3\right)\\\
-H(q+1)\left(2m^{2}(q-2)+m(n(2q-7)-q+2)-3(n-1)n\right)\end{multlined}n(j+3q+2)\left(2m^{2}+m(4n-5)+2n^{2}-5n+3\right)\\\
-H(q+1)\left(2m^{2}(q-2)+m(n(2q-7)-q+2)-3(n-1)n\right)\right)\geq 0$ (27)

In this case, I substitute $\alpha=-1$, $m=0.2$ and $n=1-m=0.8$, to obtain WEC
$(\rho_{0}+p_{0})\simeq 0.07$. The WEC in this case is obeyed and consistent
with observations.

###  IV.3 Logarithmic Model: $f(T,B)=\alpha\log(B)+\beta T$

For the third case, I propose a novel cosmological model of the form
$f(T,B)=\alpha\log(B)+\beta T$ where $\alpha\neq 0$ and $\beta\neq 0$ are free
parameters. Since the model has only two free parameters, I find an analytical
expression for which the WEC is obeyed.
The WEC for this model is given as:

$WEC\Longleftrightarrow-3H^{2}\left(2\beta+\frac{\alpha}{2\left(3H^{2}-H^{2}(q+1)\right)}\right)+0.5\left(6\beta
H^{2}+\alpha\log\left(6\left(3H^{2}-H^{2}(q+1)\right)\right)\right)\\\
+\frac{\alpha H^{2}(q+1)}{2\left(3H^{2}-H^{2}(q+1)\right)}+\frac{\alpha
H^{3}(q+1)(6H-2H(q+1))}{2\left(3H^{2}-H^{2}(q+1)\right)^{2}}\geq 0,\\\
\text{and}\\\
-H^{2}(q+1)\left(2\beta+\frac{\alpha}{2\left(3H^{2}-H^{2}(q+1)\right)}\right)+\frac{\alpha
H^{2}(q+1)}{2\left(3H^{2}-H^{2}(q+1)\right)}\\\ -\frac{1}{6}\alpha
H^{3}\left(\frac{2(6H-2H(q+1))^{2}}{\left(3H^{2}-H^{2}(q+1)\right)^{3}}-\frac{6-2(q+1)}{\left(3H^{2}-H^{2}(q+1)\right)^{2}}\right)(j+3q+2)\\\
+\frac{\alpha H^{3}(q+1)(6H-2H(q+1))}{2\left(3H^{2}-H^{2}(q+1)\right)^{2}}\geq
0.$ (28)

Upon substituting the respective values of $H_{0}$, $j_{0}$ and $s_{0}$, the
constraints on $\alpha$ and $\beta$ for the validation of the WEC
($\rho_{0}+p_{0}\geq 0$) reads

$\frac{\alpha}{\beta}\gtrsim-0.2$ (29)

For this model, I substitute $\alpha=0.1$ and $\beta=-0.5$ to obtain
$\rho_{0}+p_{0}\simeq 0.0017$ which is in excellent agreement with
observations.

##  V Conclusions

Recent cosmological observations make it clear-cut that the universe is
undergoing an accelerated expansion by virtue of the so-called dark energy.
Furthermore, galactic rotational curves and gravitational lensing experiments
hint at the existence of a massive abundance of non-baryonic dark matter.
There is no general consensus about the nature of these enigmatic quantities
which together makes about 95% of the energy budget of the universe. To
explain these eccentric cosmological observations, viable cosmological models
which are either adhered to general relativity or infra-red modifications of
general relativity have been proposed and are currently being investigated to
understand their viability and applicability.
Modified theories of gravity are geometrical extensions of general relativity
and have widespread use in modern cosmology. The cosmological models
reconstructed upon these extended theories of gravity have been able to
explain inflation, baryon asymmetry, coincidence problem and the cosmic
acceleration without the assistance of dark energy. Interestingly, these
models under certain conditions can also avoid the initial big bang
singularity and explain the flat rotational curves without requiring dark
matter. Many of these extended theories of gravity have been constrained from
the big-bang nucleosynthesis, redshift drift, supernovae, Planck and other
datasets to obtain the range in parameter spaces.
In this work, I investigate the viability of some well motivated $f(T,B)$
teleparallel gravity models from the energy conditions. $f(T,B)$ is a recently
proposed straightforward generalization of the popular $f(T)$ teleparallel
gravity theory by the incorporation of a boundary term
$B=\frac{2}{e}\partial_{i}(eT^{i})=\bigtriangledown_{i}T^{i}$. Through the
addition of the boundary term $B$, $f(T)$ gravity becomes a generalized metric
counterpart of $f(R)$ gravity since for $f(T,B)=f(-T+B)=f(R)$ no .
I find that for all the cosmological models investigated in this study, there
exists corners in parameter spaces for which the weak energy condition attains
a minute positive value to suffice the late-time acceleration. Note that every
model under consideration predicts a violation of the strong energy condition
at the present epoch.
However, as first reported in ecfr  and further discusssed in ecfg , issues
regarding the application of energy conditions in modified theories of gravity
is an open interrogation, which eventually relates to the confrontation
between theory and observations.
As a possible extension, readers are encouraged to employ the constraints on
model parameters obtained from the work in other cosmological scenarios such
as gravitational baryogenesis, inflation and late time acceleration to
investigate the cosmological viability and applicability of $f(T,B)$ gravity
in the era of precision cosmology.

## Acknowledgments

I thank the referee for his or her suggestions.

## References

  * (1) Riess,A.G., et al.,”Observational Evidence from Supernovae for an Accelerating Universe and a Cosmological Constant”, Astron. J. 116, 1009 (1998); Perlmutter, S., et al., ”Measurements of Omega and Lambda from 42 High-Redshift Supernovae”,Astrophys. J. 517, 565 (1999).
  * (2) Bengochea, G.R and Ferraro, R,”Dark torsion as the cosmic speed-up” Phys. Rev. D 79 124019 (2009); Böhmer, C.G., Harko, T. and Lobo, F. S. N,”Wormhole geometries in modified teleparallel gravity and the energy conditions”, Phys. Rev. D 85 044033 (2012); Sadjadi, H.M, ” Generalized Noether symmetry in $f(T)$ gravity” Phys. Lett. B 718 270 (2012); Wei, H., Guo, X-J. and Wang, L-F, ”Noether Symmetry in $f(T)$ Theory”,Phys. Lett. B 707 298 (2012).
  * (3) Mandal, S. et. al, ”Accelerating Universe in Hybrid and Logarithmic Teleparallel Gravity”, Physics of the Dark Universe, 28 (2020) 100551; arXiv:2004.08211.
  * (4) Bhattacharjee,S. , Sahoo, P.K., ”Baryogenesis in $f(Q,T)$ Gravity”, Eur. Phys. J. C 80(3), (2020) 289; arXiv:2002.11483.
  * (5) Bhattacharjee,S.,”Gravitational baryogenesis in extended teleparallel theories of gravity”, Physics of the Dark Universe, 30 (2020) 100612; arXiv:2005.05534.
  * (6) Bahamonde, S., Böhmer, C.G. and Wright, M, ”Modified teleparallel theories of gravity”,Phys. Rev. D 92, 104042 (2015);
  * (7) Planck Collaboration: ”Planck 2018 results. VI. Cosmological parameters”, arXiv:1807.06209.
  * (8) Bahamonde, S. et.al.,”Thermodynamics and cosmological reconstruction in $f(T,B)$ gravity” ,arXiv:1609.08373v2.
  * (9) Garcia N.M., et al., ”Energy conditions in modified Gauss-Bonnet gravity”, Phys.Rev.D 83 104032 (2011).
  * (10) Atazadeh, K., Darabi, F., ”Energy conditions in $f(R,G)$ gravity”,Gen. Relativ. Gravit. 46 1664 (2014)
  * (11) Capozziello S., et al.,”Cosmic acceleration in non-flat $f(T)$ cosmology”, Gen Relativ Gravit 50, 53 (2018).
  * (12) Liu,Di, Reboucas,M. J., ”Energy conditions bounds on $f(T)$ gravity”,Phys.Rev. D 86 083515 (2012).
  * (13) Santos J., et al.,”Energy conditions in $f(R)$ gravity” ,Phys.Rev.D 76, 083513 (2007).
  * (14) Alvarenga F. G., et al., ”Testing Some $f(R,T)$ Gravity Models from Energy Conditions ”, Journal of Modern Physics, 4, 130-139 (2013).
  * (15) Hawking,S. W., and Ellis,G.F.R., ”The Large Scale Structure of Spacetime”,(Cambridge University Press, England, 1973).
  * (16) Bahamonde,S., and Capozziello,S., ”Noether symmetry approach in $f(T,B)$ teleparallel cosmology” ,Eur. Phys. J. C 77 107 (2017).
  * (17) Moraes, P. H. R. S.,Sahoo,P. K., ”The simplest non-minimal matter-geometry coupling in the $f(R,T)$ cosmology”,Eur. Phys. J. C. 77, 480 (2017).
  * (18) Wald,R. M., ”General relativity” (University of Chicago Press, Chicago, 1984)
  * (19) Capozziello,S., Capriolo,M., Caso,L., ”Weak field limit and gravitational waves in $f(T,B)$ teleparallel gravity”, Eur. Phys. J. C 80, 156 (2020).
  * (20) Garci’a, N. M., et.al., ”$f(G)$ modified gravity and the energy conditions”,J. Phys. Conf. Ser. 314, 012060 (2011).
  * (21) Capozziello S., et al.,”Cosmography in $f(T)$ gravity”, Phys.Rev.D 84, 043527 (2011).
  * (22) Gong,Y., Wang, A., ”Energy conditions and current acceleration of the universe” ,Phys. Lett. B 652 (2007) 63.
  * (23) Jamil, M., et al.,”Energy conditions in generalized teleparallel gravity models”, GRG, 45, 263 (2013)
  * (24) Capozziello, S., et al.,”Extended gravity cosmography” , IJMPD 28, 10, 1930016 (2019).
  * (25) Z. Yousaf et al., ”The Influence of Modification of Gravity on the Dynamics of Radiating Spherical Fluids”, Phys. Rev. D 93, 064059 (2016); Z. Yousaf et al., ”Causes of Irregular Energy Density in $f(R,T)$ Gravity”, Phys. Rev. D 93, 124048 (2016); Z. Yousaf et al.,”Charged Gravastars in Modified Gravity”, Phys. Rev. D 100, 024062 (2019).
  * (26) P.K. Sahoo, S. Bhattacharjee, ”Revisiting The Coincidence Problem in $f(R)$ Gravitation” New Astronomy, 77 (2020), 101351.
  * (27) S. Arora, S. K. J. Pacif, S. Bhattacharjee, P.K. Sahoo, ”$f(Q,T)$ gravity models with observational constraints”, Physics of the Dark Universe, 30 (2020) 100664.


# Fault-Tolerant Distance Labeling for Planar Graphs

Aviv Bar-Natan  University of Haifa, Israel
<EMAIL_ADDRESS><EMAIL_ADDRESS>Panagiotis Charalampopoulos  The
Interdisciplinary Center Herzliya, Israel
<EMAIL_ADDRESS><EMAIL_ADDRESS>Paweł
Gawrychowski  University of Wrocław, Poland
<EMAIL_ADDRESS>Shay Mozes  The Interdisciplinary Center Herzliya, Israel
<EMAIL_ADDRESS><EMAIL_ADDRESS>Oren Weimann
University of Haifa, Israel
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In fault-tolerant distance labeling we wish to assign short labels to the
vertices of a graph $G$ such that from the labels of any three vertices
$u,v,f$ we can infer the $u$-to-$v$ distance in the graph $G\setminus\\{f\\}$.
We show that any directed weighted planar graph (and in fact any graph in a
graph family with $O(\sqrt{n})$-size separators, such as minor-free graphs)
admits fault-tolerant distance labels of size $O(n^{2/3})$. We extend these
labels in a way that allows us to also count the number of shortest paths, and
provide additional upper and lower bounds for labels and oracles for counting
shortest paths.

##  1 Introduction

Computing distances in graphs is one of the most basic and important problems
in graphs theory, both from theoretical and practical points of view. In this
work we consider distance labeling schemes, in which one preprocesses a
network to assign labels to the vertices, so that the distance between any two
vertices $u$ and $v$ can be recovered from just the labels of $u$ and $v$ (and
no other information). The main criteria of interest are foremost the size of
the label, and to a lesser extent the time it takes to recover the distance
from a given pair of labels (query time). Distance labeling schemes are useful
in the distributed setting, where it is advantageous to be able to infer
distances based only on local information such as the labels of the source and
destination. This is the case in communication networks or in disaster
stricken areas, where communication with a centralized entity is infeasible or
downright impossible.

Considering the latter scenario of disaster management, it is not only likely
that a disastrous event makes communication with a centralized entity
impossible, but also that parts of the network are affected by the disaster,
and that only shortest paths that avoid affected parts of the network should
be considered when computing distances. Forbidden-set distance labeling
schemes assign labels to vertices, so that, for any pair of vertices $u$ and
$v$, and any set $F$ of failed vertices, the length of a shortest $u$-to-$v$
path that avoids all vertices in $F$ can be recovered just from the labels of
$u$, $v$, and of the vertices in $F$. In this work we study forbidden-set
distance labeling schemes in directed planar networks. We also study the
extension of such schemes to capture not only the distance from $u$ to $v$,
but also the number of distinct $u$-to-$v$ shortest paths.

For unweighted (i.e., unit-weight) graphs, we measure the label size in bits.
For weighted graphs and queries concerning lengths of the shortest paths, we
assume that the distance between any two nodes fits in a single machine words,
and measure the label size in words. For queries concerning the number of
shortest paths, unless mentioned otherwise, we assume that the number of
shortest paths between any two nodes fits in a single machine word, and
measure the label size in words.

###  1.1 Related work

Labeling schemes provide a clean and natural model for studying how to
distribute information about a graph. Problems considered in this model
include adjacency [31, 6, 43, 7, 5, 10], flows and connectivity [33, 28, 37],
and Steiner tree [42]. See [44] for a recent survey. We specifically focus on
distance labeling schemes.

#### Distance labeling schemes.

Embedding distance information into labels was studied by Graham and Pollack
[25] in the 1970’s in what was termed the squashed cube model. In 2000, Peleg
[41] formalized the notion of distance labeling schemes, and provided schemes
with polylogarithmic label size (number of bits) and query time for trees,
interval graphs and permutation graphs. Gavoille et al. [22] showed that for
general graphs, the label size is $\Theta(n)$, and for trees,
$\Theta(\log^{2}n)$. For (unit-weight) planar graphs they showed a lower bound
of $\Omega(n^{1/3})$, and an upper bound of $O(\sqrt{n}\log n)$ bits. The
upper bound was recently improved to $O(\sqrt{n})$ [24], but the rare
_polynomial_ gap between the lower and upper bound remains an interesting and
important open problem. For weighted planar graphs Gavoille et al. gave tight
(up to polylogarithmic factors) $\tilde{\Theta}(n^{1/2})$ upper and lower
bounds.

#### Approximate distance labeling schemes.

Since exact distance labels typically require polynomial size labels [22],
researchers have sought smaller labels that yield approximate distances.
Gavoille et al. [21] studied such labels for general graphs and various graph
families. Specifically, for planar graphs, they presented $O(n^{1/3}\log
n)$-bit labels that provide a 3-approximation of the distance. In the same
year, Gupta et al. [26] presented smaller 3-approximate labels, requiring only
$O(\log^{2}n)$ bits, and Thorup gave $(1+\epsilon)$-approximate labels of size
$O(\log n/\epsilon)$, for any fixed $\epsilon>0$ [45]. The latter result was
generalized to $H$-minor free graphs by Abraham and Gavoille in [4].

#### Forbidden-set distance labeling schemes.

Forbidden-set labels were introduced in the context of routing labels by
Feigenbaum et al. [18, 19], and studied by several others [46, 14, 15, 3, 2].
Exact forbidden-set labeling schemes of polylogarithmic size are given in [46,
15] for graphs of bounded treewidth or cliquewidth. For unweighted graphs of
bounded doubling dimension, forbidden-set labels with polylogarithmic size and
$(1+\epsilon)$-stretch are also known [3]. For undirected planar graphs, and
for any fixed $\epsilon>0$, Abraham et al. [2] presented a forbidden-set
labeling scheme of polylogarithmic size such that a
$(1+\epsilon)$-approximation of the shortest path between vertices $u$ and $v$
that avoids a set $F$ of failed vertices can be recovered from the labels of
$u,v,$ and the labels of the failed vertices in $\tilde{O}(|F|^{2})$
time.111The $\tilde{O}(\cdot)$ notation suppresses $\log^{O(1)}n$ factors.

#### Other related work.

There are many other concepts related to distances in the presence of
failures. In the replacement paths problem we are given a graph along with a
source and sink vertices, and the goal is to efficiently compute all shortest
paths between the source and the destinations for every possible single-edge
failure in the graph. In planar graphs this problem can be solved in nearly
linear time [16, 36, 47]. For the single source, single failure version of the
problem (i.e. when only the source vertex is fixed at construction time, and
the query specifies just the target and a single failed vertex), Baswana et
al. [8] presented an oracle with size and construction time $O(n\log^{4}n)$
that answers queries in $O(\log^{3}n)$ time. Building upon this oracle, they
then present an oracle of size $\tilde{O}(n^{2}/q)$ supporting arbitrary
distance queries subject to a single failure in time $\tilde{O}(q)$ for any
$q\in[1,n^{1/2}]$. The authors of [13] show how to construct in $\tilde{O}(n)$
time an oracle of size $\tilde{O}(n)$ that, given a source vertex $u$, a
target vertex $v$, and a set $F$ of $k$ faulty vertices, reports the length of
a shortest $u$-to-$v$ path in $G\setminus F$ in $\tilde{O}(\sqrt{kn})$ time.
They further show that for any $r\in[1,n]$ there exists an
$\tilde{O}(\frac{n^{k+1}}{r^{k+1}}\sqrt{nr})$-size oracle that answers queries
in time $\tilde{O}(k\sqrt{r})$. Recently, Italiano et al. [29] gave an oracle
of size $O(n\log n)$ and construction time $O(n\log^{2}n/\log\log n)$ that
supports reachability queries subject to a single failure in time $O(\log n)$.

Another related concept is that of dynamic distance oracles. Here a graph is
preprocessed so as to efficiently support distance queries between arbitrary
pairs of vertices as well as updates to the graph. Updates may include
deletion of edges or vertices (decremental updates), or also addition of new
edges and vertices (fully dynamic). Fakcharoenphol and Rao [17] presented
distance oracles that require $\tilde{O}(n^{2/3})$ and $\tilde{O}(n^{4/5})$
amortized time per update and query for non-negative and arbitrary edge-weight
updates respectively.222Though this is not mentioned in [17], the query time
can be made worst case rather than amortized by standard techniques. The space
required by these oracles is $O(n\log n)$. The extensions of this result in
[34, 30, 32, 13] yield a dynamic oracle that can handle arbitrary edge weight
updates, edge deletions and insertions (not violating the planarity of the
embedding) and vertex deletions, as well as answer distance queries, in
$\tilde{O}(n^{2/3})$ time each.

#### Counting shortest paths.

In the (non-faulty) counting version of shortest paths labeling, given the
labels of vertices $s$ and $t$ we wish to return the number of shortest
$s$-to-$t$ paths in $G$ (i.e. paths whose length is equal to $d(s,t)$). This
problem (without faults) was recently studied in [9] where labels333In [9],
the authors actually considered the oracle version of the problem, but their
solution can be easily applied for labeling as well. of size
$\Theta(\sqrt{n})$ were constructed under the assumption that the number of
shortest paths between any two nodes fits in a constant number of machine
words. In the general case where the numbers consist of $L$ bits, the obtained
labels consist of $O(\sqrt{n}\cdot L)$ bits. As already observed in [9], it is
easy to construct an unweighted graph where $L=n-1$ making the labels consist
of $\Theta(n^{1.5})$ bits, that is, more than in a naive encoding storing the
whole graph in every label. However, the following simple construction shows
that we cannot hope to construct labels consisting of $o(n)$ bits without
bounding $L$: given $n$ bits $b_{0},\ldots,b_{n-1}$ we construct a graph
consisting of a path $s=u_{0}-u_{1}-\cdots-u_{n-1}$ and another path
$v_{1}-v_{2}-\cdots-v_{n}=t$ in which every edge is duplicated (i.e., there
are two parallel edges between each pair $v_{i},v_{i+1}$). Finally, for every
$i=0,\ldots,n-1$ such that $b_{i}=1$, we add an edge $u_{i}-v_{i+1}$. Then the
number of shortest $s$-to-$t$ paths is exactly $\sum_{i=0}^{n-1}b_{i}\cdot
2^{n-1-i}$, and so by an encoding argument the total number of bits in the
labels of $s$ and $t$ must be at least $n$. Therefore, when counting shortest
paths we will measure the size of a label in the number of machine words, each
long enough to store the number of shortest paths between any two nodes in the
graph.

We highlight one interesting application where our scheme for counting
shortest $s$-to-$t$ paths that avoid nodes $v_{1},v_{2},\ldots,v_{k}$ can be
modified to obtain a better bound on the sizes of the labels in bits. Say that
instead of counting such shortest paths we would like to check if avoiding
nodes $v_{1},v_{2},\ldots,v_{k}$ increases the length of the shortest path. In
such case, we only need to check if the number of shortest $s$-to-$t$ paths
that avoid nodes $v_{1},v_{2},\ldots,v_{k}$ is nonzero. Because the number of
shortest paths is always at most $2^{n}$, by well known properties of prime
numbers, choosing a random prime $p$ consisting of $\Theta(k\cdot\log n)$ bits
guarantees that with high probability, for every
$s,t,v_{1},v_{2},\ldots,v_{k}$, the number of shortest paths counted modulo
$p$ is nonzero if and only if the number of shortest paths is nonzero. Our
scheme (as well as the scheme of [9]) can be used for counting modulo $p$, so
we obtain labels consisting of $\tilde{O}(\sqrt{n}\cdot k)$ bits for such
queries.

###  1.2 Our results

  * •

In Section 3 we present a single-fault distance labeling scheme (forbidden-set
labeling scheme for a set of cardinality 1). The label size is $O(n^{2/3})$,
the query time is $\tilde{O}(\sqrt{n})$, and time to construct all labels is
$\tilde{O}(n^{5/3})$. Our labeling scheme extends (with no overhead in the
label size) to a labeling scheme for counting shortest paths (with a single
fault).

  * •

In Section 4 we extend the counting labels of [9] to the following fault-
tolerant variant. Given the labels of vertices $s,t,v_{1},v_{2},\ldots,v_{k}$,
we wish to return the number of $s$-to-$t$ paths that avoid vertices
$v_{1},\ldots,v_{k}$ and whose length is equal to $d(s,t)$ (the original
$s$-to-$t$ distance in $G$). We show that the labeling of [9] (with labels of
size $\tilde{O}(\sqrt{n})$) actually works in this more general setting. A
naive query to such labeling takes $\tilde{O}(\sqrt{n}\cdot k^{2})$ time, we
show how to improve this to $\tilde{O}(\sqrt{n}\cdot k)$.

  * •

In Section 5 we show a lower bound of $\Omega(\sqrt{nL})$ on the label-size
(in bits) for counting shortest paths (without faults), in graphs in which the
number of distinct shortest paths between any two nodes consists of at most
$L$ bits.

  * •

In Section 6 we show a lower bound on dynamic oracles for counting shortest
paths, conditioned on the hardness of online boolean matrix-vector
multiplication. We prove that for any dynamic shortest paths counting oracle
in undirected planar graphs, either the query time or the update time must be
$\Omega(\sqrt{n})$ (up to subpolynomial factors).

We focus on planar graphs but in fact all our results (except for the
efficient preprocessing time and query time in Section 3) hold for any graph
family with $O(\sqrt{n})$-size separators (such as $H$-minor free graphs and
bounded genus graphs). This is also the case for the standard (i.e. without
failures) labeling scheme of Gavoille et al. [22]. However, while their
$\tilde{O}(n^{1/2})$-size labels are obtained with a straightforward
application of separators, our $O(n^{2/3})$-size (fault-tolerant) labels are
obtained with a non-standard and intricate use of separators.

A main open question that is left unanswered by our work is the existence of
non-trivial forbidden-set distance labels tolerating more than a single fault.
Labels for approximate distances [2] also rely on separators, and do handle
multiple failures. In the failure-free case, the labels of [2] consist of
distances to a small (logarithmic) sample of vertices on some separators,
called connections. To handle failures, the label of each vertex $u$ also
stores the failure-free labels of the connections of $u$. This only increases
the label-size by a polylogarithmic factor. In case of exact distances, the
size of the failure-free labels is $\Omega(\sqrt{n})$, so this approach seems
unsuitable.

Another natural open question is whether the gap between our $O(n^{2/3})$-size
fault-tolerant labels and the $\tilde{O}(n^{1/2})$-size labels without
failures is actually required and tight. We observe that the existing lower
bound technique of Gavoille et al. cannot be extended to show a lower bound
above $\Omega(\sqrt{n})$ for fault-tolerant labels. The reason is that their
technique uses a global argument showing that if we wish to encode the
distances between a subset $S$ of $k\leq\sqrt{n}$ vertices then all their
labels together require size $\Omega(k^{2})$. However, even in the presence of
(any number of) failures, encoding distances can be done with total size
$\tilde{O}(k^{2})$ (simply store for every $u,v\in S$ the length of the
shortest $u$-to-$v$ path that is internally disjoint from $S$).

##  2 Preliminaries

Throughout the paper we consider as input a weighted directed planar graph
$G$, embedded in the plane. We assume that the input graph has no negative
length cycles. We can transform the graph in a standard way, in
$O(n\frac{\log^{2}n}{\log\log n})$ time, so that all edge weights are non-
negative and distances are preserved [40].

#### Separators and recursive decompositions.

Miller [38] showed how to compute a Jordan curve that intersects the graph at
a set of nodes $Sep(G)$ of size $O(\sqrt{n})$ and separates $G$ into two
pieces with at most $2n/3$ vertices each. Jordan curve separators can be used
to recursively separate a planar graph until pieces have constant size. The
authors of [35] show how to obtain a complete recursive decomposition tree
$\mathcal{T}$ of $G$ in $O(n)$ time. $\mathcal{T}$ is a binary tree whose
nodes correspond to subgraphs of $G$ (called pieces), with the root being all
of $G$ and the leaves being pieces of constant size. We identify each piece
$P$ with the node representing it in $\mathcal{T}$ (we can thus abuse notation
and write $P\in\mathcal{T}$), with its boundary $\partial P$ (i.e. vertices
that belong to some separator along the recursive decomposition used to obtain
$P$), and with its separator $Sep(P)$. We denote by $\mathcal{T}[P,Q]$ the
$P$-to-$Q$ path in $\mathcal{T}$ (and also use $\mathcal{T}(P,Q]$,
$\mathcal{T}[P,Q)$, and $\mathcal{T}(P,Q)$).

An _$r$ -division_ [20] of a planar graph, for $r\in[1,n]$, is a decomposition
of the graph into $O(n/r)$ pieces, each of size $O(r)$, such that each piece
$P$ has $O(\sqrt{r})$ boundary vertices (denoted $\partial P$). Another
desired property of an $r$-division is that the boundary vertices lie on a
constant number of faces (called holes) of the piece. For every $r$ larger
than some constant, an $r$-division with few holes is represented in the
decomposition tree $\mathcal{T}$ of [35]. It is convenient to describe the
$r$-division by truncating $\mathcal{T}$ at pieces of size $O(r)$, that also
satisfy the other required properties. We refer to those pieces (the leaves of
$\mathcal{T}$ after truncation) as regions and denote by $R_{u}$ the region
containing vertex $u$ (if $u$ belongs to multiple regions, we arbitrarily
designate one of them as $R_{u}$).

#### Dense distance graphs and FR-Dijkstra.

The _dense distance graph_ of a set of vertices $U$ that lie on a constant
number of faces of a planar graph $H$, denoted $DDG_{H}(U)$ is a complete
directed graph on the vertices of $U$. Each edge $(u,v)$ has weight
$d_{H}(u,v)$, equal to the length of the shortest $u$-to-$v$ path in $H$.
$DDG_{H}(U)$ can be computed in time $O((|U|^{2}+|H|)\log|H|)$ using the
multiple source shortest paths (MSSP) algorithm [34, 11]. Thus, computing
$DDG_{P}(\partial P)$ over all pieces of the recursive decomposition of $G$
requires time $O(n\log^{2}n)$ and space $O(n\log n)$. We next give a
–convenient for our purposes– interface for FR-Dijkstra [17], which is an
efficient implementation of Dijkstra’s algorithm on any union of $DDG$s. The
algorithm exploits the fact that, due to planarity, certain submatrices of the
adjacency matrix of $DDG_{H}(U)$ satisfy the Monge property. (A matrix $M$
satisfies the Monge property if, for all $i<i^{\prime}$ and $j<j^{\prime}$,
$M_{i,j}+M_{i^{\prime},j^{\prime}}\leq M_{i^{\prime},j}+M_{i,j^{\prime}}$
[39].) The interface is specified in the following theorem, which was
essentially proved in [17], with some additional components and details from
[32, 40].

######  Theorem 1 ([17, 32, 40]).

Given a set $Y$ of $DDG$s, Dijkstra’s algorithm can be run on the union of any
subset of $Y$ with $O(N)$ vertices in total (with multiplicities) and an
arbitrary set of $O(N)$ extra edges in time $O(N\log^{2}N)$.

##  3 Single-Fault Labeling for Reporting Shortest Paths

#### Warm-up.

As a warm-up, we first sketch a simple labeling scheme that assigns a label of
size $O(n^{4/5})$ to each vertex. Consider an $r$-division for $r=n^{4/5}$,
and let $\mathcal{R}$ be the set of its regions. The label of each vertex $u$
consists of the following:

  1. (a)

The $r$-division $\mathcal{R}$. Space: $O(n/r)$.

  2. (b)

For each region $R$ in the $r$-division, the length of the shortest path in
$G$, among paths that are internally disjoint from $R$, from $u$ to
$\bigcup_{P\in\mathcal{R}}\partial P$, and from
$\bigcup_{P\in\mathcal{R}}\partial P$ to $u$. There are $O(n/r)$ regions and
for each of them we store $O(n/r\cdot\sqrt{r})$ distances. Space:
$O(n^{2}/r^{3/2})$.

  3. (c)

The region $R_{u}$ and the $\partial R_{u}$-to-$\partial R_{u}$ distances in
$G\setminus\\{u\\}$. Space: $O(r)$.

The space is thus $O(n/r+n^{2}/r^{3/2}+r)=O(n^{4/5})$.

Let us now consider a query $(u,v,f)$, and assume, for simplicity, that no two
of $u$, $v$ and $f$ are contained in a single region. We have two cases. If
there is a shortest $u$-to-$v$ path in $G\setminus\\{f\\}$ that is vertex-
disjoint from $R_{f}$, then the $u$-to-$\partial R_{v}$ distances among paths
internally-disjoint from $R_{f}$ (item (b)), together with $R_{v}$, which is
stored for $v$ (item (c)), allow us to retrieve the length of this path. In
the other case, we employ the $u$-to-$\partial R_{f}$ distances among paths
internally-disjoint from $R_{f}$ (item (b)), the information stored in item
(c) for $f$, and the $\partial R_{f}$-to-$v$ distances among paths internally-
disjoint from $R_{f}$ (item (b)).

It is not difficult to combine this approach with the distance-labeling scheme
of Gavoille et al. [22] for the failure-free setting to obtain labels of size
$O(n^{3/4})$. (Item (b) has to be modified to store distances to separators of
ancestors of $R_{u}$ instead of distances to
$\bigcup_{P\in\mathcal{R}}\partial P$, requiring $O(n^{3/2}/r)$ space.) In the
approach that we present below, we rely on separators in a more sophisticated
and delicate manner to obtain labels of size $O(n^{2/3})$.

#### The label.

Recall that an $r$-division is represented by a decomposition tree
$\mathcal{T}$, whose root corresponds to $G$. The internal nodes of
$\mathcal{T}$ correspond to pieces of $G$. The two children of a piece
$P\in\mathcal{T}$ are the subgraphs of $P$ external and internal to $Sep(P)$.
The leaves of $\mathcal{T}$ are the regions of the $r$-division.

The label of each vertex $u$ in $G$ consists of the following information:

  1. (i)

The entire recursive decomposition tree $\mathcal{T}$. Space: $O(n/r)$.

  2. (ii)

For each region $R$ in the $r$-division, the shortest path distances in $G$
from $u$ to $\partial R$ among paths that are internally disjoint from $R$.
There $O(n/r)$ regions and each of them has $O(\sqrt{r})$ boundary nodes.
Space: $O(n/\sqrt{r})$.

  3. (iii)

The region $R_{u}$ and the $\partial R_{u}$-to-$\partial R_{u}$ distances in
$G\setminus\\{u\\}$. Space: $O(r)$.

  4. (iv)

For each piece $P\in\mathcal{T}$ with sibling $Q$, for each $p\in\partial
P\setminus Q$, the shortest path distance from $u$ to $p$ in $G\setminus(P\cup
Q)\cup\\{p\\}$, and the shortest path distance from $p$ to $u$ in $G\setminus
Q$. Space: $O(\sum_{P\in\mathcal{T}}\partial P)=O(n/\sqrt{r})$, c.f. [23].

  5. (v)

For each ancestor piece $P$ of $R_{u}$ in $\mathcal{T}$, for each vertex $p$
of $Sep(P)\setminus\partial P$, the shortest path distance from $u$ to $p$
among paths in $P\setminus\partial P$ that are internally disjoint from
$Sep(P)$, and the shortest path distance in $P\setminus\partial P$ from $p$ to
$u$. Space: $O(\sqrt{n})$, c.f. [23].

The overall space required by the above five items is
$O(n/r+n/\sqrt{r}+r+n/\sqrt{r}+\sqrt{n})$, which is $O(n^{2/3})$ for
$r=n^{2/3}$.

#### The query.

Upon query $(u,v,f)$ we say that a path is a $(u,v,f)$-path if it is a
$u$-to-$v$ path in $G$ that avoids $f$, and we seek the shortest
$(u,v,f)$-path, which we denote by $S$. Let $X$ denote the lowest node in
$\mathcal{T}$ that is an ancestor of $R_{f}$ and of at least one of
$\\{R_{u},R_{v}\\}$. Let us assume without loss of generality that $X$ is an
ancestor of $R_{u}$. We return the minimum of the following three:

  1. 1.

$S$ includes a vertex of $\partial R_{f}$.

The length of this path is found with a SSSP computation on the (non-planar)
graph $G_{1}$ whose vertices are $u,v$, and $\partial R_{f}\setminus\\{f\\}$
and whose edges are in one-to-one correspondence with the distances specified
below, i.e. for each $a$-to-$b$ distance, there is an edge from $a$ to $b$
with length equal to that distance:

     * •

the $u$-to-$\partial R_{f}\setminus\\{f\\}$ distances from item (ii) in $u$’s
label (or the $u$-to-$\partial R_{f}\setminus\\{f\\}$ distances in
$R_{f}\setminus\\{f\\}$, which can be computed from item (iii), if
$R_{u}=R_{f}$);

     * •

the $\partial R_{f}\setminus\\{f\\}$-to-$\partial R_{f}\setminus\\{f\\}$
distances from item (iii) in $f$’s label;

     * •

the $\partial R_{f}\setminus\\{f\\}$-to-$v$ distances from item (ii) in $v$’s
label (or the $\partial R_{f}\setminus\\{f\\}$-to-$v$ distances in
$R_{f}\setminus\\{f\\}$, which can be computed from item (iii), if
$R_{v}=R_{f}$).

  2. 2.

$S$ avoids $R_{f}$ but includes a boundary vertex of some piece on
$\mathcal{T}[X,R_{f}]$.

The length of this path is found with a SSSP computation on the graph $G_{2}$
whose vertices are $u,v$, and $\partial P$ of all nodes $P$ that are siblings
of some node $Q$ on the $X$-to-$R_{f}$ path in $\mathcal{T}$. The edges are in
one-to-one correspondence with the $u$-to-$\partial P$ distances from item
(iv) in $u$’s label and the $\partial P$-to-$v$ distances from item (iv) in
$v$’s label.

  3. 3.

$S$ avoids all boundary vertices of all the pieces on $\mathcal{T}[X,R_{f}]$.

This is required only for the case where the lowest common ancestor of $R_{u}$
and $R_{v}$ is not an ancestor of $R_{f}$ (otherwise, it is an ancestor of $X$
and a $u$-to-$v$ path cannot avoid the boundary vertices of $X$). The length
of this path is found with a SSSP computation on the graph $G_{3}$ whose
vertices are $u,v$, and $Sep(P)\setminus\partial P$ of all nodes $P$ on
$\mathcal{T}(X,R_{u})$. The edges are in one-to-one correspondence with the
$u$-to-$Sep(P)$ distances from item (v) in $u$’s label and the $Sep(P)$-to-$v$
distances from item (v) in $v$’s label. If $R_{u}=R_{v}$, the shortest path
may not cross any of these separators; in that case the distance may be
retrieved by a single SSSP computation in $R_{u}\setminus\\{f\\}$ (item
(iii)).

#### Correctness.

Let us consider the three options for the shortest $(u,v,f)$-path $S$ (an
illustration is provided in Figure 1).

  1. 1.

$S$ includes a vertex of $\partial R_{f}$. Let $a$ (resp. $b$) denote the
first (resp. last) vertex of $S$ that belongs to $\partial
R_{f}\setminus\\{f\\}$. The path $S$ can be partitioned into a $u$-to-$a$
prefix, an $a$-to-$b$ infix, and a $b$-to-$v$ suffix. All three subpaths are
represented in $G_{1}$, and all paths represented in $G_{1}$ do not include
$f$.

  2. 2.

$S$ avoids $R_{f}$ but includes a boundary vertex of some piece on
$\mathcal{T}[X,R_{f}]$. First observe that all $u$-to-$v$ paths in $G_{2}$
avoid some (not necessarily proper) ancestor of $R_{f}$ and therefore also
avoid $f$. To see that $S$ is represented in $G_{2}$, let $Q$ denote the
unique piece on $\mathcal{T}(X,R_{f}]$ such that $S$ avoids $Q$ but visits its
sibling $P$ (such a piece $Q$ must exist because $S$ avoids $R_{f}$ but visits
some piece on $\mathcal{T}[X,R_{f}]$). Since $S$ visits $P$ it must visit some
vertex of $\partial P$. Let $p$ be the first such vertex of $S$. Partition $S$
into a shortest $u$-to-$p$ path in $G\setminus(Q\cup P)\cup\\{p\\}$ and a
shortest $p$-to-$v$ path in $G\setminus Q$. These two subpaths are represented
in $G_{2}$.

  3. 3.

$S$ avoids all boundary vertices of all the pieces on $\mathcal{T}[X,R_{f}]$.
If $S$ does not visit $\partial R_{u}$ (and thus $R_{u}=R_{v}$) then we find
$S$ with an SSSP computation in $R_{u}\setminus\\{f\\}$. Otherwise, $S$ visits
a separator vertex in of some piece that is a proper ancestor of $R_{u}$. Let
$P$ be the rootmost such piece. Since $S$ avoids $\partial X$ we have that $S$
is restricted to $X$ and hence $P$ is a descendant of $X$. In fact, $P$ must
be a proper descendant of $X$ (otherwise, $S$ visits $Sep(X)$ and therefore
visits the boundary of both child-pieces of $X$ including the one on
$\mathcal{T}[X,R_{f}]$, a contradiction). We therefore have that
$P\in\mathcal{T}(X,R_{u})$ and $S$ is restricted to $P$. Also observe that $S$
avoids $\partial P$ because otherwise $S$ must visit a separator vertex of
some ancestor of $P$, contradicting $P$ being rootmost. Let $p$ be the first
vertex of $S$ that belongs to $Sep(P)$. $S$ can be decomposed into a shortest
path from $u$ to $p$ in $P\setminus\partial P$ that is internally disjoint
from $Sep(P)$, and a suffix that is a shortest path from $p$ to $v$ in
$P\setminus\partial P$; $S$ is thus represented in $G_{3}$. To see that no
path represented in $G_{3}$ contains $f$, observe that $P$ may contain $f$,
but since $R_{f}$ is not a descendant of $P$, $f$ must be a vertex of
$\partial P$ and so is not visited by any path represented in $G_{3}$.

$R_{f}$$u$$v$$f$$a$$b$ (a) Case 1.

$R_{f}$$X$$P$$Q$$u$$p$$v$ (b) Case 2.

$R_{f}$$X$$P$$u$$p$$v$ (c) Case 3.

Figure 1: An illustration of the 3 different cases that arise for the query.
In the figures we assume that $u,v\not\in R_{f}$ and the different colors in
each path represent its decomposition as defined in the proof of correctness.
In the figure for Case 2, the blue piece denotes $R_{f}$, while the siblings
of its ancestors in $\mathcal{T}(X,R_{f}]$ are denoted by different scales of
gray; the deeper the piece is in $\mathcal{T}$, the darker its color. Piece
$Q$ is denoted be the red-dashed rectangle. For Case 3, the setting is the
same and in our illustration $P$ is the child of $X$ that is not an ancestor
of $R_{f}$. $Sep(P)$ is denoted by green.

We thus arrive at the following result.

######  Theorem 2.

Given a directed planar graph $G$ of size $n$, with real edge-lengths, we can
assign an $O(n^{2/3})$-size label to each vertex of $G$ such that upon query
$(u,v,x)$, where $u,v,x\in V(G)$, the length of the shortest $u$-to-$v$ path
in $G\setminus\\{x\\}$ can be retrieved from the labels of $u$, $v$ and $x$.

######  Remark.

Let us note, that any graph $G$ of size $n$ from a family of graphs that
hereditarily admits $O(\sqrt{n})$-size separators (such as $H$-minor free
graphs and bounded genus graphs) can be recursively decomposed so that we get
an $r$-division (perhaps not with the few-holes property). As our labeling
scheme does not require the few-holes property, Theorem 2 actually applies to
any such graph family.

#### Extension for counting.

We now show how to extend our single-fault labeling from reporting $u$-to-$v$
shortest paths in $G\setminus\\{f\\}$ to counting the number of $u$-to-$v$
shortest paths in $G\setminus\\{f\\}$. Our modification does not increase the
label size (assuming that each number we store fits into a single word, see
the discussion in the introduction). However, the efficient query algorithm
cannot be applied, leading to $\tilde{O}(n^{2/3})$ query time.

In order to extend the labeling scheme for counting, for every $u$-to-$v$
shortest path distance which is stored in our label, we also store the number
of such $u$-to-$v$ shortest paths. The change in query time is that instead of
the SSSP computations on $G_{1},G_{2},G_{3}$ we use an SSSP computation that
counts shortest paths. That is, for each edge in $G_{i}$ there is a value
representing its multiplicity (the value we added to the label), and we want
to compute the number of shortest paths with respect to the multiplicities.
This extension can be achieved by a trivial extension to Dijkstra’s algorithm,
resulting in $\tilde{O}(n^{2/3})$ query time (In contrast, FR-Dijkstra has no
known extension for counting shortest paths). The following lemma proves the
correctness of our labeling scheme.

######  Lemma 3.

Every shortest path from $u$ to $v$ in $G\setminus\\{f\\}$ is represented
exactly once in the query graphs $G_{1},G_{2},G_{3}$.

###### Proof.

The same argument as in the correctness subparagraph proves that every
shortest path is represented at least once in the query graphs. It remains to
show that every path is represented at most once. Let us consider the three
cases for a shortest $(u,v,f)$-path:

  1. 1.

$S$ includes a vertex of $\partial R_{f}$. $S$ is not represented in
$G_{2},G_{3}$ because every path that is represented there must avoid an
ancestor of $R_{f}$. $S$ is represented exactly once in $G_{1}$ because it has
a unique decomposition into subpaths $S_{1}S_{2}S_{3}$ where $S_{1}$ is from
$u$ to the first vertex $b_{1}$ of $S$ in $\partial R_{f}$, $S_{2}$ is from
$b_{1}$ to the last vertex $b_{2}$ of $S$ in $\partial R_{f}$, and $S_{3}$ is
from $b_{2}$ to $v$.

  2. 2.

$S$ avoids $R_{f}$ but includes a boundary vertex of some piece on
$\mathcal{T}[X,R_{f}]$. $S$ is not represented in $G_{1}$ because all the
paths that are represented there touch $R_{f}$, it is also not represented in
$G_{3}$ since every path there avoids all boundary vertices of all pieces in
$\mathcal{T}[X,R_{f}]$. To prove that $S$ is represented in $G_{2}$ exactly
once we again show that $S$ can be uniquely decomposed into three subpaths in
$G_{2}$. Let $P$ be the sibling of some piece $Q\in\mathcal{T}[X,R_{f}]$ s.t.
$S$ visits $P$, and let $p\in\partial P\cap S$. If $P$ is not the deepest such
piece, then $S$ also visits $Q$ but the edge $(p,v)$ in $G_{2}$ counts only
paths in $G\setminus Q$, hence $S$ is not represented as a $u-p-v$ path in
$G_{2}$. If $P$ is the deepest such piece but $p$ is not the first vertex in
$\partial P$ that $S$ visits, then the $u$-to-$p$ subpath of $S$ is not
represented as an edge $(u,p)$ in $G_{2}$ since only paths in
$G\setminus(P\cup Q)\cup\\{p\\}$ are.

  3. 3.

$S$ avoids all boundary vertices of all the pieces on $\mathcal{T}[X,R_{f}]$.
$S$ is not represented in $G_{1},G_{2}$ because every path that is represented
there touches some piece in $\mathcal{T}[X,R_{f}]$. It is counted exactly once
in $G_{3}$ by a similar argument to case 2 above: $S$ is counted once in
$G_{3}$ by the first separator vertex that $S$ visits in the rootmost piece
that it visits. Finally, in the case where $R_{u}=R_{v}=R_{f}$, we perform
Dijkstra (with its extension for counting) on $R_{u}\setminus\partial R_{u}$.∎

#### Efficient queries for planar graphs.

We can easily achieve $\tilde{O}(n^{2/3})$ query-time, since this is the size
of the graphs that we construct and can thus perform Dijkstra for SSSP
computations. This query time applies to any graph family with $\sqrt{n}$-size
separators, such as minor-free graphs. On planar graphs, in order to perform
queries more efficiently we have to assume random access to the labels of
vertices $u$, $v$ and $x$; retrieving them would require $O(n^{2/3})$ time. We
present an $\tilde{O}(\sqrt{n})$-time query algorithm for planar graphs at the
expense of increasing the labels’ size by polylogarithmic factors.

Let us now formally state the main result of [8].

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

Given a weighted directed planar graph $G$ of size $n$ and a source $s\in
V(G)$, we can construct in $O(n\log^{4}n)$ time an $O(n\log^{4}n)$-size data
structure, that upon query $(v,x)$, for $v,x\in V(G)$, returns the $s$-to-$v$
distance in $G\setminus\\{x\\}$ in time $O(\log n)$.

_C_ ases 2 & 3\. $G_{2}$ and $G_{3}$ are of size $O(\sqrt{n})$ and they can be
constructed in $O(\sqrt{n})$ time from the labels of $u,v$ and $f$. We can
compute SSSPs in these graphs in $O(\sqrt{n}\log n)$ time using Dijkstra’s
algorithm. We handle the subcase of Case 3 in which $R_{u}=R_{v}$ and the
sought shortest path does not cross $\partial R_{u}$ as follows. The label of
$u$ additionally stores the single-source single-failure distance oracle of
Theorem 4 for graph $R_{u}\setminus(\partial R_{u}\setminus\\{u\\})$ and
source $u$. It occupies $\tilde{O}(r)=\tilde{O}(n^{2/3})$ additional space.
Upon query, we simply query this oracle with $(v,x)$.

_C_ ase 1. This is the only involved case, as $G_{1}$ can be of size
$\Theta(r)=\Theta(n^{2/3})$ and we aim at performing SSSP computations in time
$\tilde{O}(\sqrt{n})$. Let us note that the distances of $u$ to $\partial
R_{f}\setminus\\{f\\}$ in the case that $R_{u}=R_{f}$ can be computed in time
$\tilde{O}(\sqrt{r})=\tilde{O}(n^{1/3})$ if we have stored the oracle of
Theorem 4 for graph $R_{u}$ and source $u$ in the label of $u$. The case
$R_{v}=R_{f}$ can be treated analogously.

In order to perform efficient SSSP computations we resort to FR-Dijkstra
(Theorem 1). We first make a minor modification to item (iii) of the label so
that the Monge property required for FR-Dijkstra is satisfied: instead of
storing $\partial R_{u}$-to-$\partial R_{u}$ distances in $G\setminus\\{u\\}$,
we instead store $\partial R_{u}$-to-$\partial R_{u}$ distances in
$R\setminus\\{u\\}$ and $\partial R_{u}$-to-$\partial R_{u}$ distances in
$G\setminus((R\setminus\partial R)\cup\\{u\\})$. This ensures that the set of
vertices over which the $DDG$s are built lie on a constant number of faces of
the reference graph. The size of the label is unaffected by this modification.
We can then use Theorem 1 in a straightforward way to compute the sought
shortest path in time $\tilde{O}(\sqrt{r})=\tilde{O}(n^{1/3})$.

#### Efficient preprocessing for planar graphs.

The labels can be naively constructed in $O(n^{2})$ time. This is true for any
graph family with $\sqrt{n}$-size separators. For the case of planar graphs,
we now show that the construction time can be improved to
$\tilde{O}(n^{5/3})$.

The complete recursive decomposition of $G$, required for item (i), can be
computed in $O(n)$ time [35]. For the rest of the items, we use MSSP data
structure for an appropriate subgraph of $G$, or of the reverse graph of $G$,
i.e. $G$ with all its edges reversed.

The multiple-source shortest paths (MSSP) data structure [34] represents all
shortest path trees rooted at the vertices of a single face $g$ in a planar
graph. It can be constructed in $O(n\log n)$ time, requires $O(n\log n)$
space, and can report any distance between a vertex of $f$ and any other
vertex in the graph in $O(\log n)$ time. Using a simple modification of the
underlying graph, presented in [13], we can ensure that MSSP returns the
length of the shortest path that is internally disjoint from a prespecified
subset of the vertices of $g$.

To compute the information required for item (ii) of the labels, we build an
MSSP data structure for the reverse graph of $G\setminus(R\setminus\partial
R)$ for each piece $R$ in the $r$-division and each of the $O(1)$ holes $g$ on
which the vertices of $\partial R$ lie. We then query the sought distances.
The time required to construct the MSSP data structures is
$\tilde{O}(n^{2}/r)=\tilde{O}(n^{4/3})$ and the time required for computing
the distances is $\tilde{O}(n^{2}/\sqrt{r})=\tilde{O}(n^{5/3})$. The
precomputations for items (iii), (iv) and the first part of item (v) can be
done analogously –for item (iii) we store the distances described in the
description of the efficient query implementation.

For the second part of item (v), we can not make use of MSSP, as the shortest
path from $u$ to $p\in Sep(P)$ is allowed to cross $Sep(P)$. We can instead
build an $\tilde{O}(|P|)$-size exact distance oracle for $P\setminus\partial
P$ in $\tilde{O}(|P|^{3/2})$ time that answers distance queries in
$\tilde{O}(|P|^{\epsilon})$ time, for any constant $\epsilon>0$ ([12]); we
pick $\epsilon=1/6$. We then query this oracle for the all distances we need
to compute in $P\setminus\partial P$. Over all pieces, the preprocessing time
is $\tilde{O}(n^{3/2})$ and the sought distances are retrieved in
$\tilde{O}(n^{3/2}\cdot n^{1/6})=\tilde{O}(n^{5/3})$

To wrap up, the global preprocessing time is $\tilde{O}(n^{5/3})$ and is upper
bounded by the total size of the labels up to polylogarithmic factors.

##  4 Labeling for Counting Shortest Paths

In this section we design labels such that given the labels of any $k+2$
vertices $s,t,v_{1},v_{2},\ldots,v_{k}$, we should return the number of
$s$-to-$t$ paths that avoid vertices $v_{1},\ldots,v_{k}$ and whose length is
equal to $d(s,t)$ (the original $s$-to-$t$ distance in $G$). Note that this is
the same as returning the number of shortest $s$-to-$t$ paths in
$G\setminus\\{v_{1},v_{2},\dots,v_{k}\\}$ only if the length of the shortest
$s$-to-$t$ path does not change when $\\{v_{1},v_{2},\dots,v_{k}\\}$ fail. We
show that the labeling of [9] (with labels of size $O(\sqrt{n})$) actually
works in this more general setting and show how to perform a query in
$\tilde{O}(\sqrt{n}\cdot k)$ time. We assume in this section that edge weights
are strictly positive.

#### The label.

We first compute a complete recursive decomposition of $G$. The label of each
vertex $v$ in $G$ then consists of the following information:

  1. (i)

For each ancestor piece $P$ of $v$, for every $u\in Sep(P)$, the number
$p_{1}(v,u)$ and length $d_{1}(v,u)$ of all $v$-to-$u$ shortest paths in
$P\setminus Sep(P)\cup\\{u\\}$.

  2. (ii)

For each ancestor piece $P$ of $v$, for every $u\in Sep(P)$, the number
$p_{2}(u,v)$ and length $d_{2}(u,v)$ of all $u$-to-$v$ shortest paths in
$P\setminus\partial P$.

In what follows, in the case that $u$ is in many separators of ancestor pieces
of $v$, when referring to $d_{1}(v,u)$, $p_{1}(v,u)$, $d_{2}(u,v)$ and
$p_{2}(u,v)$ we mean the values computed for the rootmost such piece.

#### The query - without faults.

When there are no faulty vertices, every $s$-to-$t$ shortest path $Q$ in $G$
is uniquely determined by a piece $P$ in the recursive decomposition and a
vertex $u\in Sep(P)$. The piece $P$ is the rootmost ancestor piece of $s$ in
the recursive decomposition s.t. $Q$ visits $Sep(P)$ and therefore does not
visit $\partial P$. Such a piece $P$ must be an ancestor of both $s$ and $t$.
The vertex $u\in Sep(P)$ is the first vertex of $Sep(P)$ visited by $Q$. $Q$
can thus be decomposed into a prefix $Q_{1}$ in $P\setminus Sep(P)\cup\\{u\\}$
from $s$ to $u$, and a suffix $Q_{2}$ in $P\setminus\partial P$ from $u$ to
$t$. For every possible $u$ we have the number of such $Q_{1}$ in (i) of $s$
and the number of such $Q_{2}$ in (ii) of $t$. We therefore add the term
$p_{1}(s,u)\cdot p_{2}(u,t)$ to the answer. However, we only wish to add this
term if $d(s,u)+d(u,t)=d(s,t)$ (otherwise, we are counting non-shortest
paths). We have $d(s,u)+d(u,t)$ from the labels of $s$ and $t$. We compute
$d(s,t)$ as follows. Let $A[v]$ be the union of separator vertices of all
ancestors of $v$. Then

$d(s,t)=\min_{u\in A[s]\cap A[t]}(d_{1}(s,u)+d_{2}(u,t)),$ (1)

and the overall query is computed as

$paths(s,t)\ \ \
=\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\sum_{\begin{subarray}{c}u\in A[s]\cap
A[t]\text{ s.t }\\\
d_{1}(s,u)+d_{2}(u,t)=d(s,t)\end{subarray}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!p_{1}(s,u)\cdot
p_{2}(u,t)$ (2)

It takes $\tilde{O}(\sqrt{n})$ time to perform such query because there are
$O(\sqrt{n})$ vertices in $A[s]\cap A[t]$ and for each of them we perform
$\tilde{O}(1)$ calculations. We also compute $d(s,t)$ beforehand in
$\tilde{O}(\sqrt{n})$ time.

#### The query - with faults.

We begin with an $\tilde{O}(\sqrt{n}\cdot k^{2})$ time query and then improve
this to $\tilde{O}(\sqrt{n}\cdot k)$. We order the faulty vertices in the
increasing order of their distances from $s$ in $G$, and index them
$v_{1},\ldots,v_{k}$ accordingly. For convenience we refer to $s$ as $v_{0}$
and to $t$ as $v_{k+1}$. Denote by $R[j]$ the number of $s$-to-$v_{j}$
shortest paths in $G$ that avoid $v_{1},\ldots,v_{j-1}$. Denoting by
$paths(v_{i},v_{j})$ the number of $v_{i}$-to-$v_{j}$ shortest paths in $G$ we
obtain the recurrence:

$R[j]=paths(s,v_{j})\ \ \
\\!\\!\\!\\!-\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\sum_{\begin{subarray}{c}i<j\text{
s.t. }\\\ d(s,v_{i})+d(v_{i},v_{j})=d(s,v_{j})\\\
\end{subarray}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!R[i]\cdot
paths(v_{i},v_{j})$ (3)

To see why this recurrence holds, it suffices to show that every shortest path
$Q$ in $G$ from $s$ to $v_{j}$ that visits at least one of
$v_{1},\ldots,v_{j-1}$ is counted in the second term exactly once. It is clear
that every such path $Q$ is counted at least once, because it can be
decomposed into a prefix composed of a shortest path from $s$ to the first
$v_{i}$ that $Q$ visits (i.e. is counted by $R[i]$) and a suffix composed of a
$v_{i}$-to-$v_{j}$ path (i.e. counted by $paths(v_{i},v_{j})$). To see why
every path $Q$ is counted at most once, notice that every such path $Q$ visits
the faulty vertices monotonically with respect to their ordering. In other
words, if $Q$ visits some $v_{i}$ and then some $v_{j}$ then $i<j$. This holds
because if $v_{i}$ is on a shortest path from $s$ to $v_{j}$ then
$d(s,v_{i})<d(s,v_{j})$, and by our ordering of the faulty vertices $i<j$.
Since $R[i]$ only counts paths that are internally disjoint from failed
vertices, the only time $Q$ is counted is when we count paths of the form
$s\rightsquigarrow v_{i}\rightsquigarrow v_{j}$, where $v_{i}$ is the first
faulty vertex $Q$ visits.

Given $R[1],\ldots,R[j-1]$ we can compute $R[j]$ in $\tilde{O}(\sqrt{n}\cdot
j)$ using the recurrence. For each faulty vertex $v_{i}$ with $i<j$ we perform
a $paths(v_{i},v_{j})$ query as described above which takes
$\tilde{O}(\sqrt{n})$ time, so the overall complexity is
$\tilde{O}(\sqrt{n}\cdot k^{2})$.

#### Improved query time.

We now show how to improve the query time from $\tilde{O}(\sqrt{n}\cdot
k^{2})$ to $\tilde{O}(\sqrt{n}\cdot k)$. In order to achieve this, we cannot
afford to compute $paths(v_{i},v_{j})$ for every pair $i,j$. Instead, we will
express $R[j]$ as a summation over $O(\sqrt{n})$ terms that we can compute in
$\tilde{O}(1)$ time.

By combining equations (2) and (3), and since $paths(s,v_{j})$ can be computed
in $\tilde{O}(\sqrt{n})$ time, we get that computing $R[j]$ boils down to
computing the following double summation:

$\sum_{\begin{subarray}{c}i<j\text{ s.t. }\\\
d(s,v_{i})+d(v_{i},v_{j})=d(s,v_{j})\\\
\end{subarray}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!R[i]\
\ \ \ \ \ \sum_{\begin{subarray}{c}u\in A[v_{i}]\cap A[v_{j}]\text{ s.t }\\\
d_{1}(v_{i},u)+d_{2}(u,v_{j})=d(v_{i},v_{j})\end{subarray}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!p_{1}(v_{i},u)\cdot
p_{2}(u,v_{j})$ (4)

The above sum counts all $s$-to-$v_{j}$ shortest paths $Q$ that can be
decomposed into three parts:
$Q_{1}$ \- a shortest $s$-to-$v_{i}$ path in $G$ (for some $v_{i}$) that
avoids $v_{1},\ldots,v_{i-1}$.
$Q_{2}$ \- a shortest $v_{i}$-to-$u$ path in $P\setminus Sep(P)\cup\\{u\\}$
for some $u\in Sep(P)$, where $P$ is defined as the rootmost ancestor of
$v_{i}$ s.t. $Q$ touches $Sep(p)$ ($u$ is the first vertex of $Sep(P)$ in
$Q_{2}$).
$Q_{3}$ \- a shortest $u$-to-$v_{j}$ path in $P\setminus\partial P$.

We use the same decomposition into $Q_{1},Q_{2},Q_{3}$ but sum the terms
differently. Denoting $D(s,u)=\min_{i}(d(s,v_{i})+d_{1}(v_{i},u))$ we compute:

$\sum_{\begin{subarray}{c}u\in A[v_{j}]\text{ s.t. }\\\
D(s,u)+d_{2}(u,v_{j})=d(s,v_{j})\end{subarray}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!p_{2}(u,v_{j}){\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\sum_{\begin{subarray}{c}i<j\text{
s.t. }u\in A[v_{i}]\text{ and }\\\
d(s,v_{i})+d_{1}(v_{i},u)=D(s,u)\end{subarray}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!R[i]\cdot
p_{1}(v_{i},u)}$ (5)

Let us explain equation (5). Denote the inner summation term (in blue) as
$F_{j}(u)$. $F_{j}(u)$ counts the number of combinations for $Q_{1}Q_{2}$ by
iterating over every faulty vertex $v_{i}$ where $i<j$ and $u\in A[v_{i}]$.
For a fixed $v_{i}$, the number of such combinations is $R[i]\cdot
p_{1}(v_{i},u)$. Among all $Q_{1}Q_{2}$ combinations, we only want to sum
combinations $Q_{1}Q_{2}$ that have length $d(s,u)$. Ideally, this could be
imposed by adding the condition $d(s,v_{i})+d_{1}(v_{i},u)=d(s,u)$ to the
inner sum. However, we cannot compute $d(s,u)$ because we do not have the
label of $u$. Instead, we add the condition $d(s,v_{i})+d_{1}(v_{i},u)=D(s,u)$
where $D(s,u)=\min_{i}(d(s,v_{i})+d_{1}(v_{i},u))$ (observe that $D(s,u)\geq
d(s,u)$). This condition is easy to check using $d_{1}(v_{i},u)$ stored in the
label of $v_{i}$ and the value $d(s,v_{i})$ which can be computed beforehand
using equation (1). The counting remains correct because in the outer sum we
check that $D(s,u)+d_{2}(u,v_{j})=d(s,v_{j})$ which only holds if
$D(s,u)=d(s,u)$ (because when $D(s,u)>d(s,u)$ then by the triangle inequality
we have that $D(s,u)+d_{2}(u,v_{j})>d(s,u)+d_{2}(u,v_{j})\geq d(s,v_{j})$).
Note that even if $D(s,u)=d(s,u)$ it may be that
$D(s,u)+d_{2}(u,v_{j})>d(s,v_{j})$. This happens in the case that there are no
$s$-to-$v_{j}$ shortest paths that visit $u$. In other words, we check that a
path $Q_{1}Q_{2}Q_{3}$ is shortest by verifying that
$d(s,v_{i})+d_{1}(v_{i},u)+d_{2}(u,v_{j})=d(s,v_{j})$. This is true iff
$D(s,u)=d(s,u)$ and $d_{2}(u,v_{j})=d(u,v_{j})$ which means that
$Q_{1}Q_{2}Q_{3}$ is indeed a shortest path.

Observe that in the inner sum we consider only $i<j$. This is because for
$i\geq j$ none of the paths from $s$ to $v_{j}$ that visit $v_{i}$ is shortest
due to the ordering of the faulty vertices.

As for the outer sum, it counts the number of $Q_{3}$ paths for every $u\in
A[v_{j}]$. Overall, we iterate over every $u\in A[v_{j}]$ and multiply
$F_{j}(u)$ (the number of $Q_{1}Q_{2}$ paths) by $p_{2}(u,v_{j})$ (the number
of $Q_{3}$ paths) and obtain the answer.

Overall, in the $j$’th iteration we compute $R[j]$ using the $F_{j}(u)$ values
according to equation (5). Notice that $F_{j+1}(u)$ is either equal to
$F_{j}(u)$ or to $F_{j}(u)+R[j]\cdot p_{1}(v_{j},u)$. We can therefore compute
$F_{j+1}(u)$ for every $u\in A[v_{j}]$ using the just computed $R[j]$ and
$F_{j}(u)$. This takes total $\tilde{O}(\sqrt{n})$ time and
$\tilde{O}(\sqrt{n}\cdot k)$ time over all the $k+2$ iterations.

In order to check the distance restrictions in the summations we precompute
$d(s,v_{j})$ for every $0\leq j\leq k+1$ and $D(s,u)$ for every
$u\in\bigcup_{0\leq i\leq k+1}A[v_{i}]$. The former ($d(s,v_{j})$) is computed
using (1), and the latter ($D(s,u)$) is computed by iterating over every $i$
and $u\in A[v_{i}]$ and maintaining the minimum value for each $D(s,u)$. The
precomputation of $D(s,u)$ and $d(s,v_{j})$ therefore takes
$\tilde{O}(\sqrt{n}\cdot k)$ time.

##  5 A Lower Bound on Labeling for Counting Shortest Paths

In this section we prove the following lower bound on labeling schemes for
counting shortest paths (without faults) in graphs such that the number of
distinct shortest paths between any two nodes consists of at most $L$ bits.

The proof is a modification of the approach of Gavoille et al. [22] for
standard distance labeling. Their proof proceeds by assigning weights to the
edges of a $\sqrt{n}\times\sqrt{n}$ grid graph so that the shortest path from
the $i$-th node in the first column to the $j$-th node in the first row
consists of $j-1$ horizontal edges, followed by $i-1$ vertical edges. Then,
the proof hides a single bit in every intersection by creating or not a
shortcut. The shortest paths defined above are still of the same form, up to
using the shortcut in case it exists: horizontal edges, possibly a shortcut,
and then vertical edges.

######  Theorem 5.

Any labeling scheme for counting shortest paths in planar graphs such that the
number of distinct shortest paths between any two nodes consists of at most
$L$ bits requires labels consisting of $\Omega(\sqrt{nL})$ bits.

###### Proof.

Let us consider a $\sqrt{m}\times\sqrt{m}$ grid graph, weighted as in the
proof of Gavoille et al. from [22]. In every intersection, instead of a single
$s$-to-$t$ shortcut, we introduce an $O(L)$-size gadget – essentially the one
described in the introduction, in our proof that labels of $o(n)$ bits cannot
exist if $L$ is unbounded.

More specifically, suppose that we are given $L-1$ bits
$b_{0},\ldots,b_{L-2}$. Each edge of the gadget will have weight equal to
$1/L$ times the weight of the shortcut in the proof of Gavoille et al. The
gadget consists of a path $s=u_{0}-u_{1}-\cdots-u_{L-1}$ and another path
$v_{1}-v_{2}-\cdots-v_{L}=t$ in which every edge is duplicated (i.e., there
are two parallel edges between each pair $v_{i},v_{i+1}$). Finally, for every
$i=0,\ldots,L-2$ such that $b_{i}=1$, we add an edge $u_{i}-v_{i+1}$. The
number of shortest $s$-to-$t$ paths in the gadget is exactly
$\sum_{i=0}^{L-2}b_{i}\cdot 2^{L-1-i}$. Note that this number is congruent to
$0$ modulo $2$. The size of the graph is $n=\Theta(mL)$.

Now, the number of shortest paths from the $i$-th node in the first column to
the $j$-th node in the first row is $1$ if all $b_{i}$’s are equal to $0$ for
the gadget at intersection $(i,j)$; otherwise it is equal to
$\sum_{i=0}^{L-2}b_{i}\cdot 2^{L-1-i}$. Hence, each pair $(i,j)$ allows us to
recover $\Theta(L)$ distinct bits. Thus, the labels must consist of
$\Omega((\sqrt{m}-1)^{2}L/(2\sqrt{m}-1))=\Omega(\sqrt{m}L)=\Omega(\sqrt{nL})$
bits. ∎

We leave the problem of closing the gap between this $\Omega(\sqrt{nL})$ lower
bound and the $O(\sqrt{n}L)$ upper bound open for further investigation.

##  6 A Lower Bound on Dynamic Oracles for Counting Shortest Paths

In this section we consider dynamic oracles for counting shortest paths
(without faults) in undirected planar graphs. That is, data structures that
can support queries for counting shortest paths as well as updates to the edge
weights. We show a lower bound conditioned on the hardness of Online Boolean
Matrix-Vector Multiplication (OMv):

######  Conjecture 6 (OMv Conjecture, [27]).

For every $\epsilon>0$, there is no $O(N^{3-\epsilon})$-time algorithm that
given an $N\times N$ boolean matrix $M$ and a stream of boolean vectors
$v_{1},\ldots,v_{N}$ computes the products $Mv_{i}$ online (i.e. computes
$Mv_{i}$ before seeing $v_{i+1}$).

Based on the above conjecture, we prove that for any dynamic shortest paths
counting oracle in undirected planar graphs, either the query time or the
update time must be $\Omega(\sqrt{n})$ (up to subpolynomial factors).

######  Theorem 7.

A dynamic shortest paths counting oracle in undirected $n$-vertex planar
graphs with amortized query time $q(n)$ and update time $u(n)$ cannot have
$q(n)+u(n)=O(n^{1/2-\epsilon})$ for any $\epsilon>0$ unless the OMv conjecture
is false. This holds even if we only allow edge-weight increments and
decrements by 1.

###### Proof.

Our proof follows closely the proof of Abboud-Dahlgaard [1] for dynamic
oracles reporting (i.e. not counting) shortest paths. There are a few subtle
differences, but the main difference is that [1] was based on min-plus vector-
matrix multiplication while ours is based on standard vector-matrix
multiplication.

#### Encoding the matrix as a grid.

We consider a $\sqrt{n}\times\sqrt{n}$ boolean matrix $M$ (i.e. $N=\sqrt{n}$
in Conjecture 6) and encode it using a $(\sqrt{n}+1)\times(\sqrt{n}+1)$ grid
$G_{M}$. For convenience, we index the rows and columns of $M$ as
$1,\ldots,\sqrt{n}$ and the rows and columns of $G_{M}$ as
$0,\ldots,\sqrt{n}$. The grid $G_{M}$ contains:

  1. 1.

All horizontal edges of the form $((i,j),(i,j+1))$ except for
$((0,j),(0,j+1))$ (i.e. except for the first grid row). All these edges have
the same weight $\sqrt{n}$.

  2. 2.

All vertical edges of the form $((i,j),(i+1,j))$ except for
$((i,\sqrt{n}),(i+1,\sqrt{n}))$ (i.e. except for the last grid column). The
weight of edge $((i,j),(i+1,j))$ is $j+1$.

  3. 3.

If $M_{i,j}=1$ we add an edge $e_{i,j}=((i-1,j-1),(i,j))$ with weight
$\sqrt{n}+j$.

Denote the vertices of the first row $(0,j)$ as $s_{j}$ and vertices of the
last column $(i,\sqrt{n})$ as $t_{i}$. Consider the shortest
$s_{j}$-to-$t_{i}$ path. It is easy to see that if $M_{i,j+1}=0$ then this
path is (1) unique, (2) composed of a vertical prefix and and a horizontal
suffix, and (3) is of length $\sqrt{n}(\sqrt{n}-j)+i(j+1)$. If however
$M_{i,j+1}=1$ then there are exactly two such shortest paths (one using
$e_{i,j}$ and the other using $((i-1,j-1),(i,j-1))$ followed by
$((i,j-1),(i,j))$) both of length $\sqrt{n}(\sqrt{n}-j)+i(j+1)$.

#### The zero matrix grid.

We would like to make the length of the above shortest paths independent of
$i$ and $j$. We define another $(\sqrt{n}+1)\times(\sqrt{n}+1)$ grid $G_{0}$
that has no diagonal edges and contains:

  1. 1.

All horizontal edges of the form $((i,j),(i,j+1))$ except for
$((0,j),(0,j+1))$ (i.e. except for the first grid row). All these edges have
the same weight $\sqrt{n}$.

  2. 2.

All vertical edges of the form $((i,j),(i+1,j))$ except for $((i,0),(i+1,0))$
(i.e. except for the first grid column). The weight of edge $((i,j),(i+1,j))$
is $\sqrt{n}-j+1$.

Denote the vertices of the first column $(i,0)$ of $G_{0}$ as $s^{\prime}_{i}$
and vertices of the first row $(0,j)$ of $G_{0}$ as $t^{\prime}_{j}$. The
graph $G$ on which we build the oracle is obtained by connecting the two grids
$G_{0}$ and $G_{M^{t}}$ (the grid representation of the transpose of $M$).
This is done by adding edges $b_{i}=(t_{i},s^{\prime}_{i})$ of weight
$w(b_{i})=(\sqrt{n}+1)(\sqrt{n}-i)$ for every $1\leq i\leq\sqrt{n}$.

#### The reduction.

In order to solve the OMv problem, for each query vector
$v[1,\ldots,\sqrt{n}]$, if $v$ is the all-zero vector we simply output an all-
zero vector. Otherwise, we (1) reset the weight $w(b_{i})$ of every $b_{i}$ to
be $(\sqrt{n}+1)(\sqrt{n}-i)$, (2) for every $i$, if $v[i]=0$ we increase the
weight of $b_{i}$ by 1, and (3) for every index $0\leq j<\sqrt{n}$ we query
the oracle for the number of shortest paths from $s_{j}$ to
$t^{\prime}_{j+1}$. Finally, we decrease the oracle’s answer by the number of
1’s in $v$ and assign this value as the $j$’th entry in the result $Mv$.

To see why the above procedure correctly calculates $Mv$, first note that the
$j$’th entry in $Mv$ is exactly the number of indices $1\leq i\leq\sqrt{n}$
s.t. $e_{i,j}$ is present in $G_{M^{t}}$ and $v[i]=1$. The length of the
shortest path from $s_{j}$ to $t^{\prime}_{j+1}$ through an edge $b_{k}$ is
$d(s_{j},t_{k})+w(b_{k})+d(s^{\prime}_{k},t^{\prime}_{j+1})=2n+2\sqrt{n}$.
This value is independent of both $j$ and $k$, so for each $1\leq
k\leq\sqrt{n}$ we have a unique shortest path through $b_{k}$ if $e_{k,j+1}$
is absent in $G$ or exactly two shortest paths if $e_{k,j+1}$ is present in
$G$. In step (2), when we increase by 1 the edges $b_{i}$ corresponding to
entries in $v$ where $v[i]=0$, paths going through these $b_{i}$’s are longer
than paths going through other $b_{i}$’s and are therefore not shortest (we
made sure that $v$ is not all-zero). Hence, every $b_{i}$ that corresponds to
$v[i]=1$ contributes $1+M^{t}_{i,j+1}$ to the number of shortest paths from
$s_{j}$ to $t^{\prime}_{j+1}$, and by subtracting the number of $1$’s in $v$
we obtain the correct answer.

Overall, for each vector we perform $O(\sqrt{n})$ updates and queries, so
overall we perform $O(n)$ updates and queries. If each update/query takes
$O(n^{0.5-\epsilon})$ time then we get overall
$O(n^{1.5-\epsilon})=O(N^{3-\epsilon/2})$ contradicting Conjecture 6. ∎

## References

  * [1] Amir Abboud and Søren Dahlgaard.  Popular conjectures as a barrier for dynamic planar graph algorithms.  In 57th FOCS, pages 477–486, 2016.  doi:10.1109/FOCS.2016.58.
  * [2] Ittai Abraham, Shiri Chechik, and Cyril Gavoille.  Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels.  In 44th STOC, pages 1199–1218, 2012.  doi:10.1145/2213977.2214084.
  * [3] Ittai Abraham, Shiri Chechik, Cyril Gavoille, and David Peleg.  Forbidden-set distance labels for graphs of bounded doubling dimension.  ACM Trans. Algorithms, 12(2):22:1–22:17, 2016.  URL: https://doi.org/10.1145/2818694, doi:10.1145/2818694.
  * [4] Ittai Abraham and Cyril Gavoille.  Object location using path separators.  In 25th PODC, pages 188–197. ACM, 2006.  doi:10.1145/1146381.1146411.
  * [5] Noga Alon and Rajko Nenadov.  Optimal induced universal graphs for bounded-degree graphs.  In 28th SODA, pages 1149–1157, 2017.  doi:10.1137/1.9781611974782.74.
  * [6] Stephen Alstrup, Søren Dahlgaard, and Mathias Bæk Tejs Knudsen.  Optimal induced universal graphs and adjacency labeling for trees.  J. ACM, 64(4):27:1–27:22, 2017.  doi:10.1145/3088513.
  * [7] Stephen Alstrup, Haim Kaplan, Mikkel Thorup, and Uri Zwick.  Adjacency labeling schemes and induced-universal graphs.  SIAM J. Discret. Math., 33(1):116–137, 2019.  doi:10.1137/16M1105967.
  * [8] Surender Baswana, Utkarsh Lath, and Anuradha S. Mehta.  Single source distance oracle for planar digraphs avoiding a failed node or link.  In 23rd SODA, pages 223–232, 2012.  doi:10.1137/1.9781611973099.20.
  * [9] Ivona Bezáková and Andrew Searns.  On counting oracles for path problems.  In 29th ISAAC, pages 56:1–56:12, 2018.  doi:10.4230/LIPIcs.ISAAC.2018.56.
  * [10] Nicolas Bonichon, Cyril Gavoille, and Arnaud Labourel.  Short labels by traversal and jumping.  Electronic Notes in Discrete Mathematics, 28:153–160, 2007.  doi:10.1016/j.endm.2007.01.022.
  * [11] Sergio Cabello, Erin W. Chambers, and Jeff Erickson.  Multiple-source shortest paths in embedded graphs.  SIAM J. Comput., 42(4):1542–1571, 2013.  doi:10.1137/120864271.
  * [12] Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, and Oren Weimann.  Almost optimal distance oracles for planar graphs.  In 51st STOC, pages 138–151, 2019.  doi:10.1145/3313276.3316316.
  * [13] Panagiotis Charalampopoulos, Shay Mozes, and Benjamin Tebeka.  Exact distance oracles for planar graphs with failing vertices.  In 30th SODA, pages 2110–2123, 2019.  doi:10.1137/1.9781611975482.127.
  * [14] Bruno Courcelle, Cyril Gavoille, and Mamadou M. Kanté.  Compact labelings for efficient first-order model-checking.  Journal of Combinatorial Optimization, 21(1):19–46, 2009.  doi:10.1007/s10878-009-9260-7.
  * [15] Bruno Courcelle and Andrew Twigg.  Constrained-path labellings on graphs of bounded clique-width.  Theory of Computing Systems, 47(2):531–567, 2010.  doi:10.1007/s00224-009-9211-9.
  * [16] Yuval Emek, David Peleg, and Liam Roditty.  A near-linear-time algorithm for computing replacement paths in planar directed graphs.  ACM Trans. Algorithms, 6(4):64:1–64:13, 2010.  doi:10.1145/1824777.1824784.
  * [17] Jittat Fakcharoenphol and Satish Rao.  Planar graphs, negative weight edges, shortest paths, and near linear time.  J. Comput. Syst. Sci., 72(5):868–889, 2006.  doi:10.1016/j.jcss.2005.05.007.
  * [18] Joan Feigenbaum, David R. Karger, Vahab S. Mirrokni, and Rahul Sami.  Subjective-cost policy routing.  In 1st WINE, pages 174–183, 2005.  doi:10.1007/11600930\\_18.
  * [19] Joan Feigenbaum, David R. Karger, Vahab S. Mirrokni, and Rahul Sami.  Subjective-cost policy routing.  Theor. Comput. Sci., 378(2):175–189, 2007.  doi:10.1016/j.tcs.2007.02.020.
  * [20] Greg N. Frederickson.  Fast algorithms for shortest paths in planar graphs, with applications.  SIAM J. Comput., 16(6):1004–1022, 1987.  doi:10.1137/0216064.
  * [21] Cyril Gavoille, Michal Katz, Nir A. Katz, Christophe Paul, and David Peleg.  Approximate distance labeling schemes.  In 9th ESA, pages 476–487, 2001.  doi:10.1007/3-540-44676-1\\_40.
  * [22] Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz.  Distance labeling in graphs.  Journal of Algorithms, 53(1):85–112, 2004.  doi:10.1016/j.jalgor.2004.05.002.
  * [23] Paweł Gawrychowski, Shay Mozes, Oren Weimann, and Christian Wulff-Nilsen.  Better tradeoffs for exact distance oracles in planar graphs.  In 29th SODA, pages 515–529, 2018.  doi:10.1137/1.9781611975031.34.
  * [24] Paweł Gawrychowski and Przemysław Uznański.  A note on distance labeling in planar graphs.  CoRR, abs/1611.06529, 2016.  arXiv:1611.06529.
  * [25] R. L. Graham and H. O. Pollak.  On embedding graphs in squashed cubes.  In Y. Alavi, D. R. Lick, and A. T. White, editors, Graph Theory and Applications, pages 99–110, Berlin, Heidelberg, 1972. Springer Berlin Heidelberg.
  * [26] Anupam Gupta, Amit Kumar, and Rajeev Rastogi.  Traveling with a pez dispenser (or, routing issues in MPLS).  In 42nd FOCS, pages 148–157, 2001.  doi:10.1109/SFCS.2001.959889.
  * [27] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak.  Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture.  In 47th STOC, pages 21–30, 2015.  doi:10.1145/2746539.2746609.
  * [28] Tai-Hsin Hsu and Hsueh-I Lu.  An optimal labeling for node connectivity.  In 20th ISAAC, 2009.  doi:10.1007/978-3-642-10631-6\\_32.
  * [29] Giuseppe F. Italiano, Adam Karczmarz, Nikos Parotsidis.  Planar Reachability Under Single Vertex or Edge Failures Giuseppe F. Italiano, Adam Karczmarz, Nikos Parotsidis.  In 32nd SODA, pages 2739-2758, 2021.  doi:10.1137/1.9781611976465.163.
  * [30] Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen.  Improved algorithms for min cut and max flow in undirected planar graphs.  In 43rd STOC, pages 313–322, 2011.  doi:10.1145/1993636.1993679.
  * [31] Sampath Kannan, Moni Naor, and Steven Rudich.  Implicit representation of graphs.  SIAM Journal on Discrete Mathematics, 5(4):596–603, 1992.  doi:10.1137/0405049.
  * [32] Haim Kaplan, Shay Mozes, Yahav Nussbaum, and Micha Sharir.  Submatrix maximum queries in monge matrices and partial monge matrices, and their applications.  ACM Trans. Algorithms, 13(2):26:1–26:42, 2017.  doi:10.1145/3039873.
  * [33] Michal Katz, Nir A. Katz, Amos Korman, and David Peleg.  Labeling schemes for flow and connectivity.  SIAM J. Comput., 34(1):23–40, 2004.  doi:10.1137/S0097539703433912.
  * [34] Philip N. Klein.  Multiple-source shortest paths in planar graphs.  In 16th SODA, pages 146–155, 2005.  URL: http://dl.acm.org/citation.cfm?id=1070432.1070454.
  * [35] Philip N. Klein, Shay Mozes, and Christian Sommer.  Structured recursive separator decompositions for planar graphs in linear time.  In 45th STOC, pages 505–514, 2013.  doi:10.1145/2488608.2488672.
  * [36] Philip N. Klein, Shay Mozes, and Oren Weimann.  Shortest paths in directed planar graphs with negative lengths: A linear-space ${O}(n\log^{2}n)$-time algorithm.  ACM Trans. Algorithms, 6(2):30:1–30:18, 2010.  doi:10.1145/1721837.1721846.
  * [37] Amos Korman.  Labeling schemes for vertex connectivity.  ACM Trans. Algorithms, 6(2):39:1–39:10, 2010.  doi:10.1145/1721837.1721855.
  * [38] Gary L. Miller.  Finding small simple cycle separators for 2-connected planar graphs.  In 16th STOC, pages 376–382, 1984.  doi:10.1145/800057.808703.
  * [39] Gaspard Monge.  Mémoire sur la théorie des déblais et des remblais.  De l’Imprimerie Royale, 1781.
  * [40] Shay Mozes and Christian Wulff-Nilsen.  Shortest paths in planar graphs with real lengths in ${O}(n\log^{2}n/\log\log n)$ time.  In 18th ESA, pages 206–217, 2010.  doi:10.1007/978-3-642-15781-3_18.
  * [41] David Peleg.  Proximity-preserving labeling schemes.  J. Graph Theory, 33(3):167–176, March 2000.
  * [42] David Peleg.  Informative labeling schemes for graphs.  Theor. Comput. Sci., 340(3):577–593, 2005.  doi:10.1016/j.tcs.2005.03.015.
  * [43] Casper Petersen, Noy Rotbart, Jakob Grue Simonsen, and Christian Wulff-Nilsen.  Near-optimal adjacency labeling scheme for power-law graphs.  In 43rd ICALP, pages 133:1–133:15, 2016.  doi:10.4230/LIPIcs.ICALP.2016.133.
  * [44] Noy Galil Rotbart.  New Ideas on Labeling Schemes.  PhD thesis, University of Copenhagen, 2016.
  * [45] Mikkel Thorup.  Compact oracles for reachability and approximate distances in planar digraphs.  Journal of the ACM, 51(6):993–1024, 2004.  doi:10.1145/1039488.1039493.
  * [46] Andrew D. Twigg.  Compact forbidden-set routing.  Technical Report UCAM-CL-TR-678, University of Cambridge, Computer Laboratory, December 2006.  URL: https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-678.pdf.
  * [47] Christian Wulff-Nilsen.  Solving the replacement paths problem for planar directed graphs in ${O}(n\log n)$ time.  In 21st SODA, pages 756–765, 2010.  doi:10.1137/1.9781611973075.62.