# Improved Compression of the Okamura-Seymour Metric

Shay Mozes  The Interdisciplinary Center Herzliya, Israel
<EMAIL_ADDRESS>Nathan Wallheimer  University of Haifa, Israel
<EMAIL_ADDRESS><EMAIL_ADDRESS>Oren Weimann  University of Haifa,
Israel
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Let $G=(V,E)$ be an undirected unweighted planar graph. Consider a vector
storing the distances from an arbitrary vertex $v$ to all vertices
$S=\\{s_{1},s_{2},\ldots,s_{k}\\}$ of a single face in their cyclic order. The
pattern of $v$ is obtained by taking the difference between every pair of
consecutive values of this vector. In STOC’19, Li and Parter used a VC-
dimension argument to show that in planar graphs, the number of distinct
patterns, denoted $x$, is only $O(k^{3})$. This resulted in a simple
compression scheme requiring $\tilde{O}(\min\\{k^{4}+|T|,k\cdot|T|\\})$ space
to encode the distances between $S$ and a subset of terminal vertices
$T\subseteq V$. This is known as the Okamura-Seymour metric compression
problem.

We give an alternative proof of the $x=O(k^{3})$ bound that exploits planarity
beyond the VC-dimension argument. Namely, our proof relies on cut-cycle
duality, as well as on the fact that distances among vertices of $S$ are
bounded by $k$. Our method implies the following:
(1) An $\tilde{O}(x+k+|T|)$ space compression of the Okamura-Seymour metric,
thus improving the compression of Li and Parter to
$\tilde{O}(\min\\{k^{3}+|T|,k\cdot|T|\\})$.
(2) An optimal $\tilde{O}(k+|T|)$ space compression of the Okamura-Seymour
metric, in the case where the vertices of $T$ induce a connected component in
$G$.
(3) A tight bound of $x=\Theta(k^{2})$ for the family of Halin graphs, whereas
the VC-dimension argument is limited to showing $x=O(k^{3})$.

##  1 Introduction

Planar metric compression. The shortest path metric of planar graphs is one of
the most popular and well-studied metrics in computer science. The planar
graph metric compression problem is to compactly encode the distances between
a subset of $k$ terminal vertices so that we can retrieve the distance between
any pair of terminals from the encoding. On an $n$-vertex planar graph
$G=(V,E)$, a naïve encoding uses $\tilde{O}(\min\\{k^{2},n\\})$ bits (by
either storing the $k\times k$ distance matrix or alternatively by storing the
entire graph111Naïvely, this takes $O(n\log n)$ bits, but can be done with
$O(n)$ bits [30, 26, 10, 4].). It turns out that this naïve bound is actually
optimal (up to logarithmic factors) for weighted planar graphs, as shown by
Gavoille et al. [16]. It is important to note that their lower bound applies
even when all terminals lie on a single face. The complexity of unweighted
undirected planar graphs is also well-understood. Gavoille et al. [16] (see
also [1]) gave a lower bound of $\Omega(\min\\{k^{2},\sqrt{k\cdot n}\\})$, and
Abboud et al. [1] gave a matching upper bound.

If we are willing to settle for approximate distances, then there are
ingenious compressions requiring only $\tilde{O}(k)$ bits [29, 22, 21]. The
problem has also been extensively studied (both in the exact [24, 23, 9, 6, 7,
17] and the approximate [18, 2, 5, 19, 8, 13, 14] settings) for the case where
we require that the compression is itself a graph (that contains the terminals
and preserves their distances).

#### The Okamura-Seymour metric compression.

An important special case for which tight bounds are not yet known, is when
the planar graph is unweighted and undirected and we want to encode the
$S\times T$ distances between a set of $k$ source terminals
$S=\\{s_{1},s_{2},\ldots,s_{k}\\}$ lying consecutively on a single face and a
subset of target terminal vertices $T\subseteq V$. A query $(v,s_{i})$ to the
encoding (with $v\in T$ and $s_{i}\in S$) returns the $v$-to-$s_{i}$ distance.

  * •

When $T=S$, it is possible to exploit the _Unit-Monge_ property to obtain an
$O(k\log k)$ space encoding with $O(\log k)$ query time [1]. In fact, even if
$T\neq S$ the Unit-Monge property implies an (optimal) $\tilde{O}(|T|+k)$
space encoding, as long as the vertices of $T$ lie (not necessarily
consecutively) on single face.

  * •

When $T=V$, the MSSP data structure of Eisenstat and Klein [12] gives an
$O(n)$ space encoding with $O(\log n)$ query time.

  * •

For arbitrary $S,T$, Li and Parter [25] recently presented a compression of
size $\tilde{O}(\min\\{k^{4}+|T|,k\cdot|T|\\})$ and query time $O(1)$.222The
actual bound stated in [25] is $\tilde{O}(k^{3}\cdot D+|T|)$ where $D$ is the
diameter of the graph. The reason for the additional $D$ factor is that they
store all possible distance tuples $d_{v}=\\{d(v,s_{i})\\}_{i=1}^{k}$ instead
of all possible patterns $p_{v}$. The reason for the missing $k$ factor is
simply a mistake in their paper. This compression is useful algorithmically.
In the distributed setting, Li and Parter used it to compute the diameter of a
planar graph in $\tilde{O}(poly(D))$ rounds where $D$ is the graph’s diameter.
It was also used to develop an exact distance oracle with subquadratic space
and constant query time [15].

#### The Li-Parter compression.

At the heart of the Li-Parter compression [25], is the notion of a _pattern_.
Let $d(\cdot,\cdot)$ denote the shortest path metric of $G$. The pattern of a
vertex $v\in V$ is the vector

$p_{v}=\left\langle
d(v,s_{2})-d(v,s_{1}),d(v,s_{3})-d(v,s_{2}),\ldots,d(v,s_{k})-d(v,s_{k-1})\right\rangle.$

Since the graph is unweighted, every entry of $p_{v}$ is in $\\{-1,0,1\\}$ by
the triangle inequality. This already gives an efficient way to encode $v$’s
distances to $S$: Instead of explicitly storing these distances (using
$O(k\log n)$ bits), store $p_{v}$ and $d(v,s_{1})$ (using $O(k+\log n)$ bits).
This way, any distance $d(v,s_{i})$ can be retrieved by

$d(v,s_{i})=d(v,s_{1})+\sum_{j=1}^{i-1}p_{v}[j].$

The main contribution of Li and Parter in this context is in showing that,
while there are overall $n$ patterns in the graph, there are only $O(k^{3})$
distinct patterns:

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

The number of distinct patterns over all vertices of the graph is $O(k^{3})$.

The compression follows easily from the above theorem: Store one table that
contains all the distinct patterns of vertices in $T$, and another table that
contains for every $v\in T$ the value $d(v,s_{1})$ and a pointer to $p_{v}$ in
the first table. Since there cannot be more than $|T|$ distinct patterns, the
size of the first table is $O(\min\\{k^{4},k\cdot|T|\\})$. The size of the
second table is $\tilde{O}(|T|)$. The query time is $O(k)$ but can be improved
to $O(1)$ by storing precomputed prefix-sums of every pattern (increasing the
size of the first table by a logarithmic factor).

#### The original proof of Theorem 1 [25].

Let us assume that the distinguished face is the infinite face. For
convenience, we transform333This transformation was suggested by Li and Parter
in their STOC’19 talk. the problem so that patterns are binary rather than
ternary (i.e. over $\\{-1,1\\}$ instead of $\\{-1,0,1\\}$). To this end, we
subdivide every edge of the graph to get a new (unweighted) graph
$G^{\prime}$. In particular, we replace each edge $\\{s_{i},s_{i+1}\\}$ of the
infinite face with a dummy vertex $w_{i}$ and edges
$\\{s_{i},w_{i}\\},\\{w_{i},s_{i+1}\\}$. For every vertex $u$ of $G^{\prime}$,
let $\hat{p}_{u}$ be the pattern of $u$ w.r.t. the set of vertices
$S^{\prime}=\\{s_{1},w_{1},s_{2},w_{2},\ldots,s_{k},w_{k}\\}$. Observe that
the parity of $u$-to-$s_{i}$ distances is different from the parity of
$u$-to-$w_{j}$ distances, for all $i,j$’s. Hence, $\hat{p}_{u}$ is a binary
vector (i.e. over $\\{-1,1\\}$). Additionally, for every vertex $v$ of $G$ we
can retrieve its pattern $p_{v}$ from $\hat{p}_{v}$ since
$p_{v}[i]=(\hat{p}_{v}[2i-1]+\hat{p}_{v}[2i])/2$. See Figure 1. Hence, we
henceforth assume that patterns $p_{v}$ are over $\\{-1,1\\}$ (i.e. we replace
$p_{v}$ with $\hat{p}_{v}$). For brevity, we also assume that patterns are of
length $k-1$ (rather than $2k-1$).

(a)  (b)

Figure 1: Before (left) and after (right) the transformation that makes all
patterns binary. Every edge is subdivided and a new vertex (in color) is put
in the middle. In this example, $p_{v}=\langle 0,1,-1,0,1,1,-1\rangle$ and
$\hat{p}_{v}=\langle 1,-1,1,1,-1,-1,1,-1,1,1,1,1,-1,-1,-1\rangle$.

Li and Parter’s VC-dimension argument is based on the simple observation that,
by planarity, there cannot be two vertices $v$ and $u$ and 4 indices $a<b<c<d$
such that ${p}_{u}[a]=-1,{p}_{u}[b]=1,{p}_{u}[c]=-1,{p}_{u}[d]=1$ but
${p}_{v}[a]=1,{p}_{v}[b]=-1,{p}_{v}[c]=1,{p}_{v}[d]=-1$. The reason is that
such $(-1,1,-1,1),(1,-1,1,-1)$ patterns correspond to an illegal configuration
of shortest paths in planar graphs.

Consider arranging all the patterns as the rows of a binary matrix $P$. The
VC-dimension $d$ of $P$, is the maximum number of columns in a submatrix of
$P$ that contains all possible $2^{d}$ rows. The above forbidden configuration
implies that there is no submatrix with $4$ columns or more that contains all
possible rows, hence the VC-dimension of $P$ is at most $3$. By the well known
Sauer’s Lemma [27], this means that there are $O((k-1)^{3})=O(k^{3})$ distinct
rows. This is the entire proof.

#### Limitations of the original proof.

It remains an open problem whether the number of distinct patterns in planar
graphs is $\Theta(k^{3})$ or less (there is a simple $\Omega(k^{2})$ lower
bound). We do know however that there is no hope of improving $\Theta(k^{3})$
using the VC-dimension argument: Consider the following set of sequences over
$\\{-1,1\\}^{k-1}$:

$\left\\{(-1)^{x_{1}}\circ 1^{x_{2}}\circ(-1)^{x_{3}}\circ
1^{k-1-x_{1}-x_{2}-x_{3}}\;|\;x_{1}+x_{2}+x_{3}<k\right\\}$

There is no pair of sequences in this set that contains the forbidden
$(1,-1,1,-1),(-1,1,-1,1)$ configuration, and yet its cardinality is
$\Theta(k^{3})$. This means that any improvement to the $O(k^{3})$ bound on
the number of distinct patterns in planar graphs would have to further exploit
structural properties of planar graphs. In fact, even in the restricted family
of Halin graphs, where we know that there are only $\Theta(k^{2})$ distinct
patterns (see Section 4), the VC-dimension argument is limited to proving
$O(k^{3})$.

#### Our results and technique.

We develop a new technique for analyzing and encoding the structure of
patterns in a planar graph using bisectors. The bisector $\beta_{i}$
associated with vertex $s_{i}$ is a simple cycle in the dual graph such that
all (primal) vertices on the same side of $\beta_{i}$ have the same $i$’th bit
in their patterns. We show that any two bisectors are arc-disjoint. This
implies the following lemma:

######  Lemma 2.

The patterns of every two adjacent vertices in $G$ differ by at most two bits.

We then show how to use this property to obtain the following compression
(recall that $x$ denotes the number of distinct patterns in $G$):

######  Theorem 3.

There is an $\tilde{O}(x+k+|T|)$ space compression of the Okamura-Seymour
metric with $\tilde{O}(n)$ construction time and $\tilde{O}(1)$ query time.
Moreover, for the special case where the vertices of $T$ induce a connected
component in $G$, the space is $\tilde{O}(k+|T|)$.

By plugging $x=O(k^{3})$ from Theorem 1 (and the trivial compression that
stores all $T\times S$ distances) we get an
$\tilde{O}(\min\\{k^{3}+|T|,k\cdot|T|\\})$ compression (i.e. a factor $k$
improvement over Li and Parter [25]). Moreover, for the special case where the
vertices of $T$ induce a connected component in $G$, we obtain an optimal
$\tilde{O}(|T|+k)$ space encoding. Recall that, prior to our work, this bound
was only known (using the Unit-Monge property) when the vertices of $T$ all
lie (not necessarily consecutively) on a single face [1]. In fact, even in
such setting, our method gives $\tilde{O}(|T|+k)$. Thus, our method strictly
dominates the one based on Unit-Monge.

