Optimal Distance Labeling for Permutation Graphs¹¹1Partially supported by the Polish National Science Centre grant number 2023/51/B/ST6/01505.

Take any shortest path $P^{\prime }$ and any adjacent $q_i$ and $q_{i+1}$ on $P^{\prime }$, assume without loss of generality that $q_{i+1}\in {\mathrm{𝖳𝖫}}_{q_i}$. Suppose that $q_{i+1}$ is not on the top boundary. We either have $q_{i+2}\in {\mathrm{𝖳𝖫}}_{q_i+1}$ or $q_{i+2}\in {\mathrm{𝖡𝖱}}_{q_i+1}$. Note that by transitivity if $q_{i+2}\in {\mathrm{𝖳𝖫}}_{q_{i+1}}$, then $q_{i+2}\in {\mathrm{𝖳𝖫}}_{q_i}$ and we could have a shorter path by removing $q_{i+1}$. Thus, assume $q_{i+2}\in {\mathrm{𝖡𝖱}}_{q_{i+1}}$. If $q_{i+1}$ is not on the top boundary, then by definition there exists a boundary point $q^{\prime }\in {\mathrm{𝖳𝖫}}_{q_{i+1}}$, and it must be that $q_{i+2}\in {\mathrm{𝖡𝖱}}_{q^{\prime }}$. This means that we could replace $q_{i+1}$ by $q^{\prime }$, increasing the number of points from the path lying on the boundary, and then repeat the argument. Therefore, we have that all points except the first and last ones can always lie on boundaries. See Figure 6 for an illustration. These must be alternating boundaries, as by definition no two points on the same boundary are adjacent. $◀$

We partition all points on the boundaries into layers, in the following way. Layer 0 consists of a single left-most point $p_0$ in the whole set $S$. Note that $p_0$ is on the top boundary. Then, a boundary point is in a layer number $i$ if its distance to $p_0$ is $i$. By $L(u)$ we denote the layer number of $u$. See Figure 7 for some intuition, we will soon see that indeed layers are always nicely structured, as pictured. Observe that in even layers, we have only points from the top boundary, and in odd layers only from the bottom boundary, as points on a single boundary are non-adjacent. Thus, points in a single layer are ordered, by both coordinates.

To determine the distance between boundary points, we use a method similar to the one from the paper of Gavoille and Paul [28], precisely Theorem 3.8. This is also connected to what Bazzaro and Gavoille [12] do in their work, but not identical, as they use bottom and top boundaries separately, as two almost independent interval graphs.

As noted, points on both boundaries are ordered, and layers switch between boundaries, starting with layer 0 containing just a single left-most point from the top layer. Say ordered points on the top layer are $t_0,t_1,t_2,\mathrm{\dots }$. We prove that there exist strictly increasing numbers $i_0=0,i_2,i_4,\mathrm{\dots }$ such that layer 0 consists of $t_0$, and then any layer $2k$ consists of consecutive points $t_{i_{2k-2}+1},\mathrm{\dots },t_{i_{2k}}$. Similarly, for points $b_0,b_1,\mathrm{\dots }$ on bottom layer, there exists numbers $i_1,i_3,\mathrm{\dots }$ defining analogous ranges. Denote by $\mathrm{𝗅𝖺𝗌𝗍}(q)$ the last point (with largest coordinates) in layer $q$. We prove by induction, in a given order, some intuitive properties (focusing without loss of generality on an odd layer):

The properties for layer $2k+1=1$ are apparent, except for the third point, which can be done as in the induction step. Now consider layer $2k+1$. As all points from layer $2k$ are adjacent to $\mathrm{𝗅𝖺𝗌𝗍}(2k-1)$, meaning they are in ${\mathrm{𝖳𝖫}}_{\mathrm{𝗅𝖺𝗌𝗍}(2k-1)}$, all these points are to the left of points from layer $2k+1$. Moreover, the last point in layer $2k$ has the largest $y$ coordinate, thus if any point from layer $2k+1$ is adjacent to some point from layer $2k$, then it is also adjacent to $\mathrm{𝗅𝖺𝗌𝗍}(2k)$. This gives us the first two properties.

Now, by definition, if points $b_q,b_r$ with $r>q$ are adjacent to some point $v$ on the top boundary, then all points $b_q,b_{q+1},\mathrm{\dots },b_r$ are adjacent to $v$. Thus, if $b_{i_{2k-1}+1}$ is adjacent to $\mathrm{𝗅𝖺𝗌𝗍}(2k)$, we get the third property. But it must be adjacent, as otherwise it would be above $\mathrm{𝗅𝖺𝗌𝗍}(2k)$, and then layer $2k+1$ would be empty. We can apply the above principles to any point from layer $2k$ - it either neighbours the first point in layer $2k+1$ or no point from this layer. This means any point from layer $2k$ neighbours prefix of points from layer $2k+1$ (possibly empty, possibly full layer). Moreover $t_{j+1}$ is adjacent to the same points from layer $2k+1$ that $t_j$ is, and possibly more, as $t_{j+1}$ is above $t_j$. See Figure 8. $◀$

