Online Routing in Directed ${\text{Yao}}_4^{\mathrm{\infty }}$ Graphs

A fundamental problem in geometric routing is to construct a directed planar graph on a given set of points that supports competitive local routing, using the fewest number of edges. A routing algorithm is competitive if the length of the path that it finds is at most a constant times the length of the shortest path, however a local algorithm does not have access to the full graph. This problem has applications in wireless sensor networks, robotic navigation, and distributed computing. Routing is inherently directional, and in many real-world settings, signals are sent from a transmitter to an antenna. This directional nature is particularly relevant in wireless communication, where signal transmission can be costly. Wide-angle broadcasting consumes excessive power, and long-distance transmission is expensive, with energy consumption proportional to the distance squared. As a result, nodes should send signals in restricted directions, ensuring that each transmitted signal has a unique receiver. To reduce the effects of interference, we desire planarity, meaning that signals do not cross. However, we allow bidirectional edges, which count as two directed edges, since otherwise, not all point sets admit strongly-connected directed planar graphs. Disallowing bidirectional edges presents different challenges and has led to the study of oriented spanners [12]. Note that every undirected graph can be converted into a directed graph by replacing every undirected edge with two directed edges. This implies that every routing result on undirected graphs can also be viewed as a routing result on directed graphs with twice as many edges. Thus, the challenge is to construct directed planar graphs that support local routing while minimizing the number of directed edges.

Routing on graphs in an online fashion, without relying on precomputed routing tables is a compelling motivation for studying routing on geometric embeddings of graphs. The use of routing tables can be circumvented by exploiting geometric properties of the graph, such as empty proximity regions, to guide path-finding. Routing tables are often inefficient to compute and difficult to maintain in a dynamic setting, compared to maintaining a geometric embedding of a graph. Embeddings like Yao and Theta graphs provide a framework for leveraging these empty proximity regions to facilitate efficient routing. Our focus on the $\overrightarrow{{\text{Yao}}_4^{\mathrm{\infty }}}$ graph stems from its unique combination of properties: it is planar, has a bounded out-degree of $4$, and supports a novel competitive local routing algorithm.

For decades, researchers have been studying the distance-preserving properties of geometric graphs, such as the Delaunay triangulation [17]. The vertex set of a geometric graph is a finite set of points in the plane and the edges are weighted by the $L_2$-norm. The Delaunay triangulation has an edge between two vertices exactly when they lie on the boundary of a disk which contains no other vertex in its interior [15]. When the disk is replaced with a square, then we obtain an $L_{\mathrm{\infty }}$-Delaunay graph. Also a geometric graph of interest is the Yao graph. For any $k>2$, a ${\text{Yao}}_k$ graph is constructed by considering $k$ equal-sized cones around each vertex and connecting each vertex to the nearest point in each cone [18]. In this way, a graph on $n$ points has at most $nk$ edges. Normally, nearest is defined using the $L_2$-norm, however in the case of $k=4$, replacing $L_2$ with $L_{\mathrm{\infty }}$ is a natural choice because the resulting graph, denoted ${\text{Yao}}_4^{\mathrm{\infty }}$, is a subgraph of the well-known $L_{\mathrm{\infty }}$-Delaunay graph. In other words, the ${\text{Yao}}_4^{\mathrm{\infty }}$ graph has an edge between two vertices when there exists an empty square with one endpoint on a corner and the other endpoint on an opposing side. If the graph is defined using the $L_1$-norm, then we obtain the well-studied ${\mathrm{\Theta }}_4$-graph.