An additional benefit of working with bisectors is that they can be used to
bound the number $x$ of distinct patterns. We show that every two bisectors
can cross only $O(k)$ times. Our proof relies not only on the planar
structure, but also on the fact that the distance between any two vertices of
$S$ is bounded by $k$ (this property is not used in the VC-dimension
argument). The set of all bisectors partitions the plane into regions. All
(primal) vertices in the same region have the same pattern because they all
lie on the same side of every bisector. Since there are $O(k^{2})$ pairs of
bisectors, and each pair crosses $O(k)$ times, there are only $O(k^{3})$
regions (and hence only $O(k^{3})$ distinct patterns). This provides an
alternative proof of Theorem 1. We believe that our new technique may prove
useful in settling the question of the number of distinct patterns in a planar
graph. In particular, it may be that a similar argument that uses stronger
structural properties will be able to show that the partition induces only
$O(k^{2})$ regions. We demonstrate this potential of our technique in Section
4, where we show such a bound for a family of graphs that includes Halin
graphs:

######  Theorem 4.

The number of distinct patterns over all vertices of a Halin graph is
$O(k^{2})$. This bound is tight.

In contrast, the VC-dimension argument is limited to proving $O(k^{3})$, even
on Halin graphs.

##  2 Preliminaries

Let $G=(V,E)$ be an unweighted, undirected planar embedded graph. We prefer to
think of $G$ as a directed planar graph with a set of arcs $\mathcal{A}$, such
that there is a pair of arcs $uv,vu$ (embedded on the same curve) for every
edge $\\{u,v\\}\in E$. We refer to $u$ and $v$ as the _tail_ and _head_ of
$uv$, respectively. We refer to $uv$ as the _reverse_ of $vu$, or simply
$rev(vu)$. However, we use the term edge whenever the orientation is not
important or when we refer to any of the arcs (possibly both). We denote by
$P_{u,v}$ an arbitrary directed shortest path from $u$ to $v$. For $i<j$ we
denote by $S[i,j]$ a path (along the infinite face) $s_{i}-s_{i+1}-\cdots-
s_{j}$. We extend the definition of $rev(\cdot)$ to paths. We denote by
$P[w,y]$ the subpath of $P$ between vertices $w$ and $y$. We similarly use
$P(w,y]$, $P[w,y)$, and $P(w,y)$ to denote whether the subpath includes the
corresponding endpoint(s) or not. We use $\circ$ to denote a concatenation of
two paths. Let $C$ be a directed non-crossing cycle in $G$. We denote by ${\sf
left}(C)$ and ${\sf right}(C)$ the subgraphs of $G$ that consist of all edges,
vertices and faces that are lying to the left and right of $C$, respectively.
The arcs of $C$ and their reverses are in both ${\sf left}(C)$ and ${\sf
right}(C)$.

Figure 2: An example of two directed paths $P$ and $Q$ that cross at the
crossing part $R$.

Let $P$ and $Q$ be directed paths or cycles. We say that they cross at subpath
$R$ if, when ignoring their orientation: (1) $R$ is a proper (not a prefix or
suffix) subpath of both $P$ and $Q$, and (2) The edges of $Q$ that follow and
precede $R$ are in different sides of $P$. See Figure 2. We refer to $R$ as a
_crossing part_ of $P$ and $Q$.

The dual graph of $G$ is denoted by $G^{*}=(V^{*},E^{*})$. Again, we think of
$G^{*}$ as a directed graph with a set of arcs $\mathcal{A}^{*}$, defined as
follows. For every arc $uv\in\mathcal{A}$, there is a corresponding arc
$(uv)^{*}\in\mathcal{A}^{*}$ such that the tail and head of $(uv)^{*}$ are the
faces that lie to the right and the left of $uv$, respectively. We note that
we slightly abuse the notation here, since the dual of $(uv)^{*}$ is $rev(uv)$
(and not $uv$). For $B\subseteq\mathcal{A}$, let $B^{*}=\\{(uv)^{*}\;|\;uv\in
B\\}$. For a cut $X\subseteq V$, let $\delta(X)=\\{uv\in\mathcal{A}\;|\;u\in
X,v\in V\setminus X\\}$. For a cycle $C^{*}$ in the dual graph we say that
$v\in V$ is in ${\sf left}(C^{*})$ (resp. ${\sf right}(C^{*})$) if the face of
$G^{*}$ that corresponds to $v$ is in ${\sf left}(C^{*})$ (resp. ${\sf
right}(C^{*})$).

##  3 A Bisector-Based Approach to the Okamura-Seymour Compression

In this section we present our new proof of Theorem 1 and the proofs of Lemma
2 and Theorem 3. Our main tool is the use of simple dual cycles that we call
bisectors. In Section 3.1 we define bisectors, and prove that they are arc-
disjoint and that this implies Lemma 2. In Section 3.2 we use it to prove
Theorem 3. Then, in Section 3.3 we show that the union of all bisectors
partitions the graph into regions such that all vertices belonging to the same
region have the same pattern. Finally, in Section 3.4 we show that every two
bisectors can cross at most $O(k)$ times, implying that the partition induces
only $O(k^{3})$ regions (and hence only $O(k^{3})$ distinct patterns) thus
proving Theorem 1.

###  3.1 Bisectors

For $1\leq i\leq k-1$, define the cut $A_{i}=\\{v\in V\;|\;p_{v}[i]=-1\\}$.
Since we assume the patterns are over $\\{-1,1\\}$, $V\setminus A_{i}=\\{v\in
V\;|\;p_{v}[i]=1\\}$. We define the bisector $\beta_{i}=\delta(A_{i})^{*}$.
Namely, $\beta_{i}$ consists of all arcs $(uv)^{*}\in\mathcal{A}^{*}$ such
that $p_{u}[i]=-1$ and $p_{v}[i]=1$. Moreover, every edge $\\{u,v\\}\in E$
such that $p_{u}\neq p_{v}$ belongs to some bisector (possibly more than one).
By cut-cycle duality, if the induced subgraphs of $A_{i}$ and $V\setminus
A_{i}$ are both connected, then $\beta_{i}$ is a directed simple cycle in the
dual graph. The next lemma implies that both induced subgraphs of $A_{i}$ and
$V\setminus A_{i}$ are connected.

Figure 3: The bisector $\beta_{i}$ and its corresponding cut $A_{i}$.

######  Lemma 5.

For any $u\in A_{i}$ (resp. $V\setminus A_{i})$, the vertices of
$P_{u,s_{i+1}}$ (resp. $P_{u,s_{i}}$) are in $A_{i}$ (resp. $V\setminus
A_{i}$).

###### Proof.

Assume that $u\in A_{i}$ (the proof of the other case is symmetric). Let $v$
be any vertex of $P_{u,s_{i+1}}$ and assume for the sake of contradiction that
$v\in V\setminus A_{i}$. Thus, $d(v,s_{i+1})=d(v,s_{i})+1$. By the triangle
inequality, we get the following contradiction:

$d(u,s_{i})=d(u,s_{i+1})+1=d(u,v)+d(v,s_{i+1})+1=d(u,v)+d(v,s_{i})+2\geq
d(u,s_{i})+2\ \ \ \ \ \qed$

By the above lemma, any two vertices $u,v\in A_{i}$ (resp. $V\setminus A_{i}$)
are connected in the induced subgraph of $A_{i}$ (resp. $V\setminus A_{i}$) by
the path $P_{u,s_{i+1}}\circ rev(P_{v,s_{i+1}})$ (resp. $P_{u,s_{i}}\circ
rev(P_{v,s_{i}})$). This yields the following corollary.

######  Corollary 6.

$\beta_{i}$ is a directed simple cycle in the dual graph.

We note that the above corollary implies that for any face $f$, every bisector
contains at most two arcs incident to $f$. This shows that there are only
$O(k)$ total bit changes between patterns as we go along the vertices of a
face $f$.

Another useful corollary comes from the fact that any edge whose dual is in
$\beta_{i}$ contains endpoints that are both in $A_{i}$ and $V\setminus
A_{i}$. Therefore:

######  Corollary 7.

For any $u\in A_{i}$ (resp. $u\in V\setminus A_{i}$), the dual edges of
$P_{u,s_{i+1}}$ (resp. $P_{u,s_{i}}$) are not in $\beta_{i}$.

Note that $\beta_{i}$ has two arcs incident to $f_{\infty}$, one of them being
$(s_{i+1}s_{i})^{*}$. We think of $(s_{i+1}s_{i})^{*}$ as the first arc of
$\beta_{i}$. See Figure 3. The following lemma shows that bisectors are arc-
disjoint.

######  Lemma 8.

Every pair of bisectors $\beta_{i},\beta_{j}$ are arc-disjoint.

###### Proof.

Assume for contradiction that arc $(uv)^{*}$ appears both in $\beta_{i}$ and
in $\beta_{j}$. By definition, $u$ belongs to $A_{i}$ and $A_{j}$, and $v$
belongs to $V\setminus A_{i}$ and $V\setminus A_{j}$. We first prove that
under our assumption, either $P_{u,s_{i+1}}$ intersects with $P_{v,s_{j}}$ or
$P_{u,s_{j+1}}$ intersects with $P_{v,s_{i}}$. To see why, first note that
since $P_{v,s_{i}}$ and $P_{v,s_{j}}$ are shortest paths, we can choose them
to follow a common maximal-length prefix $P_{v,s_{i}}[v,w]=P_{v,s_{j}}[v,w]$
for some $w$, and they do not intersect again after $w$. Consider the directed
cycle $C=rev(P_{v,s_{j}})\circ P_{v,s_{i}}\circ S[i,j]$ (see Figure 4). Notice
that by our choice of $P_{v,s_{i}}$ and $P_{v,s_{j}}$ and by the fact that
$S[i,j]$ lies on the infinite face, $C$ is not necessarily simple but it does
not self-cross. We have two cases to consider:

Case 1: $u\in{\sf left}(C)\setminus C$. Since $s_{i+1}\in{\sf right}(C)$ then
(by the Jordan curve theorem and the fact that all vertices of $S$ lie on the
infinite face) $P_{u,s_{i+1}}$ must intersect with $rev(P_{v,s_{j}})\circ
P_{v,s_{i}}$. However, by Lemma 5, $P_{u,s_{i+1}}$ cannot intersect with
$P_{v,s_{i}}$, therefore it intersects with $rev(P_{v,s_{j}})$ (and hence with
$P_{v,s_{j}}$).

Case 2: $u\in{\sf right}(C)$. Notice that $s_{j+1}\in{\sf left}(C)$. If
$s_{j+1}$ is in $P_{v,s_{i}}$ then $P_{u,s_{j+1}}$ intersects with
$P_{v,s_{i}}$ and we are done. Otherwise, since $s_{j+1}$ is not in
$P_{v,s_{j}}$ by Lemma 5, then $s_{j+1}\in{\sf left}(C)\setminus C$. But then
again (by the Jordan curve theorem) $rev(P_{u,s_{j+1}})$ (and hence
$P_{u,s_{j+1}}$) must intersect with $rev(P_{v,s_{j}})\circ P_{v,s_{i}}$.
However, by Lemma 5, $P_{u,s_{j+1}}$ cannot intersect with $rev(P_{v,s_{j}})$,
therefore it intersects with $P_{v,s_{i}}$.

(a)  (b)

Figure 4: The two cases in the proof of Lemma 8. Case 1 on the left. Case 2 on
the right. ${\sf right}(C)$ is shaded. For clarity, $C$ is a simple cycle in
this example.

We can therefore continue under the assumption that $P_{u,s_{i+1}}$ and
$P_{v,s_{j}}$ intersect at a vertex $x$ (the other case is symmetric). By the
triangle inequality:

$\begin{split}&d(u,s_{j+1})\leq d(u,x)+d(x,s_{j})-1\\\
&d(u,x)+d(x,s_{i+1})\leq d(u,v)+d(v,s_{i})-1\\\ &d(v,s_{i})\leq
d(v,x)+d(x,s_{i+1})-1\\\ &d(v,x)+d(x,s_{j})\leq
d(v,u)+d(u,s_{j+1})-1\end{split}$

Since $d(u,v)=d(v,u)=1$, summing the above inequalities we get the
contradiction $0\leq-2$. ∎

The above lemma shows that two bisectors cannot share an arc. Note however
that it is still possible that a bisector contains reversed arcs of another
bisector. This proves Lemma 2. Next, we prove Theorem 3.

###  3.2 A proof of Theorem 3

We begin by describing how to compute all the bisectors of the graph and
report their arcs in $\tilde{O}(n)$ time. We split every edge
$\\{s_{i},s_{i+1}\\}$ by adding a dummy vertex $y_{i}$ and edges
$\\{s_{i},y_{i}\\},\\{y_{i},s_{i+1}\\}$ of weight $\frac{1}{2}$. Consider a
shortest path tree $T_{i}$ rooted at $y_{i}$. Notice that the arcs of
$\beta_{i}$ which are not incident to $f_{\infty}$, are the duals of arcs
whose tail is in the subtree rooted at $s_{i+1}$ and head is in the subtree
rooted at $s_{i}$. In the interdigitating tree of $T_{i}$ (i.e., the tree in
the dual graph whose edges are the duals of the edges not in $T_{i}$), they
are precisely the $f_{i}$-to-$f_{\infty}$ path without the last arc, where
$f_{i}\neq f_{\infty}$ is the face incident to $\\{s_{i},s_{i+1}\\}$ in $G$.
We can therefore run the MSSP algorithm of Klein [22] in $\tilde{O}(n)$ time,
and report for every $1\leq i\leq k-1$ all the those arcs of $\beta_{i}$ in
$\tilde{O}(|\beta_{i}|)$ time. To report the two arcs of $\beta_{i}$ which are
incident to $f_{\infty}$, one of them is trivially $(s_{i+1}s_{i})^{*}$ and
the other one is determined by last arc of the above $f_{i}$-to-$f_{\infty}$
path. Since by Lemma 8 the arcs of bisectors are disjoint, this takes time
$\tilde{O}(n+\sum_{i=1}^{k-1}|\beta_{i}|)=\tilde{O}(n)$ time. In particular,
we can label every edge $\\{u,v\\}\in E$ by the (at most two) bisectors that
use $(uv)^{*}$ and $(vu)^{*}$. I.e., the bits that change between $p_{u}$ and
$p_{v}$.