By the definition of layers, for points $u,v$, $d(u,v)\ge |L(u)-L(v)|$. If $d(u,v)=|L(u)-L(v)|$, we say that there is a quick path between them. Going back to the statement of the lemma, it says there exists an ordering $\lambda$ of boundary points such that there is a quick path between two points exactly when relations between their $\lambda$ values and layer numbers are opposite. We can create ordering $\lambda$ in the following greedy way: starting from $\lambda$ value of 1, always assign current value to the lowest point in the lowest layer such that it is adjacent to no points in the next layer without $\lambda$ values already assigned, then increment current value. In other words, if we direct all edges from lower to higher layers, we repeatedly choose the lowest (by layer) possible sink, assign to it the current value, and remove the sink from the graph. This is always possible, at the extreme case we can always choose a point from the highest layer containing points without assigned $\lambda$ value. See Figure 9 for an example.

For correctness, observe that when we choose $v$ from layer $k$, for all layers larger than $k$ the last point with assigned value is adjacent to all points with assigned values in the next layer. This is by the greedy procedure, as assume there is a layer $j>k$ such that $u$, the last point with assigned value in layer $j$, is not adjacent to $w$, the last point with assigned value in layer $j+1$. It cannot be that , as $w$ does not need to be processed by the greedy procedure before choosing $u$. But $\lambda (w)>\lambda (u)$ is also impossible by definition of the procedure, since $w$ cannot be processed at any moment after choosing $u$ and before choosing $v$, as no other point from layer $j$ was chosen between these events and procedure prioritises lower layers. Now, using the above, we can observe that at the moment we assign value for point $v$ in layer $k$:

• $\mathrm{■}$

  There are quick paths from $v$ to all points with assigned values and in layers larger than $k$. This is true by the choice of $v$ and transitivity. It is given that $v$ is adjacent to all points in layer $k+1$ with assigned values, then the last of these points is adjacent to all points in layer $k+2$ with assigned values, and so on.

• $\mathrm{■}$

  There are no quick paths from $v$ to any point without assigned value in a layer larger than $k$. This is clear from the greedy procedure, since points are chosen only when all their neighbours from the next layer got assigned values.

$◀$

By Lemma 4, we are able to detect when quick paths exist, and to complete knowledge about distances between boundary points we observe the following:

First let us argue that $d(u,v)\le L(v)-L(u)+2$. We observed $\mathrm{𝗅𝖺𝗌𝗍}(i)$ is adjacent to all points in layer $i+1$. Thus, $(u,\mathrm{𝗅𝖺𝗌𝗍}(L(u)-1),\mathrm{𝗅𝖺𝗌𝗍}(L(u)),\mathrm{𝗅𝖺𝗌𝗍}(L(u)+1),\mathrm{\dots },\mathrm{𝗅𝖺𝗌𝗍}(L(v)-1),v)$ is always a correct path with length $L(v)-L(u)+2$. By definition of layers, $d(u,v)$ cannot be less than $L(v)-L(u)$. Finally, by Proposition 3 there is a shortest path that alternates between boundaries, so it cannot be of length $L(v)-L(u)+1$, as we cannot change parity. $◀$

To simplify our proofs, we will add some points to the original set. For each point $v$ on the bottom boundary and from the original input, we add point $(v_x+ϵ,v_y-ϵ)$. It is easy to see that as such a point lies on the bottom boundary, adding it does not change distances between any existing points, and it removes $v$ from the bottom boundary. Then we normalise the coordinates so that they are integers, increasing the range of numbers by some constant factor. Similarly, for any original point $v$ on top boundary, we add $(v_x-ϵ,v_y+ϵ)$. What we achieve is that after this change no point from the original input lies on the boundary, which reduces the number of cases one needs to consider when assigning labels (only to the original points).

Now let us focus on any point $v$ not on the boundary. Assume $v$ is adjacent to some points from layers $i$ and $j$, $j>i$. It cannot be that $j>i+2$, by definition of layers as distances from $p_0$. Thus, $v$ is adjacent to points from at most three (consecutive) layers. We note that $v$ is adjacent to a consecutive segment of ordered points from any layer $i$. Let us denote by $\mathrm{𝖡𝖿𝗂𝗋𝗌𝗍}(v)$ and $\mathrm{𝖡𝗅𝖺𝗌𝗍}(v)$ the first and last points on the bottom boundary adjacent to $v$ and by $\mathrm{𝖳𝖿𝗂𝗋𝗌𝗍}(v)$ and $\mathrm{𝖳𝗅𝖺𝗌𝗍}(v)$ the first and last points on the top boundary adjacent to $v$. Consult Figure 10.