Given a geometric graph $G$, the spanning ratio of a subgraph $H$ is a measure of how well distances of $G$ are preserved. A subgraph $H$ is called a $c$-spanner of $G$ if for every edge $uv\in G$, the shortest path in $H$ from $u$ to $v$ is at most $c$ times the length of the edge $uv$ in $G$ [17]. The smallest such $c$ is referred to as the spanning ratio of $H$. Throughout this paper, we consider $G$ to be the complete graph with edges weighted by Euclidean distance. The undirected ${\text{Yao}}_4$ graph was first proved to be a spanner by Bose et al. [9] with a stretch factor of approximately $662$. As part of the proof, the authors established that the undirected ${\text{Yao}}_4^{\mathrm{\infty }}$ graph is an $8$-spanner. Then, Bonichon et al. [6] proved that the ${\text{Yao}}_4^{\mathrm{\infty }}$ graph has spanning ratio at most $6.31$. Later, Damian and Nelavalli [14] improved both results by showing that the ${\text{Yao}}_4$ and ${\text{Yao}}_4^{\mathrm{\infty }}$ graphs have spanning ratios of at most $54.62$ and $4.93$, respectively. We will denote the directed versions of these graphs using an arrow: for example, the directed version of ${\text{Yao}}_4^{\mathrm{\infty }}$ is denoted $\overrightarrow{{\text{Yao}}_4^{\mathrm{\infty }}}$. Despite being a natural construction, the $\overrightarrow{{\text{Yao}}_4^{\mathrm{\infty }}}$ graph previously had no known upper bound on the spanning ratio. The spanning ratio of the $L_{\mathrm{\infty }}$-Delaunay graph was originally shown to be at most $\sqrt{10}\approx 3.16$ by Chew [13]. Then, Bonichon et al. [5] improved the spanning ratio of the $L_{\mathrm{\infty }}$-Delaunay triangulation to $\sqrt{4+2\sqrt{2}}\approx 2.61$, which is tight. Their lower bound construction also shows that ${\text{Yao}}_4^{\mathrm{\infty }}$ has a spanning ratio of at least $2.61$.

While spanning ratios deal with the existence of short paths, routing ratios are based on finding short directed paths with only local information. Roughly speaking, a path-finding algorithm has routing ratio $c$ if the paths produced have length at most $c$ times the straight-line distance from source to destination. In the context of planar graphs, Chew gave a local routing algorithm for $L_{\mathrm{\infty }}$-Delaunay graphs in 1986 [13]. An $L_{\mathrm{\infty }}$-Delaunay graph can contain nearly $6|V|$ directed edges in the worst case. Since then, Bonichon et al. [4] defined a number of bounded-degree planar spanners, including $G_9$ and $G_{12}$. In [10], local routing algorithms were provided for these graphs. A parametrized construction, denoted $ℳℬ𝒟𝒢$, was used in [2] to attain several lightness properties. In all of these planar graphs, the number of directed edges required is still on the order of $6|V|$. In this paper, we define a local routing algorithm for the $\overrightarrow{{\text{Yao}}_4^{\mathrm{\infty }}}$ graph, which contains at most $4|V|$ directed edges, which is the fewest number of edges among all planar directed graphs that admit a local routing algorithm.

In any bounded out-degree graph, each vertex only needs to store a constant amount of information to fully describe its outgoing neighbourhood. As a result, bounded out-degree directed graphs are a natural setting for local routing. For example, when $k$ is larger than $6$, the optimal local routing algorithm for $\overrightarrow{{\text{Yao}}_k}$ graphs is simply cone routing, where each decision is to move to the neighbour in the same cone as the destination. For smaller values of $k$, the $\overrightarrow{{\text{Yao}}_k}$ graph is less dense and cone routing can fail to produce short paths. However, [16] provides a local routing algorithm for the $\overrightarrow{{\text{Yao}}_6}$ graph with routing ratio at most $22.94$. The smallest possible $k$ for which the $\overrightarrow{{\text{Yao}}_k}$ graph is strongly connected is $k=4$, and Bose et al. [11] recently provided a local routing algorithm achieving a routing ratio of at most $23.36$ for $\overrightarrow{{\text{Yao}}_4}$ graphs. Furthermore, they show how to modify the path output by their local routing algorithm to upper bound the spanning ratio by $16.54$ for undirected ${\text{Yao}}_4$ graphs. Interestingly, their algorithm is based on the Greedy/Sweep algorithm from [7] which has a routing ratio of $17$ in the directed ${\overrightarrow{\mathrm{\Theta }}}_4$ graph.