We next describe the compression scheme. Recall that, by storing $d(v,s_{1})$
for every $v\in T$, a query $d(v,s_{i})$ (with $v\in T$ and $s_{i}\in S$)
boils down to extracting $p_{v}$ and computing its $(i-1)$’th prefix-sum. Let
$\mathcal{T}$ be a spanning tree of $G$. Label each edge $\\{u,v\\}$ of
$\mathcal{T}$ by the (at most two) bits that change between the patterns of
$u$ and $v$. Note that there could be many (potentially $\Omega(n)$) nodes of
$\mathcal{T}$ that correspond to the same pattern. In order to decrease the
size of $\mathcal{T}$ to be $x$ (the number of distinct patterns in $G$), we
root $\mathcal{T}$ at some arbitrary node $u$. Then, for every two nodes $v,w$
of $\mathcal{T}$ s.t $p_{v}=p_{w}$ (and w.l.o.g. $v$ is not a descendent of
$w$) we remove the node $w$ and turn all it’s children to be children of $v$
(their edge labels remain the same). We repeat this process until the size of
the tree is $x$. We denote the resulting tree by $\mathcal{T}^{\prime}$. Let
$Q$ be an Euler-tour of $\mathcal{T}^{\prime}$ starting from the root $u$.
Consider the patterns of the nodes as we go along $Q$, starting from $p_{u}$.
In each step, the pattern only changes in at most two bits (according to the
edge labels). Therefore, we can maintain all these $O(|Q|)=O(x)$ versions of
the pattern using a _persistent_ [11] data structure for prefix-sum (e.g.,
using persistent segment trees [3]). Such a data structure supports both
updates and prefix-sum queries to any version in $\tilde{O}(1)$ time and uses
$\tilde{O}(|Q|+k)=\tilde{O}(x+k)$ space. Finally, for every vertex $v\in T$
let $q_{v}$ be a node in $Q$ whose corresponding pattern is $p_{v}$. We store
a pointer from $v$ to the version of the persistent data structure at $q_{v}$,
using additional $\tilde{O}(|T|)$ bits overall.

We now give a randomized $\tilde{O}(n)$ time algorithm for constructing
$\mathcal{T^{\prime}}$ (and hence the compression). An arbitrary spanning tree
$\mathcal{T}$ can be computed in $O(n)$ time. Assume that every edge
$\\{w,v\\}$ of $\mathcal{T}$ is labeled by the (at most two) bits that change
between $p_{w}$ and $p_{v}$. Let us compute the pattern of the root $u$ of
$\mathcal{T}$ with a single-source shortest-paths computation in $G$. We also
compute the _Karp-Rabin fingerprint_ [20] $\phi(p_{u})$ of $p_{u}$. Such
fingerprints are appealing because: (1) for any $p_{w}\neq p_{v}$, we have
that $\phi(p_{w})\neq\phi(p_{v})$ with high probability, and (2) given
$\phi(S_{1})$ and $\phi(S_{2})$ of two strings $S_{1},S_{2}$ we can compute in
$O(1)$ time the fingerprint of the concatenation $\phi(S_{1}\circ S_{2})$.
Thus, if we maintain a complete binary tree on top of the pattern where each
node contains the fingerprint of its subtree (and in particular, the root
contains the fingerprint of the entire pattern), then we can update this tree
in $O(\log k)$ time after changing one or two bits in the pattern.

We maintain the fingerprints in a dictionary initially containing only
$\phi(p_{u})$. We process the nodes of $\mathcal{T}$ starting from $u$,
maintaining a queue of next-to-visit nodes. When we process a node $v$, we
compute $\phi(p_{v})$ from the fingerprint of $v$’s parent, by flipping the
bits according to the edge label (in $O(\log k)$ time). We then try to add
$\phi(p_{v})$ to the dictionary. If we find a collision with some vertex $w$
(namely, $\phi(p_{v})=\phi(p_{w})$) then we delete $v$ from $\mathcal{T}$, and
set the children of $v$ to be children of $w$ in $\mathcal{T}$. In any case,
we add the children of $v$ to the queue so they will be processed later.
Notice that a node is visited only after all its ancestors have been visited.
Therefore, we can always compute its fingerprint and we never move children
from a vertex to its descendent, so $\mathcal{T}$ remains a tree. In addition,
the parent of every node changes or gets deleted at most once, hence the
running time is $\tilde{O}(n)$. Overall, in $\tilde{O}(n)$ time we construct
$\mathcal{T^{\prime}}$ and the dictionary (both of size $x$).

  * •

In the special case where the vertices of $T$ induce a connected component in
$G$, we can skip the first part of the algorithm and simply take a path $Q$
that traverses only the vertices of $T$. The rest of the construction remains
the same and since $|Q|=O(|T|)$, the size of the compression is
$\tilde{O}(|T|+k)$.

  * •

In the special case where the vertices of $T$ all lie on a single face (but
not necessarily consecutively), let $Q$ be a path that visits all the vertices
of the face in clockwise order. By Corollary 6, the total number of bit
changes between patterns of consecutive vertices along $Q$ is $O(k)$.
Therefore, the number of patterns encountered is $O(k)$ and hence we get an
$\tilde{O}(|T|+k)$ compression for this case as well.

This completes the proof of Theorem 3.

###  3.3 The bisector graph and the pattern graph

The _bisector graph_ $G_{\mathcal{B}}$ is the subgraph of $G^{*}$ composed of
the union of all the bisectors. The faces of $G_{\mathcal{B}}$ represent the
patterns of $G$ in the following way.

######  Lemma 9.

For every $u,v\in V$, if $u$ and $v$ are embedded inside the same face $f$ of
$G_{\mathcal{B}}$, then $p_{u}=p_{v}$.

###### Proof.

Notice that $G_{\mathcal{B}}$ is a connected graph because all the bisectors
are incident to $f_{\infty}$. Hence, $f$ is a simple cycle in $G^{*}$. Let
$G_{f}$ be the subgraph of $G$ embedded inside the face $f$. Since there are
no bisector edges embedded inside $f$, then in $G_{f}$ there is no pair of
adjacent vertices that have different patterns. Since $f$ is a simple cycle,
then by cut-cycle duality $G_{f}$ is a connected subgraph. Therefore, there
exists a $u$-to-$v$ path in $G_{f}$, and every pair of adjacent vertices in
this path have the same pattern. Hence $p_{u}=p_{v}$. ∎

By the above lemma, every pattern $p$ of $G$ corresponds to a unique nonempty
subset of faces of $G_{\mathcal{B}}$. More precisely, a pattern $p$
corresponds to all the faces of $G_{\mathcal{B}}$ such that the vertices of
$G$ embedded in these faces have pattern $p$. In particular, the number of
faces of $G_{\mathcal{B}}$ is an upper bound on the number of distinct
patterns in $G$. Therefore, if we could prove that $G_{\mathcal{B}}$ has
$O(k^{3})$ faces we would be done. Unfortunately, this is not the case. There
can be as many as $\Omega(n)$ faces of $G_{\mathcal{B}}$ that correspond to
the same pattern (see Figure 5). To tackle this, we transform
$G_{\mathcal{B}}$ into a new graph $G_{\mathcal{P}}$ (called the _pattern
graph_) that has only $O(k^{3})$ faces and whose faces still represent all the
distinct patterns of $G$.

Figure 5: The shaded faces all correspond to the same pattern (assuming no
other bisector crosses or separates them). They are formed when the two
bisectors either cross each other or just touch (intersect without crossing).
We will later see that two bisectors can cross each other at most $O(k)$
times, but, they can touch $\Omega(n)$ times, creating $\Omega(n)$ faces that
correspond to the same pattern.

The pattern graph $G_{\mathcal{P}}$ is obtained by applying on
$G_{\mathcal{B}}$ the following two-phase procedure:
(1) A _Peel_ phase: Recall that while Lemma 8 says that every two bisectors
are arc-disjoint, it is still possible that one bisector contains reversed
arcs of another. In the peel phase, we re-embed the bisectors so that no
bisector contains reversed arcs of another bisector. After the peel phase,
crossings and touchings occur only at vertices (rather than subpaths).
(2) A _Merge_ phase: In the merge phase, we merge faces that correspond to the
same pattern and share a common vertex.

#### Peel Phase.

For every two bisectors $\beta$ and $\beta^{\prime}$, consider the set of
maximal-length subpaths $R$, such that $R$ is a subpath of $\beta$ and
$rev(R)$ is a subpath of $\beta^{\prime}$. If the arc of $\beta$ that follows
$R$ is in ${\sf right}(\beta^{\prime})$ (resp. ${\sf left}(\beta^{\prime})$),
then we re-embed every arc of $R$ on a new curve lying to the right (resp.
left) of its reverse. See Figure 6. Note that the peel phase does not create
any new crossings between $\beta$ and $\beta^{\prime}$.

Figure 6: Before (left) and after (right) a peel phase. In this example, $R$
is a single arc, and the arc of $\beta$ that follows $R$ is in ${\sf
left}(\beta^{\prime})$.

#### Merge Phase.

For every vertex $g\neq f_{\infty}$ of a bisector $\beta$, if any other
bisector crosses $\beta$ at $g$ then we do nothing. Otherwise, we split $g$
into two copies. All the arcs in ${\sf left}(\beta)$ that are incident to $g$
are connected to one copy, and all the arcs in ${\sf right}(\beta)$ that are
incident to $g$ are connected to the other copy. Finally, we replace the arcs
of $\beta$ that are incident to $g$ (say $fg$ and $gh$) by a single arc $fh$.
See Figure 7. Note that if $g$ is not incident to any bisector other than
$\beta$, then the merge phase simply contracts the arc $gh$. We repeat this
process until there are no such bisector pairs in the graph.

Figure 7: Before (left) and after (right) a merge phase. The (shaded) face
$g^{\prime}$ is obtained by merging faces $h^{\prime}$ and $f^{\prime}$.

We now show that the above two-phase procedure maintains the relation between
patterns in $G$ and faces in $G_{\mathcal{P}}$. Namely, that every pattern in
$G$ corresponds to a unique nonempty subset of faces of $G_{\mathcal{P}}$. To
this end, we extend the definition of patterns to faces of $G_{\mathcal{B}}$.
This step is necessary since the peel phase creates faces that do not
correspond to primal vertices.

We define the _pattern_ of a face $f$ of $G_{\mathcal{B}}$, denoted $p_{f}$,
to be the length $k-1$ vector where $p_{f}[i]=-1$ (resp. $p_{f}[i]=1$) if $f$
is a face in ${\sf left}(\beta_{i+1})$ (resp. ${\sf right}(\beta_{i+1})$) in
$G_{\mathcal{B}}$. The definition remains the same for any graph we obtain
from $G_{\mathcal{B}}$ during the two-phase procedure. The following two
propositions show that this definition is consistent with the original
definition of patterns (of vertices).

######  Proposition 10.

Let $v\in V$ be a vertex embedded inside a face $f$ of $G_{\mathcal{B}}$. Then
$p_{v}=p_{f}$.

###### Proof.

Let $0\leq i\leq k-2$. If $p_{f}[i]=1$ then $f$ is in ${\sf
right}(\beta_{i+1})$ by definition. Since $G_{\mathcal{B}}$ is a subgraph of
$G^{*}$, then in $G^{*}$ $v$ is also embedded in ${\sf right}(\beta_{i+1})$.
Hence, $v\in V\setminus A_{i}$ and therefore $p_{v}[i]=1$. A symmetric
argument shows that if $p_{f}[i]=-1$ then $p_{v}[i]=-1$. ∎

By Proposition 10, all the faces of $G_{\mathcal{B}}$ that correspond to a
pattern $p_{v}$ have the same face pattern. Notice that the peel phase does
not change the patterns of existing faces. It can only add new faces to the
graph, but no vertex of $G$ is embedded in any of these new faces. Hence, the
relation is preserved after the peel phase. Next we show that after a merge
step, every pattern still corresponds to a unique subset of faces (i.e., we
show that we do not merge faces that corresponded to different patterns).
Consider a single merge step happening at $g$ (as illustrated in Figure 7).
Denote by $f^{\prime}$ (resp. $h^{\prime}$) the face lying to the left of $fg$
(resp. $gh$). Namely, $f^{\prime}$ and $h^{\prime}$ are the faces that get
merged (a symmetric argument holds when they lie to the right of $fg$ and
$gh$). Let $g^{\prime}$ denote the face obtained by merging $f^{\prime}$ and
$h^{\prime}$.

######  Proposition 11.

$p_{f^{\prime}}=p_{h^{\prime}}=p_{g^{\prime}}$.

###### Proof.