We can make easy observation on points at distance two:

This is since by Proposition 3, we must have a path between $u,v$ at distance two going through a single point on the boundary. In the case of $d(u,v)=1$, assume without loss of generality that $u\in {\mathrm{𝖳𝖫}}_v$, then $[\mathrm{𝖳𝖿𝗂𝗋𝗌𝗍}(u),\mathrm{𝖳𝗅𝖺𝗌𝗍}(u)]\subseteq [\mathrm{𝖳𝖿𝗂𝗋𝗌𝗍}(v),\mathrm{𝖳𝗅𝖺𝗌𝗍}(v)]$, and ranges are never empty.

Considering points at a distance of at least three, we have the following:

We will prove the statement for the second point, as the penultimate point is symmetric. By Proposition 3 there always exists a shortest path $P$ with all but extreme points lying on alternating boundaries, with $P=(u=q_0,q_1,q_2,\mathrm{\dots },w,q_{d(u,v)}=v)$, so we denote the penultimate point by $w$.

Consider layer number of $w$. As $d(u,v)>2$ and , it must be that $v,w\in {\mathrm{𝖳𝖱}}_u$ and so $L(w)\ge \min (L(\mathrm{𝖳𝗅𝖺𝗌𝗍}(u)),L(\mathrm{𝖡𝗅𝖺𝗌𝗍}(u)))$. If $L(w)\ge \max (L(\mathrm{𝖳𝗅𝖺𝗌𝗍}(u)),L(\mathrm{𝖡𝗅𝖺𝗌𝗍}(u)))$, then by Proposition 6 and Lemma 4 we can replace $q_1$ with $\mathrm{𝖡𝗅𝖺𝗌𝗍}(u)$ or $\mathrm{𝖳𝗅𝖺𝗌𝗍}(u)$ (which have the largest $\lambda$ values in their layers among neighbours of $u$), while keeping the length of $P$ and $w$ as penultimate point. We are left with $L(w)=\min (L(\mathrm{𝖳𝗅𝖺𝗌𝗍}(u)),L(\mathrm{𝖡𝗅𝖺𝗌𝗍}(u)))$. Assume $L(\mathrm{𝖡𝗅𝖺𝗌𝗍}(u))>L(\mathrm{𝖳𝗅𝖺𝗌𝗍}(u))$, so $L(w)=L(\mathrm{𝖳𝗅𝖺𝗌𝗍}(u))$ and also $w>\mathrm{𝖳𝗅𝖺𝗌𝗍}(u)$. Then $w$ is adjacent to $\mathrm{𝗅𝖺𝗌𝗍}(L(w)-1)\in {\mathrm{𝖡𝖱}}_u$ and thus also to $\mathrm{𝖡𝗅𝖺𝗌𝗍}(u)$, so we can have $q_1=\mathrm{𝖡𝗅𝖺𝗌𝗍}(u)$. In other case, we could similarly set $q_1=\mathrm{𝖳𝗅𝖺𝗌𝗍}(u)$. Thus, we can always change $q_1$ to be $\mathrm{𝖡𝗅𝖺𝗌𝗍}(u)$ or $\mathrm{𝖳𝗅𝖺𝗌𝗍}(u)$, without changing $w$. $◀$

We established ways to determine the distance between any points using distances between specific boundary points. Additionally, observe that all conditions from Lemma 4 and Proposition 7 can be checked using just $\lambda$ values and layer numbers. That is, for $u,v$ on the same boundary we have $u\le v$ iff $(L(u),\lambda (u)){\le }_{lex}(L(v),\lambda (v))$.

At this stage, we could create labels of length $(2+4+1)\log n+𝒪(1)=7\log n+𝒪(1)$, by storing for each point $v$ coordinates $v_x,v_y$, and for all points of interest $\mathrm{𝖡𝖿𝗂𝗋𝗌𝗍}(v),\mathrm{𝖡𝗅𝖺𝗌𝗍}(v),\mathrm{𝖳𝖿𝗂𝗋𝗌𝗍}(v)$, and $\mathrm{𝖳𝗅𝖺𝗌𝗍}(v)$, their $\lambda (\cdot )$ and $L(\cdot )$ values. As a point is adjacent to at most three layers, all four layer numbers can be stored on just $\log n+𝒪(1)$ bits. Coordinates allow us to check for distance 1, distance two is checked by using Proposition 7, and larger distances by Proposition 6, Lemma 4 and 8.