Our local routing algorithm extends the Greedy/Sweep approach from ${\overrightarrow{\mathrm{\Theta }}}_4$ graphs to $\overrightarrow{{\text{Yao}}_4^{\mathrm{\infty }}}$ graphs. The original Greedy/Sweep algorithm is quite simple. If the current vertex is $u$ and the target vertex is $t$, then we consider the right triangle $T$ bounded by vertical and horizontal lines through $u$ and a diagonal line through $t$ with slope $-1$. If no vertices are in $T$, we say that $T$ is clean and we take a greedy step in the cone containing $t$. Otherwise, if $T$ is not clean, then we take a sweeping step in the cone of $T$. The authors of [11] adapted the Greedy/Sweep approach to $\overrightarrow{{\text{Yao}}_4}$ graphs by replacing the right triangle with a wedge. However, in the case of $\overrightarrow{{\text{Yao}}_4^{\mathrm{\infty }}}$ graphs, a direct application of the Greedy/Sweep approach fails miserably, resulting in long paths. The main challenge is that sweeping steps can cross the diagonal while making negligible progress towards the destination. To overcome this, we modify the definition of clean to penalize such diagonal crossings and force provable progress toward the target. Given our redefinition of cleanliness, we refer to our local routing algorithm as the DIRTY Algorithm (Directed Infinity Routing Through Yao). Our analysis yields an upper bound of $85.22$ on the routing ratio of our local routing algorithm.

Notice that our routing ratio of $85.22$ is also the best known upper bound on the spanning ratio for $\overrightarrow{{\text{Yao}}_4^{\mathrm{\infty }}}$ graphs. Next, we give a lower bound of $5+\sqrt{2}\approx 6.41$ on the spanning ratio of $\overrightarrow{{\text{Yao}}_4^{\mathrm{\infty }}}$ graphs in the worst case, highlighting a clear gap compared to the upper bound of $4.93$ for ${\text{Yao}}_4^{\mathrm{\infty }}$ graphs. Finally, we prove that no local routing algorithm for $\overrightarrow{{\text{Yao}}_4^{\mathrm{\infty }}}$ graphs can achieve a routing ratio below $7+\sqrt{2}\approx 8.41$. Additionally, we use a similar technique to provide lower bounds of $7-\sqrt{3}+\sqrt{5-2\sqrt{3}}\approx 6.51$ and $7+\sqrt{2}$ for the spanning and routing ratios of $\overrightarrow{{\text{Yao}}_4}$, respectively.

For any point $u\in {ℝ}^2$, we let $x(u)$ and $y(u)$ denote the $x$- and $y$-coordinates of $u$, respectively. We denote the line segment between points $u,v$ as $uv$, and define ${\Vert uv\Vert }_x:=|x(u)-x(v)|$ and ${\Vert uv\Vert }_y:=|y(u)-y(v)|$. For $p\in [1,\mathrm{\infty })$, the $L_p$-length of $uv$ is denoted ${\Vert uv\Vert }_p:={({\Vert uv\Vert }_x^p+{\Vert uv\Vert }_y^p)}^{\frac{1}{p}}$. We also define ${\Vert uv\Vert }_{\mathrm{\infty }}:=\max ({\Vert uv\Vert }_x,{\Vert uv\Vert }_y)$. A geometric graph is a graph whose vertex set contains points in the plane and whose edge weights are the $L_2$ (Euclidean) lengths of the corresponding line segments. In a geometric graph, each vertex is identified with its coordinates. Throughout the paper, we make the general position assumption that no two vertices have the same $x$- or $y$-coordinates and all distances between pairs of vertices are unique in the $L_{\mathrm{\infty }}$-norm. On such a point set, the edges of the $\overrightarrow{{\text{Yao}}_4^{\mathrm{\infty }}}$ graph are well-defined. For two vertices $u,v$ in a geometric graph $G$, the length of the shortest path from $u$ to $v$ in $G$ is denoted $d_G(u,v)$. Then for a constant $c\ge 1$, $G$ is said to be a $c$-spanner if for all points $u,v$ in $G$, we have $d_G(u,v)\le c{\Vert uv\Vert }_2$. The spanning ratio of $G$ is the least $c$ for which $G$ is a $c$-spanner. The spanning ratio of a class of graphs $𝒢$ is the least $c$ for which all graphs in $𝒢$ are $c$-spanners.

We make the assumption that the graph is embedded on a polynomial-sized grid and therefore the coordinates of the points require $O(\log (n))$ bits. Formally, an $m$-memory local routing algorithm is a function that takes as input $(s,N(s),t,M)$, and outputs some memory $M^{\prime }$ and a vertex $p\in N(s)$ where $s$ is the current vertex, $N(s)$ is the outgoing neighbourhood of $s$, $t$ is the destination, and both $M,M^{\prime }$ are bit-strings of length $m$. An algorithm is said to be $c$-competitive for a family of geometric graphs $𝒢$ if the path output by the algorithm for any pair of vertices $s,t\in V(G)$ for $G\in 𝒢$ has length at most $c{\Vert st\Vert }_2$. The routing ratio of an algorithm is the least $c$ for which the algorithm is $c$-competitive for $𝒢$. Note that the routing ratio is an upper bound on the spanning ratio.