Since no bisector crosses $\beta$ at $g$, then $fg$ and $gh$ belong to the
same side of every bisector. This, together with the fact that $fg$, $gh$, and
their reverses do not belong to any other bisector, implies that $f^{\prime}$
and $h^{\prime}$ also belong to the same side of every bisector. Hence
$p_{f^{\prime}}=p_{h^{\prime}}$. Now consider the arc $fh$ after the merge.
Since $f$ and $h$ belong to the same side of every bisector as $fg$ (and
$gh$), then $g^{\prime}$ also belongs to the same side of every bisector,
hence $p_{f^{\prime}}=p_{h^{\prime}}=p_{g^{\prime}}$. ∎

By proposition 10, if $f^{\prime}$ or $h^{\prime}$ are faces that correspond
to $p_{v}$ then they do not correspond to any $p_{u}\neq p_{v}$. By
Proposition 11, we can set $g^{\prime}$ to correspond to $p_{v}$, and the set
of faces corresponding to every pattern remains unique. This yields the
following corollary.

######  Corollary 12.

Every pattern of $G$ corresponds to a unique subset of faces of
$G_{\mathcal{P}}$.

Finally, we show that the number of faces in $G_{\mathcal{P}}$ depends
linearly on the number of bisector crossings. Let $t$ be the total number of
bisector crossings in $G_{\mathcal{P}}$. That is, $t$ is the sum of the number
of crossings between all pairs of bisectors.

######  Lemma 13.

The number of faces in $G_{\mathcal{P}}$ is $O(t+k)$.

###### Proof.

By Euler’s formula, it suffices to show that the number of arcs in
$G_{\mathcal{P}}$ is $O(t+k)$. For every arc $fg$ in $G_{\mathcal{P}}$, where
neither $f$ nor $g$ is $f_{\infty}$, the arc $fg$ belongs to some bisector
$\beta$. Moreover, there must exist some other bisector that crosses $\beta$
at $f$. Otherwise, the arc would have been removed in the merge phase.
Consider all the bisectors that cross $\beta$ at $f$ in a clockwise order
around $f$ starting at $fg$. Let $\beta^{\prime}$ be the one following $fg$.
Then we charge $fg$ to the crossing of $\beta$ and $\beta^{\prime}$ at $f$.
Notice that at most two arcs will be charged to this crossing of $\beta$ and
$\beta^{\prime}$ (the arc $fg$ and the arc of $\beta^{\prime}$ whose tail is
$f$). Overall, we have charged $O(t)$ arcs. The only arcs that did not get
charged are the $2(k-1)$ arcs incident to $f_{\infty}$. Therefore, the number
of arcs in $G_{\mathcal{P}}$ is $O(t+k)$. ∎

In the next subsection, we prove that every pair of bisectors can cross at
most $O(k)$ times. Since there are $O(k^{2})$ pairs of bisectors, the total
number of crossings is then $t=O(k^{3})$, which by Corollary 12 and Lemma 13
implies Theorem 1.

###  3.4 Two bisectors can cross only $O(k)$ times

Let $\beta_{i}$ and $\beta_{j}$ be two bisectors in $G^{*}$ that cross each
other at least once. Let $R_{1},R_{2},\ldots R_{r}$ be their crossing parts
that do not contain $f_{\infty}$, sorted by their order of appearance along
$\beta_{i}$. We note that since $\beta_{i}$ and $\beta_{j}$ are simple cycles,
the crossing parts must be disjoint. In Lemma 16 we show that the crossing
parts appear in reverse order along $\beta_{j}$, and in Lemma 17 we use this
fact to prove that the number of crossings $r$ is at most $O(k)$. We begin by
defining an important configuration of bisectors and shortest paths.

Figure 8: A configuration of bisectors $\beta_{i},\beta_{j}$ and shortest
paths $P_{u,s_{i+1}},P_{v,s_{j}}$ that must intersect. ${\sf right}(C^{*})$ is
shaded.

######  Lemma 14.

Let $C^{*}=\beta_{j}[f_{\infty},f]\circ rev(\beta_{i}[f_{\infty},f])$ be a
simple cycle, and let $u\in A_{i},v\in V\setminus A_{j}$ (resp. $u\in
V\setminus A_{i},v\in A_{j}$) be two vertices in ${\sf left}(C^{*})$ (resp.
${\sf right}(C^{*})$). Then $P_{u,s_{i+1}}$ and $P_{v,s_{j}}$ (resp.
$P_{u,s_{i}}$ and $P_{v,s_{j+1}}$) must intersect at some vertex $x$.

###### Proof.

We focus on the case where $u\in A_{i}$ and $v\in V\setminus A_{j}$ are
vertices in ${\sf left}(C^{*})$ (the proof of the other case is symmetric).
See Figure 8. We assume that $G$ and $G^{*}$ are embedded on the same surface,
such that for every $wy\in\mathcal{A}$, the curves of $wy$ and $(wy)^{*}$
intersect in their middles at a single _point_ $p$ on the surface. See Figure
9.

Figure 9: An arc $wy\in\mathcal{A}$ that intersects with its dual
$(wy)^{*}\in\mathcal{A}^{*}$ at a middle point $p$.

We refer to the two parts of the curve of $uv$ as $(u-p)$ and $(p-v)$. For a
path $Q$ that contains arc $uv$, we slightly abuse notation and use
$Q[\cdot,p]$ and $Q[p,\cdot]$ to denote a prefix and suffix of the curve of
$Q$. In addition, we say that a path $P$ of the primal graph crosses a path
$Q$ of the dual graph, if $P$ contains an arc $uv$ whose dual or reversed dual
is in $Q$. In particular, it means that there exist a common point $p$ (in the
middle of $uv$), such that $(u-p)$ and $(p-v)$ are on different sides of $Q$.
Let $p_{j}$ be the point in the middle of $s_{j}s_{j+1}$, and let $p_{i}$ be
the point in the middle of $s_{i}s_{i+1}$.

Notice that $s_{i+1},s_{j}\in{\sf right}(C^{*})\setminus C^{*}$ by definition,
and that $v\in{\sf left}(C^{*})\setminus C^{*}$ by assumption (and the fact
that $v$ is not part of $C^{*}$ because $v$ is a primal vertex). Hence,
$P_{v,s_{j}}$ must cross $C^{*}$. However, by Corollary 7 it cannot cross
$\beta_{j}[f_{\infty},f]$, hence it must cross $\beta_{i}[f_{\infty},f]$. This
means that there is a point $q$ that is common to both $P_{v,s_{j}}$ and
$\beta_{i}[f_{\infty},f]$. In particular, let $q$ be the last point along the
curve of $P_{v,s_{j}}$ that is also along the curve of $C^{*}$. Notice that
$P_{v,s_{j}}[q,s_{j}]\circ(s_{j}-p_{j})$ is a chord inside the cycle $C^{*}$.
Similarly, there exists a point $q^{\prime}$ along the curve of
$P_{u,s_{i+1}}$ such that
$P_{u,s_{i+1}}[q^{\prime},s_{i+1}]\circ(s_{i+1}-p_{i})$ is a chord in $C^{*}$.
The endpoints of the chords appear in clockwise order along $C^{*}$ as
$(q,p_{i},p_{j},q^{\prime})$. It is well known that two chords in such a
configuration must intersect. Therefore, there exist a primal vertex $x$ that
is common to both $P_{v,s_{j}}[q,s_{j}]$ and
$P_{u,s_{i+1}}[q^{\prime},s_{i+1}]$. ∎

It is important to remark that Lemma 14 holds even when the cycle $C^{*}$ is a
non-self-crossing non-simple cycle. Namely, if $C^{*}$ intersects with itself,
we let $g$ be the first intersection vertex in $\beta_{i}[f_{\infty},f]$, and
define a cycle $\hat{C}^{*}=\beta_{j}[f_{\infty},g]\circ
rev(\beta_{i}[f_{\infty},g])$. Note that since $\beta_{i}$ and $\beta_{j}$ are
simple cycles, and by our choice of $g$, there are no intersections in
$\hat{C}^{*}$. Clearly, we also have that $v,u\in{\sf left}(\hat{C}^{*})$.
Thus, we apply the Lemma to $\hat{C}^{*}$ instead of $C^{*}$.

######  Corollary 15.

$P_{v,s_{j}}[v,x]$ (resp. $P_{u,s_{i+1}}[u,x]$) contains an edge whose dual is
in $\beta_{i}$ (resp. $\beta_{j}$).

We are now in the position to prove the two main lemmas of this section.

######  Lemma 16.

Let $\beta_{i}$ and $\beta_{j}$ be two crossing bisectors. Let
$R_{1},R_{2},\ldots R_{r}$ be their crossing parts along $\beta_{i}$. Then,
the crossing parts along $\beta_{j}$ are reversed $R_{r},R_{r-1},\ldots
R_{1}$.

###### Proof.

We assume that $i<j$. For $\ell\leq r$, we say that $\beta_{j}$ enters
$R_{\ell}$ from ${\sf left}(\beta_{i})$ (resp. ${\sf right}(\beta_{i})$) if
the arc of $\beta_{j}$ that precedes $R_{\ell}$ is in ${\sf left}(\beta_{i})$
(resp. ${\sf right}(\beta_{i})$). For brevity, we assume that every $R_{\ell}$
is a single vertex in $V^{*}$. Finally, we assume without loss of generality
that $s_{j}$ is in ${\sf left}(\beta_{i})$ (the proof of the other case is
symmetric).

Assume for the sake of contradiction that the order of appearance is not the
reverse order. Then there exists a pair of crossing parts $R_{a}$ and $R_{b}$
such that: (1) $a<b$, (2) $R_{b}$ is the crossing part following $R_{a}$ in
$\beta_{j}$, and (3) $a$ is minimal among such pairs. Consider the cycle
$C^{*}=\beta_{j}[f_{\infty},R_{a}]\circ rev(\beta_{i}[f_{\infty},R_{a}])$.
Note that $C^{*}$ is non-crossing since if there exists $R_{c}$ for $c<a$ that
$\beta_{j}[f_{\infty},R_{a}]$ crosses, then $a$ wouldn’t be minimal. We have
two cases to consider:

(a)  Figure 10: Case 1 in the proof of Lemma 16. The dotted parts represent
parts in which there may be crossings. ${\sf right}(C^{*})$ is shaded. In this
example, $P$ is crossed by $\beta_{j}[f_{\infty},R_{a}]$ exactly twice.

Case 1: $\beta_{j}$ enters $R_{a}$ from ${\sf left}(\beta_{i})$ (hence it
enters $R_{b}$ from ${\sf right}(\beta_{i})$). Let $(uv)^{*}$ be the arc of
$\beta_{j}$ that follows $R_{b}$. We next show that $v$ and $C^{*}$ form the
configuration of Lemma 14, in the special case of $v=u$.

First we show that $v\in V\setminus A_{j}$ and $v\in A_{i}$. Note that $v\in
V\setminus A_{j}$ by definition, since $v$ is the primal vertex lying to the
right of an arc of $\beta_{j}$. Since $(uv)^{*}$ follows the crossing part
$R_{b}$, and since $\beta_{j}$ enters $R_{b}$ from ${\sf right}(\beta_{i})$,
then $(uv)^{*}\in{\sf left}(\beta_{i})\setminus\beta_{i}$. Hence, $v\in{\sf
left}(\beta_{i})$ and therefore $v\in A_{i}$.

Next we show that $v\in{\sf left}(C^{*})$. For this, we show that
$R_{b}\in{\sf left}(C^{*})\setminus C^{*}$, hence the arcs incident to $R_{b}$
and their corresponding primal vertices are in ${\sf left}(C^{*})$. Consider
the path $P=\beta_{i}[R_{a},R_{b}]$. The first arc of $P$ is in ${\sf
left}(C^{*})$ by the case assumption. To show that $R_{b}\in{\sf
left}(C^{*})\setminus C^{*}$ we will show that $P$ crosses the cycle $C^{*}$
an even number of times. Notice that $P$ does not cross
$\beta_{i}[f_{\infty},R_{a}]$ since $\beta_{i}$ is a simple cycle. It
therefore remains to show that $P$ crosses $\beta_{j}[f_{\infty},R_{a}]$ an
even number of times (equivalently, we show that $\beta_{j}[f_{\infty},R_{a}]$
crosses $P$ an even number of times). To this end, let us define a cycle
$\hat{C}^{*}=P\circ rev(\beta_{j}[R_{b},R_{a}])$. Notice that $\hat{C}^{*}$ is
non-crossing since $R_{b}$ follows $R_{a}$ in $\beta_{j}$. Notice that the
first and last arcs of $\beta_{j}[f_{\infty},R_{a}]$ are both in ${\sf
left}(\beta_{i})$. Also notice that ${\sf right}(\hat{C}^{*})$ is included in
${\sf right}(\beta_{i})$ (by the case assumption), therefore the first and
last arcs of $\beta_{j}[f_{\infty},R_{a}]$ are in ${\sf left}(\hat{C}^{*})$.
Hence, $\beta_{j}[f_{\infty},R_{a}]$ crosses $\hat{C}^{*}$ an even number of
times. Since $\beta_{j}[f_{\infty},R_{a}]$ can only cross $\hat{C}^{*}$ at $P$
(as $\beta_{j}$ is a simple cycle), it must cross $P$ an even number of times.