Considering the first property, we need to observe that when adding a point, its bottom-right quadrant is empty. For $v_{b^{\prime }}$ it holds as the point is between $\mathrm{𝖡𝗅𝖺𝗌𝗍}(v)$ and the next point on the bottom boundary on both axes. Thus it changes the status of no point on the bottom boundary and itself is on this boundary. We have a similar situation with $v_b$.

For the second property, we notice that any point adjacent to $v_{b^{\prime }}$ is also adjacent to $\mathrm{𝖡𝗅𝖺𝗌𝗍}(v)$. Since $v_{b^{\prime }}$ and $\mathrm{𝖡𝗅𝖺𝗌𝗍}(v)$ lie on the bottom boundary, any adjacent point must be in their top-left quadrant. As $v_{b^{\prime }}=(\mathrm{𝖡𝗅𝖺𝗌𝗍}{(v)}_x+ϵ,v_y+ϵ)$ and there are no points with $x$-coordinate between $\mathrm{𝖡𝗅𝖺𝗌𝗍}{(v)}_x$ and $\mathrm{𝖡𝗅𝖺𝗌𝗍}{(v)}_x+ϵ$, if some point is to the left of $v_{b^{\prime }}$, it is also to the left of $\mathrm{𝖡𝗅𝖺𝗌𝗍}(v)$, and by definition we have $v_{b^{\prime }y}>v_y>\mathrm{𝖡𝗅𝖺𝗌𝗍}{(v)}_y$. Similarly, any point adjacent to $v_b$ is also adjacent to $\mathrm{𝖡𝖿𝗂𝗋𝗌𝗍}(v)$. Therefore, these points cannot offer any shortcuts in existing shortest paths. $◀$

Similarly, for each point in the initial set, we add two points on the upper boundary. That is, consider $v$ and ${\mathrm{𝖳𝖫}}_v$. We add two points $v_t=(\mathrm{𝖳𝖿𝗂𝗋𝗌𝗍}{(v)}_x-ϵ,v_y-ϵ)$ and $v_{t^{\prime }}=(v_x+ϵ,\mathrm{𝖳𝗅𝖺𝗌𝗍}{(v)}_y+ϵ)$ to the set $S$ of points. Then, we again normalise the coordinates. This is symmetric and has the same properties.

After adding four auxiliary points for all initial points, we have the desired property:

The cases for both boundaries are symmetrical, so we focus on the bottom one.

If $w\in {\mathrm{𝖡𝖱}}_v$, then by transitivity $v$ is adjacent to $\mathrm{𝖡𝖿𝗂𝗋𝗌𝗍}(w)$, and then by definition of $w_b$, $v$ is also adjacent to $w_b$. As , we get . Analogous facts hold for $w_{b^{\prime }}$, therefore implication in the right direction holds.

We consider the left direction and use contraposition. Firstly, we want to show that if $w\notin {\mathrm{𝖡𝖱}}_v$, then either $\mathrm{𝖡𝖿𝗂𝗋𝗌𝗍}(v)>\mathrm{𝖡𝖿𝗂𝗋𝗌𝗍}(w)$ or $\mathrm{𝖡𝗅𝖺𝗌𝗍}(w)>\mathrm{𝖡𝗅𝖺𝗌𝗍}(v)$. $w\notin {\mathrm{𝖡𝖱}}_v$ means or $w_y>v_y$. Assume and $\mathrm{𝖡𝖿𝗂𝗋𝗌𝗍}(v)\le \mathrm{𝖡𝖿𝗂𝗋𝗌𝗍}(w)$. This can be only if $\mathrm{𝖡𝖿𝗂𝗋𝗌𝗍}(v)=\mathrm{𝖡𝖿𝗂𝗋𝗌𝗍}(w)$, since $w$ is to the left of $v$ and points on boundaries are ordered. As $v_b$ is below $\mathrm{𝖡𝖿𝗂𝗋𝗌𝗍}(v)$ and between $w_x$ and $v_x$, it must be that $v_b\in {\mathrm{𝖡𝖱}}_w$. So we have $v_b\in {\mathrm{𝖡𝖱}}_w$ and , a contradiction, as then $v_b$ should be $\mathrm{𝖡𝖿𝗂𝗋𝗌𝗍}(w)$. Similarly using $v_{b^{\prime }}$ we can show that assuming $w_y>v_y$ and $\mathrm{𝖡𝗅𝖺𝗌𝗍}(w)\le \mathrm{𝖡𝗅𝖺𝗌𝗍}(v)$ leads to a contradiction. See Figure 13. $◀$

The above lemma is useful when testing for adjacency of points – we do not need explicit coordinates to check it. Now, we are able to create labels of length $5\log n+𝒪(1)$, as there is no longer a need to store coordinates, thus just the four $\lambda$ values, and additionally the layer numbers using only $\log n+𝒪(1)$ bits.