We will now describe our local routing algorithm for $\overrightarrow{{\text{Yao}}_4^{\mathrm{\infty }}}$ graphs. Without loss of generality, assume the coordinates of $t$ are $(0,0)$ and ${\Vert st\Vert }_{\mathrm{\infty }}=1$. Let , and define the green square to be the set of points $p\in {ℝ}^2$ such that ${\Vert pt\Vert }_{\mathrm{\infty }}\le 2\delta$. In addition, we define the diagonal lines ${\mathrm{\ell }}_t^{-},{\mathrm{\ell }}_t^{+}$ with slope $\pm 1$ passing through $t$. Define the north, east, south and western quadrants as the cones delimited by ${\mathrm{\ell }}_t^{+}$ and ${\mathrm{\ell }}_t^{-}$. Refer to the four cones as , $\text{<object type="image/svg+xml" data="Yao4InftyRR-page-33.pdf2svg.svg" id="S3.p1.m15.g1nest" class="ltx\_graphics ltx\_img\_square" width="15" height="15" style="width: 30px; height: unset; max-width: 100\%"></object>},$ $\text{<object type="image/svg+xml" data="Yao4InftyRR-page-31.pdf2svg.svg" id="S3.p1.m16.g1nest" class="ltx\_graphics ltx\_img\_square" width="15" height="15" style="width: 30px; height: unset; max-width: 100\%"></object>},$ , respectively.

Next, for a point $p\in {ℝ}^2$, we define its height, $h(p)$, as the $L_1$ distance from $p$ to the nearest diagonal through $t$. Notice that $h(p)=||x(p)|-|y(p)||$. The bands, denoted by , are the regions close to the diagonals, excluding the green square. More precisely, let refer to the set of points $p\in {ℝ}^2$ such that $p\notin \text{<object type="image/svg+xml" data="Yao4InftyRR-page-34.pdf2svg.svg" id="S3.p2.m10.g1nest" class="ltx\_graphics ltx\_img\_square" width="15" height="15" style="width: 30px; height: unset; max-width: 100\%"></object>}$ and $h(p)\le \delta$. Refer to Figure 1. Note that $\text{<object type="image/svg+xml" data="Yao4InftyRR-page-26.pdf2svg.svg" id="S3.p2.m12.g1nest" class="ltx\_graphics ltx\_img\_square" width="15" height="15" style="width: 30px; height: unset; max-width: 100\%"></object>}\subset {ℝ}^2$ and is composed of four regions, which we label $\text{<object type="image/svg+xml" data="Yao4InftyRR-page-25.pdf2svg.svg" id="S3.p2.m13.g1nest" class="ltx\_graphics ltx\_img\_square" width="15" height="15" style="width: 30px; height: unset; max-width: 100\%"></object>},\text{<object type="image/svg+xml" data="Yao4InftyRR-page-36.pdf2svg.svg" id="S3.p2.m13.g2nest" class="ltx\_graphics ltx\_img\_square" width="15" height="15" style="width: 30px; height: unset; max-width: 100\%"></object>},\text{<object type="image/svg+xml" data="Yao4InftyRR-page-54.pdf2svg.svg" id="S3.p2.m13.g3nest" class="ltx\_graphics ltx\_img\_square" width="15" height="15" style="width: 30px; height: unset; max-width: 100\%"></object>},\text{<object type="image/svg+xml" data="Yao4InftyRR-page-55.pdf2svg.svg" id="S3.p2.m13.g4nest" class="ltx\_graphics ltx\_img\_square" width="15" height="15" style="width: 30px; height: unset; max-width: 100\%"></object>}$ clockwise from the north-eastern region. Then define the truncated wedges as those points $p\in {ℝ}^2$ such that $p\notin \text{<object type="image/svg+xml" data="Yao4InftyRR-page-34.pdf2svg.svg" id="S3.p2.m16.g1nest" class="ltx\_graphics ltx\_img\_square" width="15" height="15" style="width: 30px; height: unset; max-width: 100\%"></object>}\cup \text{<object type="image/svg+xml" data="Yao4InftyRR-page-26.pdf2svg.svg" id="S3.p2.m16.g2nest" class="ltx\_graphics ltx\_img\_square" width="15" height="15" style="width: 30px; height: unset; max-width: 100\%"></object>}$. We have $\text{<p class="ltx\_p"><object type="image/svg+xml" data="Yao4InftyRR-page-28.pdf2svg.svg" id="S3.p2.m17.g1nest" class="ltx\_graphics ltx\_img\_square" width="15" height="15" style="width: 30px; height: unset; max-width: 100\%"></object></p>}\subset {ℝ}^2$ and since is composed of four regions, we label them $\text{<object type="image/svg+xml" data="Yao4InftyRR-page-35.pdf2svg.svg" id="S3.p2.m19.g1nest" class="ltx\_graphics ltx\_img\_square" width="15" height="15" style="width: 30px; height: unset; max-width: 100\%"></object>},\text{<object type="image/svg+xml" data="Yao4InftyRR-page-27.pdf2svg.svg" id="S3.p2.m19.g2nest" class="ltx\_graphics ltx\_img\_square" width="15" height="15" style="width: 30px; height: unset; max-width: 100\%"></object>},\text{<object type="image/svg+xml" data="Yao4InftyRR-page-57.pdf2svg.svg" id="S3.p2.m19.g3nest" class="ltx\_graphics ltx\_img\_square" width="15" height="15" style="width: 30px; height: unset; max-width: 100\%"></object>},\text{<object type="image/svg+xml" data="Yao4InftyRR-page-56.pdf2svg.svg" id="S3.p2.m19.g4nest" class="ltx\_graphics ltx\_img\_square" width="15" height="15" style="width: 30px; height: unset; max-width: 100\%"></object>}$ clockwise from the northern region.