We can thus apply Lemma 14, and conclude that $P_{v,s_{j}}$ and
$P_{v,s_{i+1}}$ intersect at vertex $x$, and that $P_{v,s_{i+1}}[v,x]$
contains an edge whose dual is in $\beta_{j}$ (by Corollary 15). Since the
lengths of $P_{v,s_{j}}[v,x]$ and $P_{v,s_{i+1}}[v,x]$ are the same,
$P_{v,s_{i+1}}[v,x]\circ P_{v,s_{j}}[x,s_{j}]$ is a shortest $v$-to-$s_{j}$
path. However, since $P_{v,s_{i+1}}[v,x]$ contains an edge of $\beta_{j}$, we
get a contradiction to Corollary 7.

(a)  Figure 11: Case 2 in the proof of Lemma 16. The dotted parts represent
parts in which there may be crossings. ${\sf left}(C^{*})$ is shaded. In this
example, $P$ is crossed by $\beta_{j}[f_{\infty},R_{a}]$ exactly twice.

Case 2: $\beta_{j}$ enters $R_{a}$ from ${\sf right}(\beta_{i})$ (hence it
enters $R_{b}$ from ${\sf left}(\beta_{i})$. Let $(uv)^{*}$ be the arc of
$\beta_{j}$ that follows $R_{b}$. We next show that $u$ and $C^{*}$ form the
configuration of Lemma 14 (again, in the special case of $u=v$). By symmetric
arguments to Case 1, we can show that $u\in A_{j}$ and $u\in V\setminus
A_{i}$. We therefore only need to show that $u\in{\sf right}(C^{*})$.

To show that $u\in{\sf right}(C^{*})$, it suffices to show that $R_{b}\in{\sf
right}(C^{*})\setminus C^{*}$ (hence the arcs incident to $R_{b}$ and their
corresponding primal vertices are in ${\sf right}(C^{*})$). Consider the path
$P=\beta_{i}[R_{a},R_{b}]$. The first arc of $P$ is in ${\sf right}(C^{*})$ by
the case assumption. To show that $R_{b}\in{\sf right}(C^{*})\setminus C^{*}$,
we will show that $P$ crosses the cycle $C^{*}$ an even number of times. Since
$P$ does not cross $\beta_{i}[f_{\infty},R_{a}]$, we need to show that
$\beta_{j}[f_{\infty},R_{a}]$ crosses $P$ an even number of times (here is
where the argument will differ from Case 1).

Let $\hat{C}^{*}=P\circ rev(\beta_{j}[R_{b},R_{a}])$ be a non-crossing cycle.
Let $R$ be the first crossing between $\beta_{j}[f_{\infty},R_{a}]$ and
$\beta_{i}$. $R$ exists and is not $R_{a}$ by the assumption that
$s_{j}\in{\sf left}(\beta_{i})$, and by the case assumption. Note that
$\beta_{j}[f_{\infty},R]$ does not cross $\beta_{i}$ (and hence does not cross
$P$) by definition of $R$, so it remains to show that the number of crossings
between $\beta_{j}[R,R_{a}]$ and $P$ is even. Notice that, since $s_{j}\in{\sf
left}(\beta_{i})$, the first and last arcs of $\beta_{j}[R,R_{a}]$ are both in
${\sf right}(\beta_{i})$. Also note that ${\sf left}(\hat{C}^{*})$ is
contained in ${\sf left}(\beta_{i})$. Therefore, the first and last arcs of
$\beta_{j}[R,R_{a}]$ are in ${\sf right}(\hat{C}^{*})$. Hence,
$\beta_{j}[R,R_{a}]$ crosses $\hat{C}^{*}$ an even number of times. Since it
can only cross $\hat{C}^{*}$ at $P$, then $\beta_{j}[R,R_{a}]$ crosses $P$ an
even number of times.

We can thus apply Lemma 14, and conclude that $P_{u,s_{j+1}}$ and
$P_{u,s_{i}}$ intersect at vertex $x$, and that $P_{u,s_{j+1}}[u,x]$ contains
an edge of $\beta_{i}$ (by Corollary 15). Since the lengths of
$P_{u,s_{i}}[u,x]$ and $P_{u,s_{j+1}}[u,x]$ are the same,
$P_{u,s_{j+1}}[u,x]\circ P_{u,s_{i}}[x,s_{i}]$ is a shortest $u$-to-$s_{i}$
path. However, since $P_{u,s_{j+1}}[u,x]$ contains an edge of $\beta_{i}$, we
get a contradiction to Corollary 7. ∎

######  Lemma 17.

Two bisectors can cross at most $\frac{k}{2}+O(1)$ times.

###### Proof.

We will prove that if two bisectors $\beta_{i},\beta_{j}$ cross $r$ times then
there exists a vertex $v\in V$ such that $d(v,s_{j})-d(v,s_{i+1})\geq
2r-\frac{k}{2}-O(1)$. Since the distance between any pair of vertices along
the infinite face is at most $\frac{k}{2}$, then by the triangle inequality we
have also $d(v,s_{j})-d(v,s_{i+1})\leq\frac{k}{2}$. Hence, we get
$2r-\frac{k}{2}-O(1)\leq\frac{k}{2}$ and the lemma follows.

(a)  Figure 12: Two bisectors that cross $r$ times and the vertices and
shortest paths they induce. Observe that $v_{\ell}$ is in ${\sf
right}(\beta_{i})$ when $r-\ell$ is even, and otherwise in ${\sf
left}(\beta_{i})$. ${\sf right}(C_{\ell}^{*})$ is shaded.

Again, let us assume without loss of generality that $s_{j}$ is in ${\sf
left}(\beta_{i})$ (the proof of the other case is symmetric). For every
$\ell<r$, consider the cycle $C_{\ell}^{*}=\beta_{j}[f_{\infty},R_{\ell}]\circ
rev(\beta_{i}[f_{\infty},R_{\ell}])$. By the previous lemma, $C_{\ell}^{*}$
does not self-cross. For even (resp. odd) $r-\ell$, let
$(u_{\ell}v_{\ell})^{*}$ (resp. $(v_{\ell}u_{\ell})^{*}$) be the arc of
$\beta_{j}$ that follows $R_{\ell}$. See Figure 12. We assume that $r-\ell$ is
even (the odd case is symmetric).

We claim that $C_{\ell}^{*},v_{\ell},v_{\ell+1}$ forms the configuration of
Lemma 14. By definition of $\beta_{j}$ we have that $v_{\ell}\in V\setminus
A_{j}$. Thus, it remains to prove that $v_{\ell+1}\in A_{i}$ and that
$v_{\ell},v_{\ell+1}\in{\sf left}(C_{\ell}^{*})$. By Lemma 16 and the
assumption that $s_{j}\in{\sf left}(\beta_{i})$, $\beta_{j}$ reaches
$R_{\ell+1}$ from ${\sf right}(\beta_{i})$. Therefore,
$(v_{\ell+1}u_{\ell+1})^{*}\in{\sf left}(\beta_{i})\setminus\beta_{i}$. Hence,
$v_{\ell+1}$ is in ${\sf left}(\beta_{i})$ and therefore $v_{\ell+1}\in
A_{i}$. To see that $v_{\ell},v_{\ell+1}\in{\sf left}(C_{\ell}^{*})$, note
that by Lemma 16, $(v_{\ell+1}u_{\ell+1})^{*}$ is in
$\beta_{j}[f_{\infty},R_{\ell}]$, hence $v_{\ell+1}\in{\sf
left}(C_{\ell}^{*})$ by definition (as $\beta_{j}[f_{\infty},R_{\ell}]$ is
part of $C_{\ell}^{*}$). Clearly, since $\beta_{j}$ enters $R_{\ell}$ from
${\sf right}(\beta_{i})$ we also have that $(u_{\ell}v_{\ell})^{*}\in{\sf
left}(C_{\ell}^{*})$ and in particular $v_{\ell}\in{\sf left}(C_{\ell}^{*})$.

We can thus apply Lemma 14 and conclude that $P_{v_{\ell},s_{j}}$ and
$P_{v_{\ell+1},s_{i+1}}$ must intersect at some vertex $x_{\ell}$. In
addition, we can conclude that $P_{v_{\ell-1},s_{j+1}}$ and
$P_{v_{\ell},s_{i}}$ intersect at some vertex $x_{\ell-1}$, and that
$P_{v_{\ell-2},s_{j}}$ and $P_{v_{\ell-1},s_{i+1}}$ intersect at some vertex
$x_{\ell-2}$. Therefore, by the triangle inequality and the assumption that
patterns are binary, we have:

$\begin{split}&d(v_{\ell},x_{\ell})+d(x_{\ell},s_{j})\leq
d(v_{\ell},x_{\ell-1})+d(x_{\ell-1},s_{j+1})-1\\\
&d(v_{\ell},x_{\ell-1})+d(x_{\ell-1},s_{i})\leq
d(v_{\ell},x_{\ell})+d(x_{\ell},s_{i+1})-1\\\
&d(v_{\ell-1},x_{\ell-2})+d(x_{\ell-2},s_{i+1})\leq
d(v_{\ell-1},x_{\ell-1})+d(x_{\ell-1},s_{i})-1\\\
&d(v_{\ell-1},x_{\ell-1})+d(x_{\ell-1},s_{j+1})\leq
d(v_{\ell-1},x_{\ell-2})+d(x_{\ell-2},s_{j})-1\end{split}$

Summing the above inequalities we get:

$d(x_{\ell},s_{j})-d(x_{\ell},s_{i+1})+4\leq
d(x_{\ell-2},s_{j})-d(x_{\ell-2},s_{i+1})$ (1)

Let $m\in\\{1,2\\}$ be so that $r-m$ is even. Let $v=x_{m}$. By repeating
Equation 1 we get:

$d(x_{r-2},s_{j})-d(x_{r-2},s_{i+1})+4\cdot\left(\frac{r}{2}-O(1)\right)\leq
d(v,s_{j})-d(v,s_{i+1}).$

Since the distance between any two vertices along the infinite face is at most
$\frac{k}{2}$, it follows that:
$-\frac{k}{2}+4\cdot\left(\frac{r}{2}-O(1)\right)\leq
d(v,s_{j})-d(v,s_{i+1})\leq\frac{k}{2}.$ Therefore $r\leq\frac{k}{2}+O(1)$. ∎

##  4 A $\Theta(k^{2})$ Proof for Halin Graphs

In this section we prove Theorem 4. Namely, we show a tight $\Theta(k^{2})$
bound on the number of patterns in a family of graphs that includes Halin
graphs. The Halin graph family (see [28] for history and properties) is a
restricted family of planar graphs. A Halin graph is obtained from an embedded
tree $\mathcal{T}$ with no degree-$2$ vertices by attaching a cycle $C$ to its
leaves in their order of appearance according to the embedding. The cycle is
then the boundary of the infinite face, and we denote its size by $k$. We will
consider a more general family than Halin graphs. Namely, we allow the tree
$\mathcal{T}$ to have degree $2$ vertices, and we allow the cycle $C$ to
contain vertices that are not in $\mathcal{T}$. We will refer to such graphs
as _S-Halin_ graphs. See Figure 13.

Figure 13: An S-Halin graph whose matrix of patterns has VC-dimension $3$.

In this section, we show that the number of distinct patterns in S-halin
graphs is only $O(k^{2})$, and that this bound is tight. In contrast, we show
that the VC-dimension argument is limited to proving $O(k^{3})$ even on such
graphs.

######  Lemma 18.

Let $G=\mathcal{T}\cup C$ be an S-Halin graph, obtained by identifying the
leaves of $\mathcal{T}$ with a subset of vertices of a cycle $C$. If the size
of $C$ is $k$ then the number of distinct patterns in $G$ is $O(k^{2})$.

###### Proof.

Notice that the total number of vertices of $G$ with degree larger than $2$ is
$O(k)$ (and hence, the number of faces in $G$ is also $O(k)$). This is because
$C$ is of size $k$ and $\mathcal{T}$ contains only $k$ leaves (and hence
$O(k)$ vertices with degree larger than $2$). Now consider the dual graph
$G^{*}=(V^{*},E^{*})$. Since every bisector is a simple cycle in $G^{*}$, and
since $|V^{*}|=O(k)$, then the number of arcs in the graphs $G_{\mathcal{B}}$
and $G_{\mathcal{P}}$ is $O(k^{2})$. Therefore, by Corollary 12 the number of
distinct patterns in $G$ is $O(k^{2})$. ∎

We next show that it is not possible to prove Lemma 18 using the VC-dimension
argument. Namely, consider the S-Halin graph of Figure 13 and let $P$ be the
matrix whose rows are the patterns of the graph (recall that each pattern is
in $\\{-1,1\\}^{k-1}$).

######  Proposition 19.

The VC-dimension of $P$ is $3$.

###### Proof.

Consider the following submatrix of $P$ whose rows correspond to the vertices
$v_{0},\dots,v_{7}$ and columns correspond to the edges $e_{1},e_{2},e_{3}$:

$\blockarray{cccc}&e_{1}e_{2}e_{3}\\\ \block{c(ccc)}v_{0}\ \ 1\ \ 1\ \ 1\ \\\
v_{1}\ \ 1\ \ 1-1\\\ v_{2}\ \ 1-1\ \ 1\\\ v_{3}\ \ 1-1-1\\\ v_{4}-1\ \ 1\ \
1\\\ v_{5}-1\ \ 1-1\\\ v_{6}-1-1\ \ 1\\\ v_{7}-1-1-1\\\ $

Since it contains all possible rows, the VC-dimension of $P$ is at least $3$.
∎

It is important to remark that we can generalize the example of Figure 13 to
any large enough $k$, by adding vertices along the infinite face in the part
between $v_{7}$ and $v_{0}$ (clockwise).

So far we have seen that S-Halin graphs have at most $O(k^{2})$ distinct
patterns (Lemma 18), and that the VC-dimension argument is limited to showing
$O(k^{3})$ distinct patterns (Proposition 19). To conclude this section, we
prove that the $O(k^{2})$ bound is tight:

######  Lemma 20.

There exists an S-Halin graphs with $\Omega(k^{2})$ distinct patterns.

###### Proof.

We assume that $k$ is even and denote $k^{\prime}=k/2$. We construct the tree
$\mathcal{T}$ by taking the union of $k^{\prime}+1$ simple paths
$P_{0},P_{1},\ldots,P_{k^{\prime}}$ where every $P_{i}$ is of length $i$ and
all $P_{i}$’s originate from a common vertex $v_{0,0}$. Namely,
$P_{i}=(v_{i,0}-v_{i,1}-\cdots-v_{i,i})$, and $v_{i,0}=v_{j,0}$ for every
$i\neq j$. We choose the embedding of $\mathcal{T}$ so that in a clockwise
tour around $v_{0,0}$, the order of appearance of the paths is
$(P_{1},P_{2},\cdots,P_{k^{\prime}})$.

We define an additional $v_{k^{\prime},k^{\prime}}$-to-$v_{1,1}$ path of
length $k^{\prime}+1$ denoted
$Q=(v_{k^{\prime},k^{\prime}}-q_{1}-q_{2}-\cdots-q_{k^{\prime}}-v_{1,1})$. Let
$C$ be the cycle $Q\circ(v_{1,1}-v_{2,2}-\cdots-v_{k^{\prime},k^{\prime}})$.
Let $G=\mathcal{T}\cup C$. See Figure 14. Note that $|C|$ is $2k^{\prime}=k$.

Figure 14: The S-Halin of Lemma 20 for $k=8$.

Consider the patterns of $G$, when we choose the first vertex to be $v_{1,1}$,
the second $v_{2,2}$, etc. Let $i\in[k^{\prime}],j\in[i-1]$. We claim that the
pattern of $v_{i,j}$ is:

$p_{v_{i,j}}=1^{i-j-1}\circ(-1)^{j}\circ
1^{k^{\prime}+j+1-i}\circ(-1)^{k^{\prime}-j-1}$ (2)

To see why, consider the $v_{i,j}$-to-$v_{t,t}$ distances for $t\leq i$.
Notice that for every $1\leq t\leq i-j$ we have $d(v_{i,j},v_{t,t})=j+t$ and
for every $i-j\leq t\leq i$ we have $d(v_{i,j},v_{t,t})=2i-j-t$. In
particular, they are equal at $t=i-j$. Therefore, the pattern of all the edges
between $v_{1,1}$ and $v_{i,i}$ is $1^{i-j-1}\circ(-1)^{j}$.

Now consider the $v_{i,j}$-to-$v_{t,t}$ distances for $i\leq t\leq
k^{\prime}$. Notice that a shortest $v_{i,j}$-to-$v_{t,t}$ path will never use
$Q$ and instead will go through $(v_{i,i}-v_{i+1,i+1}-\cdots-v_{t,t})$.
Namely, the distance is $d(v_{i,j},v_{t,t})=t-j$. Therefore, the pattern of
all the edges between $v_{i,i}$ and $v_{k^{\prime},k^{\prime}}$ is
$1^{k^{\prime}-i}$.

Finally, consider the $v_{i,j}$-to-$q_{t}$ distances for $1\leq t\leq
k^{\prime}$. For every $1\leq t\leq j+1$ we have
$d(v_{i,j},q_{t})=k^{\prime}+t-j$ and for every $j+1\leq t\leq k^{\prime}$ we
have $d(v_{i,j},q_{t})=k^{\prime}+j+2-t$. In particular they are equal at
$t=j+1$. Therefore the pattern of all the edges between
$v_{k^{\prime},k^{\prime}}$ and $q_{k}^{\prime}$ is
$1^{j+1}\circ(-1)^{k^{\prime}-j-1}$. Overall, we get that $p_{v_{i,j}}$ is as
in Equation (2).

Notice that $p_{v_{i,j}}$ is unique for every different
$i\in[k^{\prime}],j\in[i-1]$. Since the number of such vertices is
$\Omega(k^{\prime 2})=\Omega(k^{2})$, there are $\Omega(k^{2})$ distinct
patterns in $G$. ∎

##  5 Conclusions

In this work we developed a technique for analyzing the structure and number
of distinct patterns in undirected planar graphs. This technique leads to an
improved $\tilde{O}(x+k+|T|)$ space compression of the Okamura-Seymour metric,
and to an optimal $\tilde{O}(k+|T|)$ compression in the special case where the
vertices of $T$ induce a connected component in $G$. Moreover, the technique
leads to an alternative proof of the $x=O(k^{3})$ upper bound on the number of
different patterns.

We have shown that for the family of Halin graphs, the original proof
technique using VC-dimension is not tight, and that our approach easily proves
the tight bound in this case. Going back to planar graphs, we were unable to
come up with constructions of families of planar graphs that have
$x=\omega(k^{2})$ patterns. We therefore make the following conjecture.

######  Conjecture.

The number of distinct patterns over all vertices of a planar graph is
$O(k^{2})$.

We hope that tools we have developed in this work will be useful in proving
this conjecture.

## References

  * [1] Amir Abboud, Pawel Gawrychowski, Shay Mozes, and Oren Weimann.  Near-optimal compression for the planar graph metric.  In 29th SODA, pages 530–549, 2018.
  * [2] Amitabh Basu and Anupam Gupta.  Steiner point removal in graph metrics, 2008.  Unpublished Manuscript, available from http://www.math.ucdavis.edu/~abasu/papers/SPR.pdf.
  * [3] Jon Louis Bentley.  Solutions to klee’s rectangle problems.  Unpublished manuscript, pages 282–300, 1977.
  * [4] Guy E. Blelloch and Arash Farzan.  Succinct representations of separable graphs.  In 21st CPM, pages 138–150, 2010.
  * [5] Hubert T.-H. Chan, Donglin Xia, Goran Konjevod, and Andréa W. Richa.  A tight lower bound for the steiner point removal problem on trees.  In 9th APPROX, pages 70–81, 2006.
  * [6] Hsien-Chih Chang, Pawel Gawrychowski, Shay Mozes, and Oren Weimann.  Near-optimal distance emulator for planar graphs.  In 26th ESA, pages 16:1–16:17, 2018.
  * [7] Hsien-Chih Chang and Tim Ophelders.  Planar emulators for monge matrices.  In 32nd CCCG, pages 141–147, 2020.
  * [8] Yun Kuen Cheung.  Steiner point removal - distant terminals don’t (really) bother.  In 29th SODA, pages 1353–1360, 2018.
  * [9] Yun Kuen Cheung, Gramoz Goranci, and Monika Henzinger.  Graph minors for preserving terminal distances approximately - lower and upper bounds.  In 43rd ICALP, pages 131:1–131:14, 2016.
  * [10] Yi-Ting Chiang, Ching-Chi Lin, and Hsueh-I Lu.  Orderly spanning trees with applications to graph encoding and graph drawing.  In 22nd SODA, pages 506–515, 2001.
  * [11] James R Driscoll, Neil Sarnak, Daniel D Sleator, and Robert E Tarjan.  Making data structures persistent.  Journal of computer and system sciences, 38(1):86–124, 1989.
  * [12] David Eisenstat and Philip N Klein.  Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs.  In 45th STOC, pages 735–744, 2013.
  * [13] Arnold Filtser.  Steiner point removal with distortion _O_(log _k_).  In 29th SODA, pages 1361–1373, 2018.
  * [14] Arnold Filtser, Robert Krauthgamer, and Ohad Trabelsi.  Relaxed voronoi: A simple framework for terminal-clustering problems.  In 2nd SOSA, pages 10:1–10:14, 2019.
  * [15] Viktor Fredslund-Hansen, Shay Mozes, and Christian Wulff-Nilsen.  Truly subquadratic exact distance oracles with constant query time for planar graphs.  In 32nd ISAAC, 2021.  To appear.
  * [16] Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz.  Distance labeling in graphs.  Journal of Algorithms, 53(1):85–112, 2004.
  * [17] Gramoz Goranci, Monika Henzinger, and Pan Peng.  Improved guarantees for vertex sparsification in planar graphs.  In 25th ESA, pages 44:1–44:14, 2017.
  * [18] Anupam Gupta.  Steiner points in tree metrics don’t (really) help.  In 12th SODA, pages 220–227, 2001.
  * [19] Lior Kamma, Robert Krauthgamer, and Huy L. Nguyen.  Cutting corners cheaply, or how to remove steiner points.  SIAM Journal of Computing, 44(4):975–995, 2015.
  * [20] Richard M. Karp and Michael O. Rabin.  Efficient randomized pattern-matching algorithms.  IBM Journal of Research and Development, 31(2):249–260, 1987\.
  * [21] Ken-ichi Kawarabayashi, Philip N Klein, and Christian Sommer.  Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs.  In 38th ICALP, pages 135–146, 2011.
  * [22] Philip N Klein.  Multiple-source shortest paths in planar graphs.  In 16th SODA, volume 5, pages 146–155, 2005.
  * [23] Robert Krauthgamer, Huy L Nguyen, and Tamar Zondiner.  Preserving terminal distances using minors.  SIAM Journal on Discrete Mathematics, 28(1):127–141, 2014.
  * [24] Robert Krauthgamer and Tamar Zondiner.  Preserving terminal distances using minors.  In 39th ICALP, pages 594–605, 2012.
  * [25] Jason Li and Merav Parter.  Planar diameter via metric compression.  In 51st STOC, pages 152–163, 2019.
  * [26] J. Ian Munro and Venkatesh Raman.  Succinct representation of balanced parentheses, static trees and planar graphs.  In 38th FOCS, pages 118–126, 1997.
  * [27] Norbert Sauer.  On the density of families of sets.  Journal of Combinatorial Theory, Series A, 13(1):145–147, 1972\.
  * [28] Maciej M Sysło and Andrzej Proskurowski.  On halin graphs.  In Graph Theory, pages 248–256. Springer, 1983.
  * [29] Mikkel Thorup.  Compact oracles for reachability and approximate distances in planar digraphs.  Journal of the ACM, 51(6):993–1024, 2004.
  * [30] György Turán.  On the succinct representation of graphs.  Discrete Applied Mathematics, 8(3):289–294, 1984.


11footnotetext<EMAIL_ADDRESS>
# Early Abnormal Detection of Sewage Pipe Network: Bagging of Various Abnormal
Detection Algorithms

Zhen-Yu Zhang  Guo-Xiang Shao  Chun-Ming Qiu  Yue-Jie Hou  En-Ming Zhao  and
Chi-Chun Zhou

(May 2022)

###### Abstract

Abnormalities of the sewage pipe network will affect the normal operation of
the whole city. Therefore, it is important to detect the abnormalities early.
This paper propose an early abnormal-detection method. The abnormalities are
detected by using the conventional algorithms, such as isolation forest
algorithm, two innovations are given: (1) The current and historical data
measured by the sensors placed in the sewage pipe network (such as ultrasonic
Doppler flowmeter) are taken as the overall dataset, and then the general
dataset is detected by using the conventional anomaly detection method to
diagnose the anomaly of the data. The anomaly refers to the sample different
from the others samples in the whole dataset. Because the definition of
anomaly is not through the algorithm, but the whole dataset, the construction
of the whole dataset is the key to propose the early abnormal-detection
algorithms. (2) A bagging strategy for a variety of conventional anomaly
detection algorithms is proposed to achieve the early detection of anomalies
with the high precision and recall. The results show that this method can
achieve the early anomaly detection with the highest precision of 98.21%, the
recall rate 63.58% and F1-score of 0.774.

##  1 Induction

In the city, sewage pipe network plays an important role. For example, it
treats the municipal wastewater ensuring that the city and groundwater are not
polluted. However, if the sewage pipe network is abnormal, it will affect the
normal operation of the whole city and cause a series of problems. For
example, the ignoring of abnormalities of sewage pipe network will lead to the
explosion of the pipe and environmental pollution during a heavy rain or pipe
aging. Therefore, the early detection of the abnormalities is important,
because abnormalities can be checked in time to avoid problems caused by
abnormalities.

Conventionally, the hardware based methods are used to detect abnormalities of
sewage pipe network and they can be categoried into two types: (1) Detection
of the data. This method is to detect the pipe network data through the
flowmeter, analyze it and diagnose the abnormality. For example: F larrarte
[1] introduces the detection application and measurement strategy of flowmeter
in sewage pipe network in detail. (2) The detection of sewage pipe network.
This method is to detect and diagnose abnormalities by closed-circuit
television detection (CCTV) and sonar. For example: Cezary et al. [2]
Introduced the application of CCTV in sewage pipeline, discussed the
operational process of pipeline inspection and improved it. Olga Duran et al.
[3] Proposed the defects of CCTV in pipe network detection, and proposed
sensors based on infrared and microwave to detect sewers. Although the
hardware based methods can efficiency detect, the methods have two main
shortcomings: (1) Only based on hardware equipment, the timeliness of
detection is not high, and it is difficult to feed back the abnormalities
detected in the sewage pipe network timely. (2) The coverage of hardware
equipment is limited, and it’s not ensure that the hardware can detect all
abnormalities in the sewage pipe network.

Therefore, in view of the shortcomings of hardware detection, at this stage,
many scholars have established different models for the situation of sewage
pipe network based on statistical or machine learning methods, and then
combined with the data obtained by hardware detection to solve the problems of
sewage pipe network. For example: micevski et al. [4] constructed the
structural degradation model of rainwater pipe network based on Markov chain
and calibrated it with Bayes. Mashford et al. [5] established a pipe network
condition prediction model based on support vector machine and applied it to
the sewage pipe network in Adelaide, Australia. Harvey R R et al. [6] used
CCTV detection data and random forest algorithm to predict the structural
state of sewer network in Guelph, Canada. Tran et al. [7, 8]used neural
network model to predict the structural and hydraulic conditions of sewage
pipe network.

These methods can effectively solve the shortcomings of hardware detection and
improve the ability of detecting the sewage pipe network, but these methods
need to model the sewage pipe network in advance. When the status of sewage
pipe network is not clear, these methods can not be used for the detection of
sewage pipe network. Therefore, this paper proposes an efficient and low-cost
unsupervised early abnormal-detection method, which can effectively detect the
sewage pipe network without modeling. Although the algorithm use the existing
conventional anomaly detection algorithm, there are two innovations: (1) The
current and historical data measured by the sensors placed in the sewage pipe
network (such as ultrasonic Doppler flowmeter) are taken as the overall
dataset, and then the general dataset is detected by using the conventional
anomaly detection method to diagnose the anomaly of the data. The anomaly
refers to the sample different from the others samples in the whole dataset.
Because the definition of anomaly is not through the algorithm, but the whole
dataset, the construction of the whole dataset is not only the key to propose
the early abnormal-detection algorithms, but also one of the important
innovations of this paper. (2) In this paper, the conventional anomaly
detection methods such as Isolation Forest, One Class SVM and Local Outlier
Factor are used to detect the whole dataset. However, these traditional
anomaly detection algorithms sometimes get unsatisfactory results. Therefore,
this paper proposes bagging strategies of various anomaly detection algorithms
to achieve high precision and recall rate data anomaly detection. In the
experiment, the data are collected from the ultrasonic Doppler flowmeter
installed at 136 points in the sewage pipe network of Erhai Lake, and then use
these data to train the algorithm obtained after bagging strategy. The results
show that this method can achieve early anomaly detection with the highest
accuracy of $98.21\%$, the recall rate $63.58\%$ and F1-score of $0.774$.

This paper is organized as following: In Sec. 2, introduce the data collected
from the 136 ultrasonic Doppler flowmeters in the sewage pipe network of Erhai
Lake. And discuss the types of abnormalities of sewage pipe network. In Sec.
3, the construction of the overall data is introduced. Then, introduces the
specific steps of anomaly detection based on current and historical data. In
Sec. 4, Propose the method of this paper. The common anomaly detection
algorithms are reviewed, and the strategy of bagging of various abnormal
detection algorithms is proposed. In Sec. 5, the experiments are conducted and
the results are analyzed. The conclusions and discussions are given in Sec. 6.

##  2 Types of abnormalities

The intelligent monitoring project of The Pollution Control of Erhai Lake was
established by the government of Dali City, China, in order to rectify the
water pollution of Erhai Lake [9]. A total of 136 mobile monitoring points
have been established around Erhai Lake, and ultrasonic Doppler flowmeter is
used to detect the flow at the monitoring points to obtain the flow data. This
paper studies these flow data, and summarizes five types of anomalies.

1) Mixing of external water sources

External water sources generally refer to rainwater, groundwater, etc. Taking
the mixed rainwater as an example, when it rains, the rainwater flows into the
sewage pipe network, and the sewage flow and liquid level rise sharply. Mixing
with external water sources increases the load of sewage pipe network, which
is easy to lead to damage of sewage pipe network and environmental pollution.

2) Abnormal flowmeter

When the flowmeter is abnormal, the measured data will be abnormal. For
example: In sewage networks, waste could flow into the pipes and cause blocked
flowmeter probe. The sewage flow and liquid level data detected by the
flowmeter will drop sharply in the meantime. If the situation is not rectified
in a timely manner, it is likely to cause complete damage to the flowmeter. At
this time, the flowmeter cannot feed back the flow data of the local pipe
network.

3) Sewage pipe network blockage

When a large number of garbage and foreign matters enter the sewage pipe
network, it may cause the blockage of the sewage pipe network. At this time,
the instantaneous flow and liquid level detected by the flowmeter will also
decrease. If the sewage pipe network can’t be dredged in time, it will lead to
pipe network damage and environmental pollution easily.

4) Network fluctuation and discontinuous transmission

When the sewage pipe network is located in the area with poor signal, the data
transmission of the sensor corresponding to the pipe network will be
interrupted due to the unstable signal. In the period of time without data,
the sewer network can’t be monitored effectively, there will be some hidden
dangers.