Next we describe the terminology used in our local routing algorithm, which we will refer to as DIRTY Algorithm 1 (Directed Infinity Routing Through Yao). For any vertex $u\in \text{<object type="image/svg+xml" data="Yao4InftyRR-page-26.pdf2svg.svg" id="S3.p3.m1.g1nest" class="ltx\_graphics ltx\_img\_square" width="15" height="15" style="width: 30px; height: unset; max-width: 100\%"></object>}$, a band step from $u$ follows the edge in the cone of $u$ containing $t$. For any vertex $u\in \text{<p class="ltx\_p"><object type="image/svg+xml" data="Yao4InftyRR-page-28.pdf2svg.svg" id="S3.p3.m5.g1nest" class="ltx\_graphics ltx\_img\_square" width="15" height="15" style="width: 30px; height: unset; max-width: 100\%"></object></p>}$, $u$ is clean if the quadrant of $u$ facing the closest diagonal ${\mathrm{\ell }}_t\in \{{\mathrm{\ell }}_t^{-},{\mathrm{\ell }}_t^{+}\}$ does not contain any vertex $v$ such that ${\Vert uv\Vert }_{\mathrm{\infty }}+\delta \le h(u)$. Intuitively, $u$ is clean if there are no points between $u$ and the nearest diagonal. For example, see Figure 1. A sweep step from $u$ follows the edge in the cone towards the closest diagonal to $u$. We denote the vertex resulting from a sweep step from $u$ as $\text{Sweep}(u,t,N(u),\delta )$. A greedy step from $u$ follows the edge in the cone of $u$ containing $t$. The vertex resulting from a greedy step from $u$ is denoted $\text{Greedy}(u,t,N(u))$. Note that a band step is technically a greedy step, however we will distinguish band steps from greedy steps in the analysis. Now we will present the local routing algorithm. In short, if there is a neighbour in the green square, then we choose it and rescale $\delta$. On the other hand, we take a greedy edge if the current vertex is in or is clean. When the current vertex is not clean, we take a sweep edge. A partial trace of Algorithm 1 is shown in Figure 1. The constant in step 1 of Algorithm 1 will be set to $0.08$, however the analysis holds for a general $c$. Furthermore, $\delta$ should be set to $c{\Vert st\Vert }_{\mathrm{\infty }}$ for the first call of Algorithm 1.