5) Full sewage pipe network

When the sewage pipe network is full, the instantaneous flow and liquid level
are almost zero. If the sewage in full pipe state is not treated in time, it
may lead to explosion of the pipe, which will affect the normal operation of
sewage pipe network.

##  3 Data introduction and Data preprocessing

###  3.1 Data introduction

According to the data of 136 monitoring points, finally 13830 typical data are
summarized for model training. The data mainly has five dimensions: time (day,
hour), instantaneous flow ($m^{3}$/h), liquid level (m) and flow rate (m/s).
Among them, instantaneous flow and liquid level are the main indicators of
diagnostic data in this paper. The sampling interval unit of data is 5
minutes. When the data is abnormal, abnormal is used to identify the data
exception.

Combined with the above five abnormal conditions, we classify the data into
three abnormal data types: sudden change of instantaneous flow and liquid
level to zero, sudden increase of instantaneous flow and liquid level, and
sudden decrease of instantaneous flow and liquid level. This paper intercepts
some data for these three types for display, as shown in Tbl. LABEL:table1. I
F in Tbl. LABEL:table1 represents instantaneous flow.

Table 1: Different exception data types. For example, this paper selects the most representative three groups of data (9 / 7, 9 / 12, 4 / 12) in the data set, which respectively reflect three different data anomaly types: the sudden change of instantaneous flow and liquid level to 0, the sudden increase of instantaneous flow and liquid level, and the sudden decrease of instantaneous flow and liquid level. Type | Day | Hour |  | I F
---
($m^{3}$/h)
| liquid level
---
($m$)
| flow rate
---
($m/s$)
Label
The instantaneous flow and liquid level suddenly change to zero | 9$/$7 | 11$:$20 | 1.288 | 0.18 | 0.081 | /
9$/$7 | 11$:$25 | 20.929 | 0.173 | 0.115 | /
9$/$7 | 11$:$30 | 4.326 | 0.168 | 0.03 | /
9$/$7 | 11$:$35 | 43.969 | 0.164 | 0.13 | /
9$/$7 | 11$:$40 | 0 | 0 | 0 | abnormal
9$/$7 | 11$:$45 | 0 | 0 | 0 | abnormal
Sudden increase of instantaneous flow and liquid level | 9$/$12 | 7$:$05 | 193.759 | 0.291 | 0.537 | /
9$/$12 | 7$:$10 | 153.54 | 0.281 | 0.463 | /
9$/$12 | 7$:$15 | 141.475 | 0.265 | 0.444 | /
9$/$12 | 7$:$20 | 132.941 | 0.255 | 0.44 | /
9$/$12 | 7$:$25 | 929.935 | 1.237 | 2.016 | abnormal
9$/$12 | 7$:$30 | 1478.788 | 1.626 | 3.286 | abnormal
Sudden decrease of instantaneous flow and liquid level | 4$/$12 | 9$:$00 | 2103.394 | 0.575 | 1.079 | /
4$/$12 | 9$:$05 | 2015.826 | 0.58 | 1.035 | /
4$/$12 | 9$:$10 | 2004.826 | 0.575 | 1.03 | /
4$/$12 | 9$:$15 | 2007.798 | 0.581 | 1.026 | /
4$/$12 | 9$:$20 | 755.699 | 0.361 | 0.738 | abnormal
4$/$12 | 9$:$25 | 705.991 | 0.357 | 0.677 | abnormal

It can be seen in Tbl. LABEL:table1 that among the data with instantaneous
flow and liquid level suddenly changing to zero, the instantaneous flow and
liquid level suddenly changed around 11:35, and after 11:35, the instantaneous
flow and liquid level have always been zero. Therefore, these data are marked
with abnormal label, corresponding to the five abnormal types introduced
above. This phenomenon may be caused by abnormal conditions such as network
fluctuations and discontinuous transmission, abnormal flow meters, and full
sewage pipe networks. As can be seen from the data in Tbl. LABEL:table1, the
instantaneous flow and liquid level suddenly increased around 7:20. So the
data after 7:20 is marked with abnormal label, corresponding to the five
abnormal types described above. This phenomenon may be caused by the mixing of
external water sources and other abnormal conditions. When the instantaneous
flow and liquid level suddenly decrease, it can be seen from the data in the
Tbl. LABEL:table1 that there is a sudden decrease in the instantaneous flow
and liquid level before and after 9:15. Therefore, the data after 9:15 is
marked with abnormal label, corresponding to the five abnormal types described
above. This may be due to blocking the sewage pipe network, abnormal flowmeter
and other abnormal conditions

###  3.2 Data preprocessing

In order to explore the correlation between current data and historical data
in sewage data, and predict the data of future state through historical data,
this paper preprocesses the data. Among them, the research preprocesses the
data by sliding window, and the operation flow is shown in Fig. 1.

Figure 1: Schematic diagram of data preprocessing

In Fig. 1, two sliding windows are set to intercept data. Each sliding step of
the sliding window is 1, and the time interval of each step is 5 minutes. The
first sliding window intercepts the samples of historical data in the N time
periods before A in the figure, and the data include instantaneous flow,
liquid level and flow rate; The second sliding window selects the data label
starting from point a and containing the future data from A to P. If there are
abnormal values in P, it outputs abnormal, otherwise it outputs normal.

##  4 Method

###  4.1 Anomaly detection algorithm: A brief review

Anomaly detection is to detect the abnormal data that does not conform to the
behavior in the data, and mark its abnormalities. This paper mainly uses three
anomaly detection algorithms: One Class SVM, Isolation Forest and Local
Outlier Factor to detect the flow data of sewage pipe network.

One class SVM. The algorithm is a single classification anomaly detection
algorithm given by $Sch\"{o}lkopf$ et al[10]. The algorithm trains only one
sample and detects the unique class in the sample. If the class is detected,
it returns "yes". If the class is not detected, it returns "no".

The algorithm of one class SVM is as follows. If one-dimensional training data
$X_{i}\in R^{n}{(i=1,2,3,....,n)}$ is set, there is:

$\mathop{\min}_{\omega,i,\xi,\rho}\frac{1}{2}\omega^{T}\omega-\rho+\frac{1}{vn}\sum_{i=1}^{n}\xi_{i}$
(1) $\left\\{\begin{array}[]{lr}\omega^{T}\Phi{(x_{i})}\geq\rho{-}\xi_{i}\\\
\xi_{i}\geq{0,}{i=1,2,....,n}\end{array}\right.$ (2)

The following results are obtained through conversion:

$\mathop{\min}_{a}\frac{1}{2}\alpha^{T}Q_{ij}\alpha,\left\\{\begin{array}[]{lr}0\leq\alpha_{i}\leq\frac{1}{vn},{i=1,2,....,n}\\\
e^{T}\alpha=1\end{array}\right.$ (3)

In formula (3):

$Q_{ij}=K(x_{i},x_{j})=\varphi(x_{k})^{T}\varphi(x_{l})$ (4)

The decision function is:

$f(x)=sign{(\sum_{i=1}^{n}K(x,x_{i}-\rho))}$ (5)

The decision function can calculate the category of data and divide the
calculation results into two categories. The calculation result of positive
category data is 1 and that of negative category data is - 1.
The symbol function is:

$g(x)=\sum_{i=1}^{n}\alpha_{i}K(x,x_{i})-\rho$ (6)

This function can judge whether the test data is normal. The greater the
distance from the test point, the greater the deviation of the data from the
zero point.

Isolation Forest. The concept of this algorithm is an unsupervised learning
proposed by F Liu and other scholars[11], which can quickly detect data sets.
Compared with other algorithms, isolated forest does not need to establish any
data model and any label description for anomaly detection. It only needs to
estimate the data in turn to find the outliers.

The isolation forest algorithm puts the data on an isolated tree[12], then
checks the characteristics of the data in turn, and classifies the data with
the same characteristics into one class, otherwise it is isolated. Because
there are great differences between abnormal data and normal data in essence,
abnormal data will be isolated very early. As shown in Fig. 2, this figure is
an example of isolation forest. According to the above description, it can be
inferred that a was isolated at the earliest and is most likely an abnormal
point.

Figure 2: Schematic diagram of isolation forest

Local Outlier Factor. The algorithm is defined by breuing et al.[13] The
algorithm mainly determines whether the data is abnormal according to the data
density around the data points. Firstly, the local reachable density of each
data point is calculated, and then an outlier factor of each data point is
further calculated through the local reachable density. The outlier factor
indicates the outlier degree of a data point. When the factor value is larger,
it means that the outlier degree is higher, which means that the data is
abnormal. The smaller the factor value, the lower the degree of outlier, and
the data is normal.

The idea of local outlier factor algorithm can be shown in Fig. 3. Set $C_{1}$
is a low-density area and set $C_{2}$ is a high-density area. According to the
traditional density based outlier detection algorithm, the distance between p
and the adjacent point in $C_{2}$ is less than the distance between any data
point in $C_{1}$ and its adjacent point, and p will be regarded as a normal
point, while locally, p is actually an isolated point, the outlier algorithm
can effectively detect outlier in the case of local factor.

Figure 3: Schematic diagram of local outlier factor

###  4.2 The bagging based algorithm

This paper uses the anomaly detection algorithm which is introduced in Chapter
4.1 to detect the anomaly flow data in Chapter 3.1. Among them, the
instantaneous flow and liquid level in the data are the main indicators of
anomaly diagnosis. When the abnormal type data shown in Tbl. LABEL:table1
appears during the detection, the abnormal data is marked with abnormal.
However, through a large number of experiments, it is found that the precision
and recall rate of the experimental results obtained by the anomaly detection
algorithm in Chapter 4.1 are not perfect. Therefore, through the integration
strategy this paper adapt the integrated learning of the anomaly algorithm in
Chapter 4.1. The idea of ensemble learning is to correct other model results
through a large number of weak learning model results, so as to make the model
more consistent with the dataset and have a better precision.

The methods of ensemble learning mainly include bagging and boosting. The
integrated learning method used in this paper is bagging. Bagging algorithm
[14, 15] uses multiple weak learning models to train the randomly collected
data sets, and then combines the results of multiple weak learning to form the
final strong learner model. The bagging process of this paper is shown in Fig.
(4). Training samples are randomly used to train three anomaly detection
algorithms: one class SVM, isolation forest and local outlier factor. Finally,
these algorithms are combined by finding the combination of the intersection
of the three algorithms to obtain the integrated algorithm G(x) which is
proposed in this paper.

Figure 4: Bagging flow chart

##  5 Result

In this paper, we detect the flow data by the anomaly detection algorithm.
When the flow data is abnormal, the abnormal data would be marked. Therefore,
the main purpose of this paper is that explore the precision and recall of the
algorithm marking abnormal, and judge the performance of the algorithm model
proposed in this paper by marking the precision and recall of abnormal and the
corresponding F1-score index. Among them, F1-score is a measurement index of
classification problems, referred to as $\emph{F}_{1}$ for short. It is the
harmonic average of accuracy and recall, with the maximum of 1 and the minimum
of 0. Generally, the larger the index, the better the performance of the
model. The calculation method of $\emph{F}_{1}$ is as follows:

$\emph{F}_{1}=2\cdot{\frac{precision\cdot{recall}}{precision+recall}}$ (7)

If there is a strong correlation between historical data and future data, the
precision and recall rate of the model can be improved. In order to get the
better correlation, we need to find the most appropriate N and P, and this
paper explored this problem. As shown in Tbl. LABEL:table2, set N to 5, 10,
15, 20, 25 and P to 7 respectively. The comparison shows that when N=$5$, the
integrated anomaly detection algorithm has a high precision and recall.
Therefore, when N=$5$, the data of history and future has a good correlation.

Table 2: Precision and recall of the algorithm in different $N$ cases | start
---
(hour)
| end
---
(hour)
$N$ | $P$ | $abnormal$ | $normal$ |  $recall($%$)$ |  $precision($%$)$ | $\emph{F}_{1}$
$2$ | $9$ | $5$ | $7$ | $184$ | $546$ | $59.24$ | $99.09$ | $0.742$
$2$ | $9$ | $10$ | $7$ | $169$ | $511$ | $59.76$ | $58.06$ | $0.739$
$2$ | $9$ | $15$ | $7$ | $154$ | $476$ | $57.79$ | $95.70$ | $0.721$
$2$ | $9$ | $20$ | $7$ | $139$ | $441$ | $51.08$ | $93.42$ | $0.66$
$2$ | $9$ | $25$ | $7$ | $126$ | $404$ | $13.49$ | $89.47$ | $0.234$

When N=$5$ is determined, the abnormal data has good correlation before and
after. Therefore, then looks for an appropriate P to make the correlation
between the abnormal data better. As shown in Tbl. LABEL:table3, all of the N
are $7$, and P is set to $5$, $6$, $8$, $9$ and $10$ respectively. Through
comparison, it can be found that when N=$5$ and P=$5$, the precision and
recall of the integrated anomaly detection algorithm are better. Therefore,
when N=$5$ and P=$5$, the correlation of historical data and future data is
the best.

Table 3: Precision and recall of the algorithm in different $P$ cases | start
---
(hour)
| end
---
(hour)
$N$ | $P$ | $abnormal$ | $normal$ |  $recall($%$)$ |  $precision($%$)$ | $\emph{F}_{1}$
$2$ | $9$ | $5$ | $5$ | $173$ | $577$ | $63.58$ | $98.21$ | $0.772$
$2$ | $9$ | $5$ | $6$ | $179$ | $561$ | $61.45$ | $98.21$ | $0.756$
$2$ | $9$ | $5$ | $8$ | $189$ | $531$ | $37.04$ | $100$ | $0.541$
$2$ | $9$ | $5$ | $9$ | $194$ | $516$ | $35.57$ | $100$ | $0.525$
$2$ | $9$ | $5$ | $10$ | $198$ | $502$ | $34.34$ | $100$ | $0.511$

When N=$5$ and P=$5$, the correlation of abnormal data is the best. Therefore,
in the case of N=$5$ and P=$5$, this paper trains the three anomaly detection
algorithms, adjusts the parameters, and then integrates the three anomaly
detection algorithms through using the integration strategy. Finally, the
integrated experimental results are obtained.

In Fig. 5, a to c are the confusion matrix obtained after training of One
Class SVM, Isolation Forest and Local Outlier Factor. The precision and recall
rates corresponding to the three anomaly detection algorithms and the
integrated algorithm are shown in Tbl. LABEL:table4, and the comparison
diagram of the results is shown in Fig. 6. The experimental results show that
the recall rate of the integrated algorithm is 63.85$\%$ and the precision
rate is 98.21$\%$. It’s an effective anomaly detection algorithm for early
warning of abnormal sewage flow data.

Table 4: Recall and precision of three anomaly detection algorithms and integrated algorithms $model$ |  $recall($%$)$ |  $precision($%$)$ | $\emph{F}_{1}$
---|---|---|---
$OneClassSVM$ | $63.85$ | $98.21$ | $0.774$
$IsolationForest$ | $100$ | $25.63$ | $0.408$
$LocalOutlierFactor$ | $83.24$ | $58.30$ | $0.686$
$Bagging$ | $63.85$ | $98.21$ | $0.774$
Figure 5: Confusion matrix of three anomaly detection algorithms Figure 6:
Comparison of results of three anomaly detection algorithms and integrated
algorithms

When the predicted results of the three anomaly detection algorithms are not
good, the integrated algorithm proposed in this paper can significantly
improve the precision while retaining a high recall rate. As shown in Tbl.
LABEL:six, it can be seen that although the integrated algorithm loses little
recall rate, compared with One Class SVM, the precision of the algorithm is
significantly improved and the false alarm rate of abnormal sewage flow is
greatly reduced. The confusion matrix and result comparison diagram of three
anomaly detection algorithms and integrated algorithms are shown in Fig. 7 and
Fig. 8 respectively.

Table 5: Recall and precision of three anomaly detection algorithms and integrated algorithms $model$ |  $recall($%$)$ |  $precision($%$)$ | $\emph{F}_{1}$
---|---|---|---
$OneClassSVM$ | $100$ | $2.38$ | $0.046$
$IsolationForest$ | $55.56$ | $55.56$ | $0.556$
$LocalOutlierFactor$ | $55.56$ | $3.97$ | $0.074$
$Bagging$ | $55.56$ | $83.33$ | $0.667$
Figure 7: Confusion matrix of three anomaly detection algorithms Figure 8:
Confusion matrix of three anomaly detection algorithms

Through the above experimental results, it can be seen that the unsupervised
anomaly detection integration algorithm proposed in this paper is an effective
and good performance method, which can effectively warn the abnormal sewage
flow data.

##  6 Conclusions and Outlooks

This paper proposed a abnormal-detection algorithm. Based on the original
hardware facilities, the anomaly detection algorithm is combined with the data
obtained by the hardware facilities to form a feasible, low-cost and effective
sewage pipe network monitoring system. The data of this project comes from the
intelligent monitoring project of The Pollution Control of Erhai Lake. The
anomaly detection algorithm which is proposed in this paper is trained by
using these data, and we can get a better result that the precision is
98.21$\%$, recall rate is 63.85$\%$, and F1-score is $0.774$. It’s a more
effective anomaly detection algorithm to detect and warn when the flow data of
sewage pipe network is abnormal. This paper has completed the design of
abnormal early warning system of sewage pipe network from the aspects of
theory and practice, and achieved a good results in practical application and
simulation scenarios. However, there are some other defect in this research of
abnormal early warning of sewage pipe network, it can be further carried out
in future research:

1) Implementation of abnormal classification and early warning algorithm of
sewage pipe network. The abnormal early warning system of sewage pipe network
has been finished, but there is no good result for the classification of
abnormal points. In the subsequent research, we can collect a large number of
abnormal data of sewage pipe network to train the classification algorithm of
abnormal sewage flow, and finish the task of abnormal classification and early
warning algorithm of sewage pipe network.

2) Improve the precision of sewage anomaly early warning algorithm. Although
this project has improved the precision of anomaly early warning to 98.21$\%$,
and recall rate also could be better. Through the lucubration and updates of
the model, we can improve the recall rate and precision of sewage anomaly
early warning algorithm.

3) This project mainly focuses on the early warning of abnormal sewage flow in
non full pipe, As for full pipe,this project don’t involve too much.
Therefore, the follow-up study can aim at abnormal early warning for the full
pipe of sewage flow.

##  7 Acknowledgments

This project get the strongly support from the intelligen monitoring project
of The Pollution Control of Erhai Lake. Chi-Chun Zhou acknowledges the
supported by National Natural Science Funds of China (Grant No. 62106033),
Yunnan Youth Basic Research Projects (202001AU070020 and 202001AU070022), and
Doctoral Programs of Dali University (KYBS201910). En-Ming Zhao acknowledges
the supported by National Natural Science Funds of China (Grant No. 62065001).

## References

  * [1] F. Larrarte, Velocity fields within sewers: An experimental study, Flow Measurement & Instrumentation 17 (2006), no. 5 282–290.
  * [2] Cezary, Madryas, , , Bogdan, and Przybyła, Inspection of pipes as an element of operating municipal sewerage networks, Tunnelling & Underground Space Technology (1998).
  * [3] O. Duran, K. Althoefer, and L. D. Seneviratne, State of the art in sensor technologies for sewer inspection, IEEE Sensors Journal 2 (2002), no. 2 73–81.
  * [4] T. Micevski, G. Kuczera, and P. Coombes, Markov model for storm water pipe deterioration, Journal of Infrastructure Systems 8 (2002), no. 2 49–56.
  * [5] J. Mashford, D. Marlow, D. Tran, and R. May, Prediction of sewer condition grade using support vector machines, Journal of Computing in Civil Engineering 25 (2011), no. 4 283–290.
  * [6] R. R. Harvey and E. A. Mcbean, Predicting the structural condition of individual sanitary sewer pipes with random forests, Canadian Journal of Civil Engineering 41 (2014), no. 4 294–303(10).
  * [7] Neural networks deterioration models for serviceability condition of buried stormwater pipes, Engineering Applications of Artificial Intelligence 20 (2007), no. 8 1144–1151.
  * [8] D., H., Tran, B., J., C., Perera, A. Wm, and Ng, Comparison of structural deterioration models for stormwater drainage pipes, Computer Aided Civil & Infrastructure Engineering (2009).
  * [9] S. Xiang, Y. Pang, Z. S. Chu, X. Z. Hu, and L. Q. Xue, Response of inflow water quality to land use pattern in northern watershed of lake erhai, Environmental Science (2016).
  * [10] Schölkopf, Bernhard, Platt, C. John, Shawe-Taylor, John, Smola, J. Alex, Williamson, and C. Robert, Estimating the support of a high-dimensional distribution., Neural Computation (2001).
  * [11] T. L. Fei, M. T. Kai, and Z. H. Zhou, Isolation forest, in IEEE International Conference on Data Mining, 2008.
  * [12] F. T. Liu, K. M. Ting, and Z. H. Zhou, Isolation-based anomaly detection, Acm Transactions on Knowledge Discovery from Data 6 (2012), no. 1 1–39.
  * [13] M. M. Breunig, H.-P. Kriegel, R. T. Ng, and J. Sander, Lof: identifying density-based local outliers, in SIGMOD ’00, 2000.
  * [14] E. Bauer and R. Kohavi, An empirical comparison of voting classification algorithms: Bagging, boosting, and variants, Machine Learning 36 (1999), no. 1-2 105–139.
  * [15] S. Dudoit and J. Fridlyand, Bagging to improve the accuracy of a clustering procedure, Bioinformatics 19 (2003), no. 9 1090–1099.