#  Succinct Data Structure for Path Graphs

Girish Balakrishnan∗ Sankardeep Chakraborty† N S Narayanaswamy∗
and Kunihiko Sadakane†
∗Indian Institute of Technology Madras, †University of Tokyo, Chennai, India
Tokyo, Japan<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We consider the problem of designing a succinct data structure for path graphs
(which are a proper subclass of chordal graphs and a proper superclass of
interval graphs) on $n$ vertices while supporting degree, adjacency, and
neighborhood queries efficiently. We provide the following two solutions for
this problem:

  1. 1.

an $n\log n+o(n\log n)$-bit succinct data structure that supports adjacency
query in $O(\log n)$ time, neighborhood query in $O(d\log n)$ time and
finally, degree query in $\min\\{O(\log^{2}n),O(d\log n)\\}$ where $d$ is the
degree of the queried vertex.

  2. 2.

an $O(n\log^{2}n)$-bit space-efficient data structure that supports adjacency
and degree queries in $O(1)$ time, and the neighborhood query in $O(d)$ time
where $d$ is the degree of the queried vertex.

Central to our data structures is the usage of the classical heavy path
decomposition by Sleator and Tarjan [1], followed by a careful bookkeeping
using an orthogonal range search data structure using wavelet trees [2] among
others, which maybe of independent interest for designing succinct data
structures for other graph classes.

##  1 Introduction

An intersection graph $G=(V,E)$ is an undirected graph whose vertices are
mapped by $f$ to a family of sets $F$ such that vertex $a_{1}$ is adjacent to
$a_{2}$ in $G$ if and only if $f(a_{1})\cap f(a_{2})\neq\phi$. Based on the
family of sets $F$ we get different graph classes. For instance, if $F$ is the
set of intervals on the real number line, then we get interval graphs. Yet
another example is chordal graphs, defined as the intersection graph of sub-
trees of a tree. Path graphs is the class of graphs obtained when $F$ is the
set of paths, $P_{1},\ldots,P_{n}$ in a tree $T$ such that two paths intersect
if and only if the corresponding vertices are adjacent. It is well-known that
the class of path graphs is a proper subclass of chordal graphs and a proper
superclass of interval graphs [3].

In this work, we address the problem of designing a succinct data structure
for the class of path graphs so that basic navigational queries such as
degree, adjacency, and neighborhood can be answered efficiently. Formally,
given a set $T$ consisting of combinatorial objects with a certain property,
our goal is to store any arbitrary member $x\in T$ using the information-
theoretic minimum of $\log(|T|)+o(\log(|T|))$ bits (throughout this paper,
$\log$ denotes the logarithm to the base $2$) while still being able to
support the queries efficiently on $x$. Recently, Acan et al. [4] showed that
the information-theoretic lower bound for representing unlabeled interval
graphs with $n$ vertices is at least $n\log n$ bits, and as path graphs are a
proper superclass of interval graphs, this lower bound also holds true for
path graphs. Interestingly, we manage to construct an $n\log n+o(n\log n)$-bit
data structure for representing path graphs matching this information-
theoretic lower bound, thus, obtaining succinct data structure for path graphs
for the first time in literature. This is the main contribution of this work.
We leave the question of whether path graphs are only a constant factor larger
in size than the class of interval graphs as an open problem.

Previous Related Work. There already exists a huge body of work on
representing various classes of graphs succinctly. A partial list of such
special graph classes would be trees [5, 6], planar graphs [7], partial
$k$-tree [8], and arbitrary graphs [9]. Recent results have appeared in
literature for intersection graphs like interval graphs due to Acan et al [4]
and chordal graphs due to Munro and Wu[10]. For interval graphs, [4] gives an
$n\log n+O(n)$ bit succinct data structure that supports degree and adjacency
queries in $O(1)$ time while neighborhood query in constant time per
neighbour. In the case of chordal graphs, [10] gives an $n^{2}/4+o(n^{2})$ bit
succinct data structure that supports adjacency query in $f(n)$ time where
$f(n)\in\omega(1)$, degree of a vertex in $O(1)$ time and neighborhood in
$(f(n))^{2}$ time per neighbour. The main motivation behind our work stems
from these two above-mentioned works. Since path graphs is a strict subclass
of chordal graphs and a strict superclass of interval graphs it would be
interesting to see whether one can design such an efficient data structure for
path graphs as well.

Our Results. Before we get to our results, note the following terminology for
graph $G=(V,E)$:

  * •

for $u,v\in V$, adjacency query checks if $\\{u,v\\}\in E$,

  * •

for $u\in V$, the neighborhood query returns all the vertices that are
adjacent to $u$ in $G$, and

  * •

for $u\in V$, the degree query returns the number of vertices adjacent to $u$
in $G$.

Our primary result in this work is an $n\log n+o(n\log n)$-bit succinct
representation for unlabelled connected path graphs. It is obtained from the
clique tree representation $(T,P_{1},\ldots,P_{n})$ [11] [12] on the input
path graph. Here $T$ is the clique tree [12] and $P_{i},1\leq i\leq n$, are
the paths in it. We then store $T$ succinctly along with the end-points of the
paths $P_{i}$ in it. Formally we have the following result.

######  Theorem 1.

Path graphs have an $n\log n+o(n\log n)$-bit succinct representation. The
succinct representation constructed from the clique tree representation
supports for a vertex $u$ the following queries:

  1. 1.

adjacency query in $O(\log n)$ time,

  2. 2.

the neighborhood query in $O(d_{u}\log n)$ time, and

  3. 3.

the degree query in $\min\\{O(\log^{2}n),O(d_{u}\log n)\\}$ time

where $d_{u}$ is the degree of vertex $u$.

The central tool that we use in obtaining the above succinct data structure
result and the space-efficient data structure is heavy path decomposition
(HPD) [1] performed on the clique tree $T$. The HPD when performed on the
clique tree $T$ gives the heavy path tree $\mathcal{T}$; explained in Section
2.2. Each node of the heavy path tree $\mathcal{T}$ corresponds to a heavy
path of the clique tree $T$. The property that heavy path tree $\mathcal{T}$
has at most $\lceil\log n\rceil$ levels helps us achieve the query times of
Theorem 1. Additionally, we observe that the intersection of the paths
$P_{1},\ldots,P_{n}$ with each heavy path defines a natural interval graph
giving us the space-efficient data structure for path graphs. Further we
observe that the union of these interval graphs corresponding to nodes in the
same level of the heavy path tree is also an interval graph. To obtain the
space-efficient data structure, we store the interval graphs at each level of
the heavy path tree using the results from [4] and organize them into at most
$\log n$ levels. Even though we use additional $\log n$ factor storage in the
space-efficient data structure over the succinct representation, we can
respond to all the queries more efficiently. This is our second result.

######  Theorem 2.

There exists a space-efficient representation for path graphs using
$O(n\log^{2}n)$ bits. The representation supports the following queries for a
vertex $u$:

  1. 1.

the adjacency and degree queries in $O(1)$ time,

  2. 2.

the neighborhood query in $O(d_{u})$ time where $d_{u}$ is the degree of the
vertex $u$.

The increased efficiency of the space-efficient data structure comes at the
expense of increased space which arises due to the duplication of edges of
path graph among the $\log n$ interval graphs. Another difference is that the
succinct data structure performs orthogonal range search to implement the
queries while the space-efficient data structure delegates the queries to
those of the underlying interval graph as implemented in [4].

All the preliminary terminology and concepts required for rest of the sections
are in Section 2 and 3. In Section 4, a succinct representation for path
graphs is presented and Section 5 describes the space-efficient data
structure.

##  2 Preliminaries

For a graph $G$, through out the paper we denote the set of vertices and edges
by $V(G)$ and $E(G)$, respectively. Familiarity with basic graph theory as in
[13] and graph algorithms as given in [14] is expected.

###  2.1 Path Graphs and Its Properties

A graph $G$ is a path graph if there exists a tree $T$ and family of paths
$\mathcal{P}=\\{P_{1},\ldots,P_{n}\\}$ in $T$ such that $G$ is the
intersection graph of paths in $\mathcal{P}$. $G$ is said to have the
representation $(T,\mathcal{P})$; see Figure 1. A vertex $a\in V(G)$ is
simplicial if the set of vertices adjacent to $a$, denoted $N(a)$, induces a
complete sub-graph of $G$ [3]. The ordering $\rho=[a_{1},\ldots,a_{n}]$ of
$V(G)$ is called a perfect elimination scheme if for all $i,X_{i}=\\{a_{j}\in
N(a_{i})\mid j>i,\\}$ is complete. Every path graph has a simplicial vertex
and a perfect elimination scheme. It is well known that any simplicial vertex
can start a perfect elimination scheme; see Theorem 4.1 and Lemma 4.2 of [3]
for more details. Let $\mathcal{C}$ be the set of maximal cliques of $G$ and
for every $a\in V(G)$ let $\mathcal{C}_{a}=\\{C|C\in\mathcal{C}\text{ and
}a\in V(C)\\}$. Consider a tree $T$ with $V(T)=\mathcal{C}$ such that for
every $a\in V(G)$, $\mathcal{C}_{a}$ induces a sub-tree $T_{a}$ of $T$. $G$ is
a choral graph if it is the intersection graph of set of such induced sub-
trees. For chordal graphs such a tree $T$ is called the clique tree of $G$
[3]. Clique tree can be computed in polynomial time [11]. The following is a
characterisation of path graphs as a sub-class of chordal graphs [11][12].

Figure 1: (a) Path graph $G$ with maximal cliques
$\mathcal{C}=\\{C_{1},\ldots,C_{8}\\}$, (b) Clique tree representation of $G$
where each node $i$ corresponds to $C_{i}\in\mathcal{C}$. For vertices $u,v\in
V(G)$ we have paths $P_{u},P_{v}$ such that $V(P_{u})\cap V(P_{v})\neq\phi$ if
and only if $\\{u,v\\}\in E(G)$. The clique tree shown here is pre-processed
as explained in Section 3.

######  Theorem 3.

The graph $G$ is a path graph if and only if there exists a clique tree $T$,
such that for every $v\in V(G)$, the set of maximal cliques containing $v$
form a path in $T$.

In this paper, we are concerned with the construction of a succinct
representation for path graphs and the construction mechanism takes as input,
$(T,\mathcal{P})$. Also, apart from clique tree $T$ we will introduce the
heavy path tree $\mathcal{T}$ in the next section. Elements of $V(T)$ and
$V(\mathcal{T})$ will be henceforth referred to as nodes of $T$ and
$\mathcal{T}$, respectively whereas for any graph $G$, elements of $V(G)$ will
be referred to as its vertices. The following is known from [11].

######  Remark 4.

The number of maximal cliques in a path graph $G$ with $n$ vertices is at most
$n$.

###  2.2 Heavy Path Decomposition

Heavy path decomposition (HPD) was introduced in [1] and used in [15] and [16]
for rooted trees. In the heavy path decomposition for a rooted tree $T$, each
internal node $u$ selects an edge $(u,v)$ such that the child $v$ has the
maximum number of descendants among the children of $u$. In the case of a tie
among two children of $u$ pick any one arbitrarily. The edge $(u,v)$ is called
a heavy edge. Thus, each internal node of $T$ selects exactly one edge as
heavy edge. Further, it is known that each vertex has at most two heavy edges
incident on it, one with its parent and second with one of its children. An
edge that is not chosen as a heavy edge by any internal node is called a light
edge. Consider the forest of paths obtained by removing light edges from $T$.
We refer to each path in this forest as a heavy path. The heavy path
decomposition of $T$ partitions the nodes of $T$ into the set of heavy paths
denoted by $\mathcal{H}$. Also, it partitions the edges of $T$ into heavy and
light edges; see Figure 2.

Figure 2: Heavy path decomposition of a rooted tree with $n=12$ nodes. At node
1, $\\{1,2\\}$ is picked as the heavy edge as 2 is the child of 1 with maximum
number of descendants. Edge $\\{1,12\\}$ is a light edge. Path
$\\{1,2,3,4,5\\}$ of the clique tree is compressed as a single node in the
heavy path tree $\mathcal{T}$. As a light edge connects a node to a sub-tree
that is at least halved in size, the heavy path tree will have at most $\log
n$ levels. Thick red lines indicate heavy edges and thin blue lines indicate
light edges respectively.

######  Remark 5.

The heavy paths in ${\cal H}$ are of two types: those that contain at least
one heavy edge and those which do not contain a heavy edge. A heavy path which
does not contain a heavy edge is a leaf node whose incident edge in $T$ is a
light edge. For instance, in Figure 2 heavy path $\\{1,2,3,4,5\\}$ is of
former type whereas heavy path $\\{6\\}$ is of later type.

Using the heavy path decomposition of $T$ we define a tree which we call the
heavy path tree denoted by $\mathcal{T}$. Let $\Phi:\mathcal{H}\rightarrow
V(\mathcal{T})$ be a bijection such that for $u\in V(H_{1})$ and $v\in
V(H_{2}),e=\\{u,v\\}$ is a light edge if and only if there exists an edge
$\\{\Phi(H_{1}),\Phi(H_{2})\\}$ in $\mathcal{T}$. Subsequently, whenever
$H_{1}$ and $H_{2}$ satisfy this property we will call $H_{1}$ and $H_{2}$
light edge separable heavy paths. In other words, $H_{1},H_{2}\in\mathcal{H}$
are light edge separable heavy paths in $T$ if and only if $\Phi(H_{1})$ and
$\Phi(H_{2})$ are adjacent in $\mathcal{T}$. Further, we refer to the edge
$\\{\Phi(H_{1}),\Phi(H_{2})\\}\in E({\cal T})$ using the light edge between
and $H_{1}$ and $H_{2}$, which in this case is $e$. The heavy path that
contains the root of $T$ is the root of $\mathcal{T}$. The level of the root
node is 0, and each other node has a level which is its distance from the
root. A sub-path of a heavy path will be referred to as heavy sub-path. The
following remark is important for the rest of the paper. The following lemmata
are well-known [15], and we extensively use them here.

######  Lemma 6.

The number of levels in $\mathcal{T}$ is at most $\lceil\log n\rceil$.
Further, a path in $\mathcal{T}$ has at most $2\lceil\log n\rceil$ edges.

######  Lemma 7.

For $u,v\in V(\mathcal{T}),V(\Phi^{-1}(v))\cap V(\Phi^{-1}(u))=\phi$ and
$V(T)=\bigcup\limits_{v\in V(\mathcal{T})}V(\Phi^{-1}(v))$. In other words,
the nodes of $T$ are partitioned among the nodes of $\mathcal{T}$.

######  Lemma 8.

Let $P$ be a path in $T$. $P$ can be partitioned into heavy sub-paths
$\Pi=\\{\pi_{1},\ldots,\pi_{k}\\},1\leq k\leq 2\lceil\log n\rceil+1$.

###### Proof.

Consider a path $P=v_{1}e_{2}v_{2}e_{2}\ldots v_{l-1}e_{l}v_{l},1\leq l\leq n$
in $T$ where $v_{1},\ldots,v_{l}\in V(P)$ and $e_{2},\ldots,e_{l}\in E(P)$.
Let $f_{1},\ldots,f_{t}$ denote the $t\geq 0$ light edges in $P$ indexed in
the order in which they occur in $P$ from $v_{1}$ to $v_{l}$. Then, we
consider $P=\pi_{1}f_{1}\pi_{2}f_{2}\ldots f_{t}\pi_{t+1}$ such that for each
$1\leq i\leq t+1$, $\pi_{i}$ is a maximal heavy sub-path in $P$. $f_{i}$ is
the light edge between the last vertex of $\pi_{i}$ and the first vertex of
$\pi_{i+1}$. For each $1\leq i\leq t+1$, let $H_{i}$ denote the heavy path in
$\mathcal{H}$ such that $\pi_{i}$ is a heavy sub-path of $H_{i}$. By our
convention on the edge label in ${\cal T}$, the edge
$\\{\Phi(H_{i}),\Phi(H_{i+1})\\}$ is considered to be $f_{i}$. Thus, for $P$
in $T$ we have a path $P^{\prime}=\Phi(H_{1})f_{1}\Phi(H_{2})f_{2}\ldots
f_{t}\Phi(H_{t+1})$ in $\mathcal{T}$. Let $|V(P^{\prime})|=t+1$ and from Lemma
6 we know that $t\leq 2\lceil\log n\rceil$. Thus, the number of heavy sub-
paths, $k\leq 2\lceil\log n\rceil+1$. ∎

The following propositions are straightforward and merely stated explicitly in
the context of heavy path trees.

######  Proposition 9.

Let $P$ be a path in $\mathcal{T}$ and $l\leq\log n$ be an integer. $P$
consists of at most two nodes with level $l$.

Through out this paper we will use the notation $[n]=\\{1,2,\ldots,n\\}$.

###  2.3 Useful Succinct Data Structures

Table 1 summarises the set of data structures we use in this work which we
will explain in this section starting with ordinal trees.

Succinct Data Structure for Ordinal Trees. Let the children of any $u\in V(T)$
be $\\{u_{1},\ldots,u_{z}\\}$ for some $z>0$. Tree $T$ is called an ordinal
tree if for $i<j$, $u_{i}$ is to the left of $u_{j}$ [17]. By considering
ordinal trees as balanced parenthesis Navarro and Sadakane [17] has given a
$2n+o(n)$ bit succinct data structure.

Data Structure |  Query |  Functionality |  To store |  Ref
---|---|---|---|---
Ordinal trees |  $\texttt{lca}(u,v)$ |  returns lowest common ancestor of nodes $u$ and $v$ |  the clique tree in Sections 4 and 5 |  [17]
$\texttt{parent}(u)$ |  returns parent of node $u$ |  |  [17]
|  $\texttt{first\\_child}(u)$ |  returns first child of node $u$ |  |  [17]
|  $\texttt{rmost\\_child}(u)$ |  returns rightmost leaf of the sub-tree rooted at $u$ |  |  [17]
|  $\texttt{child\\_rank}(u)$ |  returns the number of siblings to the left of $u$ |  |  [17]
Bit string |  $\texttt{rank}(B,b,i)$ |  returns the number of bit $b$’s up to and including position $i$ on bit vector $B$ from left |  for instance, the BP representation of clique tree |  [18]
$\texttt{select}(B,b,i)$ |  returns the position of the $i-$th bit $b$ in the bit vector $B$ from left |  |  [18]
Increasing number sequence |  $\texttt{accessNS}(B,i)$ |  returns the $i-$th number in the sequence $B$ |  the starting nodes of paths in clique tree in Section 4 |  Section 2.8 of [19]
Wavelet tree |  $\texttt{access}(S,c)$ |  returns the $y-$coordinate of the point with $x-$coordinate value $c$ stored in wavelet tree $S$ |  the paths as points in a two dimensional grid in Section 4 |  [2]
|  $\texttt{select}(S,[i,i^{\prime}],[j,j^{\prime}])$ |  returns the points in the input range $[i,i^{\prime}]\times[j,j^{\prime}]$ |  |  [2]
|  $\texttt{count}(S,[i,i^{\prime}],[j,j^{\prime}])$ |  returns the number of points in the input range $[i,i^{\prime}]\times[j,j^{\prime}]$ |  |  [2]
Table 1: Summary of the data structures used. Note that $b\in\\{0,1\\}$.

######  Lemma 10.

For any ordinal tree $T$ with $n$ nodes, there exists a $2n+o(n)$ bit Balanced
Parentheses (BP) based data structure that supports the following four
functions among others in constant time :

  1. 1.

${\texttt{lca}}(i,j)$, returns the lowest common ancestor of two nodes $i,j$
in $T$,

  2. 2.

${\texttt{parent}}(i)$, returns the parent of node $i$ in $T$, and

  3. 3.

${\texttt{first\\_child}}(i)$, returns the first child of node $i$ in $T$.

  4. 4.

${\texttt{rmost\\_leaf}}(i)$, returns the rightmost leaf of sub-tree rooted at
node $i$ in $T$.

  5. 5.

${\texttt{child\\_rank}}(i)$, returns the number of siblings to the left of
node $i$ in $T$.

Rank-Select Data Structure. Bit-vectors are extensively used in the succinct
representation given in Section 4. The following data structure due to
Golynski et al. [20] and the functions supported by it are useful.

######  Lemma 11.

Let $B$ be an $n-$bit vector and $b\in\\{0,1\\}$. There exists an $n+o(n)$ bit
data structure that supports the following functions in constant time:

  1. 1.

${\texttt{rank}}(B,b,i)$: Returns the number of $b$’s up to and including
position $i$ in the bit vector $B$ from the left.

  2. 2.

${\texttt{select}}(B,b,i)$: Returns the position of the $i$-th $b$ in the bit
vector $B$ from left. For $i\notin[n]$ it returns 0.

Non-decreasing Integer Sequence Data Structure. Given a set of positive
integers in the non-decreasing order we can store them efficiently using the
differential encoding scheme for increasing numbers; see Section 2.8 of [19].
Let $S$ be the data structure that supports differential encoding for
increasing numbers then the function $\texttt{accessNS}(S,i)$ returns the
$i-$th number in the sequence.

######  Lemma 12.

Let $S$ be a sequence of $n$ non-decreasing positive integers
$a_{1},\ldots,a_{n},1\leq a_{i}\leq n$. There exists a $2n+o(n)$ bit data
structure that supports ${\texttt{accessNS}}(S,i)$ in constant time.

###### Proof.

We will prove the lemma by giving a construction of such a data structure.
$a_{1}$ will be represented by a sequence of $a_{1}$ 1’s followed by a 0.
Subsequently $a_{i}$’s are represented by storing $a_{i}-a_{i-1}$ many 1’s
followed by a 0. It will take $2n$ bits since there are $n$ 0’s and $n$ 1’s.
Let this bit string be stored using the data structure of Lemma 11 and be
denoted as $B$. $B$ takes $2n+o(n)$ bits. $\texttt{accessNS}(S,i)$ can be
implemented using $\texttt{rank}(B,1,\texttt{select}(B,0,i))$ on the bit
string obtained. ∎

Wavelet Trees. Central to the design of the succinct data structure of Section
4 is the two-dimensional orthogonal range search data structure used to store
points in the two-dimensional plane. Specifically, we use the $n\log n+o(n\log
n)$ bit succinct wavelet trees due to Makinen and Navarro [2] that requires
the $n$ points to have distinct integer-valued $x-$ and $y-$coordinates in the
range $[n]\times[n]$. The wavelet tree has the following properties.

  1. 1.

The wavelet tree is a balanced binary search tree. Each node of the tree is
associated with an interval range of the $x$-coordinate.

  2. 2.

The range at the root of the wavelet tree has the interval $[1,n]$ and the
interval at each leaf is of the form $[a,a],1\leq a\leq n$.

  3. 3.

The range $[a,a^{\prime}],1\leq a<a^{\prime}\leq n,$ at an internal node is
partitioned among the ranges $[a,a^{\prime\prime}]$ and
$[a^{\prime\prime}+1,a^{\prime}]$ at its children, that is,
$[a,a^{\prime}]=[a,a^{\prime\prime}]\bigcup[a^{\prime\prime}+1,a^{\prime}]$.

We use the following result regarding wavelet trees from [2].

######  Lemma 13.

Given a set of $n$ points $\\{(a_{1},b_{1}),\ldots,(a_{n},b_{n})\\}$ where
$a_{i},b_{i}\in[n],1\leq i\leq n$ such that $a_{i}\neq a_{j}$ and $b_{i}\neq
b_{j}$ for $i\neq j$, there exists an $n\log n(1+o(1))$ bit orthogonal range
search data structure $S$ that supports the following functions:

  1. 1.

${\texttt{search}}(S,[i,i^{\prime}],[j,j^{\prime}])$: Returns the points in
the input range $[i,i^{\prime}]\times[j,j^{\prime}],1\leq i\leq i^{\prime}\leq
n,1\leq j\leq j^{\prime}\leq n,$ in the increasing order of the $x-$coordinate
taking $O(\log n)$ time per point.

  2. 2.

${\texttt{count}}(S,[i,i^{\prime}],[j,j^{\prime}])$: Returns the number of
points in the input range $[i,i^{\prime}]\times[j,j^{\prime}],1\leq i\leq
i^{\prime}\leq n,1\leq j\leq j^{\prime}\leq n,$ in $O(\log n)$ time.

  3. 3.

${\texttt{access}}(S,i):$ Returns the $y-$coordinate of the point stored in
$S$ with $x-$coordinate $i$ in $O(\log n)$ time.

##  3 Clique Tree Pre-processing = HPD + Pre-order Traversal

The pre-processing of the clique tree allows the paths in $\mathcal{P}$ to be
stored efficiently so that adjacency and neighbourhood queries can be
supported. This involves the following two steps:

  1. 1.

heavy path decomposition of $T$, and

  2. 2.

transformation of $T$ into an ordinal tree which is labeled based on the pre-
order traversal

A clique tree is organized as an ordinal tree as explained below.

HPD + Pre-order traversal of $T$. Fix a root node for $T$ and perform heavy
path decomposition on it. For $v\in V(T)$ order its children
$(w_{1},\ldots,w_{c})$ such that $\\{v,w_{1}\\}$ is a heavy edge. Let the
children adjacent to $v$ by light edges $(w_{2},\ldots,w_{c})$, be ordered
arbitrarily. This ordering of children of a node of the clique tree makes it
an ordinal tree. Label the nodes of this ordinal tree based on the pre-order
traversal; see Section 12.1 of [14] for more details of pre-order traversal of
trees. Labels assigned to nodes in this manner are called the pre-order label
of the nodes. Through out the rest of our paper this ordinal rooted clique
tree labeled with pre-order will be referred to as the clique tree.

Representing paths as tuples. Path $P\in\mathcal{P}$ is represented as
$P=(l,r),l,r\in V(T)$, where $l$ and $r$ are the end points of $P$ such that
$l\leq r$. We say that $l$ and $r$ are the starting and ending nodes of the
path, respectively. Let $T_{a}$ and $T_{b}$ be the sub-trees of $T$ rooted at
$a$ and $b$, respectively. For $e=\texttt{lca}(l,r)$, the following
propositions regarding the clique tree $T$ follow from pre-order traversal.

######  Proposition 14.

Let $b\in V(T_{a})$ for $a\in V(T)$. The following hold.

  1. 1.

The sub-tree rooted at $b$ is contained in $T_{a}$.

  2. 2.

Let $V(P)\nsubseteq V(T_{a})$. $|V(P)\cap V(T_{a})|\geq 1$ if and only if
$a\in V(P)$.

  3. 3.

$l\in V(T_{a})$ and $e<a$ if and only if $r\notin V(T_{a})$ and $a\in V(P)$.

  4. 4.

If $l\in V(T_{a})$ and $e=a$ then $r\in V(T_{a})$.

  5. 5.

If there are $z$ descendants of $a$ in $T_{a}$ then the nodes of $V(T_{a})$ is
the set $\\{a,a+1,\ldots,a+z\\}$.

######  Proposition 15.

Let $\pi$ be a heavy path of length $k\geq 1$ in $T$ with $a$ and $b$ as its
end points such that $a\leq b$. Then $b=a+k$.

We will subsequently use the notation $[a,b]$ to refer to the ordered set of
nodes $(a,a+1,\ldots,b-1,b)$. $a$ and $b$ are referred to as the starting and
ending points of $[a,b]$. Figure 1 shows the pre-processed clique tree for the
example path graph $G$, also shown in the figure. The heavy path starting at 1
and ending at 4 have contiguous numbering and is denoted as $[1,4]$. We
emphasize that a sub-path of a heavy path is also represented using the same
notation. A heavy path or a heavy sub-path $[a,a]$ contains only the vertex
$a$.

######  Lemma 16.

For any heavy path $H=[a^{\prime},b^{\prime}]$ of $T$ a path $\pi=[a,b]$ such
that $a^{\prime}\leq a\leq b\leq b^{\prime}$ is a heavy sub-path of $H$. For
the heavy sub-path $\pi$ of $H$ let $c$ and $d$ be the rightmost leaves in the
sub-tree rooted at $b$ and $a$, respectively. The following are true about
$\pi$.

  1. 1.

If $a\leq u\leq b$ then $u\in V(\pi)$.

  2. 2.

$a\leq b\leq c\leq d$.

  3. 3.

Let $Q=(s,t)$ be a path in $T$ . If $s>d$ then $\pi$ and $Q$ are vertex
disjoint paths in $T$.

###### Proof.

The proofs are as follows:

  1. 1.

This is true due to Proposition 15.

  2. 2.

$a\leq b$ by definition of $\pi$. $b\leq c\leq d$ since the labels are based
on pre-order traversal.

  3. 3.

From Proposition 14 we know that, if there are $z$ descendants of $a$ in
$T_{a}$, then the nodes of $V(T_{a})$ is the set $\\{a,a+1,\ldots,a+z\\}$.
Since $d$ is the label of the rightmost descendant of $a$, it follows that
$d=a+z$. Since $a+z=d<s$, we know that $Q$ starts at a node that is visited
after the nodes of $T_{a}$. Since $t>s$ the pre-order labels of nodes in $Q$
is not in $V(T_{a})$. Thus, $Q$ and $T_{a}$ are vertex disjoint, and thus $Q$
and $\pi$ are vertex disjoint.

∎

######  Lemma 17.

  1. Let $a\in V(T)$ and $a_{l}$ be a child of $a$ such that $l\in V(T_{a_{l}})$ .

  2. 1.

If ${\texttt{lca}(l,r)}<a$ then $r\in[{\texttt{rmost\\_leaf}(a)+1,n}]$.

  3. 2.

If ${\texttt{lca}(l,r)}=a$ then
$r\in[{\texttt{rmost\\_leaf}(a_{l})+1,\texttt{rmost\\_leaf}(a)}]$.

###### Proof.

The proof is as follows:

  1. 1.

Since $\texttt{lca}(l,r)<a$ and $r\geq l$, $r$ is a node that is visited after
the nodes in $T_{a}$ are visited, that is,
$r\in[\texttt{rmost\\_leaf}(a)+1,n]$.

  2. 2.

If $\texttt{lca}(l,r)=a$ then there exists a child of $a$, say $a_{r}$ such
that $r\in T_{a_{r}}$. $a_{l}<a_{r}$ since $l<r$. Thus,
$r\in[\texttt{rmost\\_leaf}(a_{l})+1,\texttt{rmost\\_leaf}(a)]$.

∎

###  3.1 Organizing the heavy paths and light edges of $T$

Let $\mathcal{H}$ be the set of heavy paths of $T$; recall from Section 2.2.
Let $H,H^{\prime}\in\mathcal{H}$ such that $H=[a,b]$ and
$H^{\prime}=[a^{\prime},b^{\prime}]$. We define a total order
$(\mathcal{H},\prec_{\mathcal{H}})$ as follows.
$H\prec_{\mathcal{H}}H^{\prime}$ if $a<a^{\prime}$. In other words,
$H\prec_{\mathcal{H}}H^{\prime}$ if $H$ is visited before $H^{\prime}$ in the
pre-order traversal of $T$.

Total order on the heavy sub-paths of paths in $T$. $\prec_{\mathcal{H}}$,
extends to the set of heavy sub-paths of a path. Let
$\Pi=\\{\pi_{1},\ldots,\pi_{k}\\},1\leq k\leq 2\lceil\log n\rceil+1$, be the
set of heavy sub-paths of path $P$; see Lemma 8 for details regarding heavy
sub-paths of a path. For any two $\pi,\pi^{\prime}\in\Pi$, let
$H,H^{\prime}\in{\cal H}$ be such that $\pi$ and $\pi^{\prime}$ are heavy sub-
paths of $H$ and $H^{\prime}$, respectively. $\pi\prec\pi^{\prime}$ if
$H\prec_{\mathcal{H}}H^{\prime}$. In other words, we order the heavy sub-paths
according to the order of the heavy paths that contain it.

Convention: In the rest of this section, $P$ denotes the path $(l,r)$ in $T$,
and $\Pi$ is the decomposition of $P$ into heavy sub-paths. In other words,
for the path $P$, $\Pi=(\pi_{1},\ldots,\pi_{k}),1\leq k\leq 2\lceil\log
n\rceil+1,\pi_{i}\prec\pi_{j}$ if $1\leq i<j\leq k$. Also, for every
$\pi_{i}\in\Pi$, $\pi_{i}=(a_{i},b_{i})$. In Section 5, we assume that the
heavy paths of $T$ are numbered such that $H_{i}\prec_{\mathcal{H}}H_{j}$ if
and only if $1\leq i<j\leq n$.

###  3.2 Characterising path intersections in $T$

In this section, first we will show that a heavy sub-path $\pi\in\Pi$
partitions the nodes of $T$ into four ranges of pre-order labels. Paths
intersecting $\pi$ are characterised based on these ranges. Adjacency and
neighbourhood queries for $\pi$ are implemented using orthogonal range search
queries that use these ranges.

Successor of a heavy sub-path. For $\pi_{i},\pi_{j}\in\Pi$, if there exists
nodes $u_{1}\in V(\pi_{i})$ and $u_{2}\in V(\pi_{j})$ such that
$\\{u_{1},u_{2}\\}$ is a light edge in $T$ then we say that $\pi_{i}$ and
$\pi_{j}$ are light edge separable heavy sub-paths; an extension of the notion
of light edge separable heavy paths from Section 2.2. Let $1\leq i<j\leq
k,\pi_{i},\pi_{j}\in\Pi$. $\pi_{j}$ is called the successor of $\pi_{i}$ if
$\pi_{i}\prec\pi_{j}$ and they are light edge separable. We define a mapping
$\texttt{succ}:\Pi\times\\{1,2\\}\rightarrow\Pi\cup\\{\texttt{NULL}\\}$ from a
heavy sub-path of $P$ to its successors defined as follows.

  1. 1.

Successors for $\pi_{1}$: We have the following sub-cases depending on the
number of heavy sub-paths of $P$.

    1. (a)

$k=1:$ $\pi_{1}$ has no successors, that is,
$\texttt{succ}(\pi_{1},1)=\texttt{succ}(\pi_{1},2)=\texttt{NULL}$.

    2. (b)

$k>1:$ There are two cases:

      1. i.

$\pi_{1}$ has both its successors that is
$\texttt{succ}(\pi_{1},1)=\pi_{2}\neq\texttt{NULL}$ and
$\texttt{succ}(\pi_{1},2)=\pi_{z}\neq\texttt{NULL}$ for $z\in[3,k]$. This
happens when $P$ can be divided into two sub-paths $P^{1}=(e,l)$ and
$P^{2}=(e,r)$ such that $e\neq l\neq r$.

      2. ii.

$\pi_{1}$ has only one successor. Let $\pi_{2}=(a_{2},b_{2})$ and $a_{1}\neq
b_{1}$. There are two sub-cases.

        1. A.

$\texttt{succ}(\pi_{1},1)=\texttt{NULL}$ and
$\texttt{succ}(\pi_{1},2)=\pi_{2}$. This happens when
$\texttt{parent}(a_{2})=a_{1}$.

        2. B.

$\texttt{succ}(\pi_{1},1)=\pi_{2}$ and
$\texttt{succ}(\pi_{1},2)=\texttt{NULL}$. This happens when
$\texttt{parent}(a_{2})=b_{1}$.

When $a_{1}=b_{1}$, we define $\texttt{succ}(\pi_{1},1)=\pi_{2}$ and
$\texttt{succ}(\pi_{1},2)=\texttt{NULL}$.

  2. 2.

Successors for $\pi_{i},i\neq 1$: $\texttt{succ}(\pi_{i},1)=\pi_{i+1}$ if
$\pi_{i+1}\in\Pi$ and $\pi_{i},\pi_{i+1}$ are light edge separable else
$\texttt{succ}(\pi_{i},1)=\texttt{NULL}$. For all $i\neq
1,\texttt{succ}(\pi_{i},2)=\texttt{NULL}$.

Note that if $\texttt{succ}(\pi_{1},2)=\pi_{z}\neq\texttt{NULL}$ for
$z\in[3,k]$ then
$\texttt{succ}(\pi_{z-1},1)=\texttt{succ}(\pi_{z-1},2)=\texttt{NULL}$. Also,
$\texttt{succ}(\pi_{k},1)=\texttt{succ}(\pi_{k},2)=\texttt{NULL}$.

Interval ranges associated with $\pi_{i}\in\Pi,1\leq i\leq k$. For $u\in
V(T)$, $\texttt{rmost\\_leaf}(u)+1$ is the node that is visited immediately
after traversing the nodes in sub-tree rooted at $u$ in the pre-order
traversal of $T$. We associate four ranges of nodes of $T$ with $\pi_{i}$. The
four ranges associated with $\pi_{i}$ denoted by $R_{j}(i),1\leq j\leq 4,$ are
as follows.

  1. i.

$R_{1}(i)$: Range of nodes visited before $a_{i}$ in the pre-order traversal
of $T$. If $i=1$ and $a_{1}>1$ then $R_{1}(1)=[1,a_{1}-1]$ else
$R_{1}(1)=\phi$.

  2. ii.

$R_{2}(i)$: Heavy sub-path $\pi_{i}$, $[a_{i},b_{i}]$.

  3. iii.

$R_{3}(i)$: There are two cases depending on existence of
$\texttt{succ}(\pi_{i},1)$.

    1. (a)

If $\texttt{succ}(\pi_{i},1)\neq\texttt{NULL}$ then $R_{3}(i)=R_{3}^{1}(i)\cup
R_{3}^{2}(i)$ where

      1. i.

$R_{3}^{1}(i)$: Range of nodes visited after $b_{i}$ and before the nodes of
$T_{a_{i+1}}$, $R_{3}^{1}(i)=[b_{i}+1,a_{i+1}-1]$.

      2. ii.

$R_{3}^{2}(i)$: Range of nodes visited after visiting the nodes of
$T_{a_{i+1}}$ and before the right-most leaf of $T_{b_{i}}$. If
$\texttt{rmost\\_leaf}(a_{i+1})\neq\texttt{rmost\\_leaf}(b_{i})$ then
$R_{3}^{2}(i)=[\texttt{rmost\\_leaf}(a_{i+1})+1,\texttt{rmost\\_leaf}(b_{i})]$
else $R_{3}^{2}(i)=\phi$.

    2. (b)

If $\texttt{succ}(\pi_{i},1)=\texttt{NULL}$ and
$b_{i}\neq\texttt{rmost\\_leaf}(b_{i})$ then
$R_{3}(i)=[b_{i}+1,\texttt{rmost\\_leaf}(b_{i})]$ else $R_{3}(i)=\phi$. Note
that $b_{i}\neq\texttt{rmost\\_leaf}(b_{i})$ means that $b_{i}$ is not a leaf.

  4. iv.

$R_{4}(i)$: There are two cases depending on $\texttt{succ}(\pi_{i},2)$.

    1. (a)

If $\texttt{succ}(\pi_{i},2)\neq\texttt{NULL}$ then by definition $i=1$ and
$R_{4}(1)=R_{4}^{1}(1)\cup R_{4}^{2}(1)$ where

      1. i.

$R_{4}^{1}(1)$: Range of nodes visited after nodes in $T_{b_{1}}$ and before
nodes of $T_{a_{z}}$. If $\texttt{rmost\\_leaf}(b_{1})+1\neq a_{z}$ then
$R_{4}^{1}(1)=[\texttt{rmost\\_leaf}(b_{1})+1,a_{z}-1]$ else
$R_{4}^{1}(1)=\phi$. Note that $\texttt{rmost\\_leaf}(b_{1})+1\neq a_{z}$
means $b_{1}$ is not a leaf.

      2. ii.

$R_{4}^{2}(1)$: Range of nodes visited after nodes in $T_{a_{z}}$ and before
the right-most node of $T_{a_{1}}$. If
$\texttt{rmost\\_leaf}(a_{z})\neq\texttt{rmost\\_leaf}(a_{1})$ then
$R_{4}^{2}(1)=[\texttt{rmost\\_leaf}(a_{z})+1,\texttt{rmost\\_leaf}(a_{1})]$
else $R_{4}^{2}(1)=\phi$.

    2. (b)

If $\texttt{succ}(\pi_{i},2)=\texttt{NULL}$ and
$\texttt{rmost\\_leaf}(a_{i})\neq b_{i}$ then
$R_{4}(i)=[\texttt{rmost\\_leaf}(b_{i})+1,\texttt{rmost\\_leaf}(a_{i})]$ else
$R_{4}(i)=\phi$.

Remark. For each $1\leq i\leq k$, $1\leq j\leq 4,R_{j}(i)\subseteq[1,n]$ are
intervals, and $R_{1}(i)\cup R_{2}(i)\cup R_{3}(i)\cup
R_{4}(i)=V(T_{a_{i}})\cup[1,a_{i}-1]$. Further, the range of nodes greater
than $\texttt{rmost\\_leaf}(a_{i})$ is not relevant, as it follows from Lemma
16 that the starting point of a path intersecting with $P$ should be in one of
these ranges. See Figure 3 for a pictorial representation of the ranges and
Table 2 and 3 summarise the ranges.

Figure 3: The regions generated by (a) $\pi_{1}$, and (b) $\pi_{i},2\leq i\leq n$. For $j\in\\{1,2,t,i,i+1\\}$, $\texttt{rmost\\_leaf}(a_{j})=d_{j}$ and $\texttt{rmost\\_leaf}(b_{j})=c_{j}$. |  |  Condition |  Range
---|---|---|---
$i=1$ |  |  |
$R_{1}$ |  $a>1$ |  $R_{1}(1)=[1,a_{1}-1]$
|  $a=1$ |  $R_{1}(1)=\texttt{NULL}$
|  $R_{2}$ |  |  $R_{2}(1)=[a_{1},b_{1}]$
|  $R_{3}$ |  $\texttt{succ}(\pi_{1},1)\neq\texttt{NULL}$ |  $R_{3}(1)=R_{3}^{1}(1)\cup R_{3}^{2}(1)$ 1. $R_{3}^{1}(1)$: $R_{3}^{1}(1)=[b_{1}+1,a_{2}-1]$. 2. $R_{3}^{2}(1)$: If $\texttt{rmost\\_leaf}(a_{2})\neq\texttt{rmost\\_leaf}(b_{1})$ then $R_{3}^{2}(1)=[\texttt{rmost\\_leaf}(a_{2})+1,\texttt{rmost\\_leaf}(b_{1})]$ else $R_{3}^{2}(1)=\texttt{NULL}$.
|  |  $\texttt{succ}(\pi_{1},1)=\texttt{NULL}$ |  If $\texttt{rmost\\_leaf}(a_{2})\neq\texttt{rmost\\_leaf}(b_{1})$ then $R_{3}^{2}(1)=[\texttt{rmost\\_leaf}(a_{2})+1,\texttt{rmost\\_leaf}(b_{1})]$ else $R_{3}^{2}(1)=\texttt{NULL}$
|  $R_{4}$ |  $\texttt{succ}(\pi_{1},2)\neq\texttt{NULL}$ |  $R_{4}(1)=R_{4}^{1}(1)\cup R_{4}^{2}(1)$ 1. $R_{4}^{1}(1)$: If $\texttt{rmost\\_leaf}(b_{1})+1\neq a_{t}$ then $R_{4}^{1}(1)=[\texttt{rmost\\_leaf}(b_{1})+1,a_{t}-1]$ else $R_{4}^{1}(1)=\texttt{NULL}$. 2. $R_{4}^{2}(1)$: If $\texttt{rmost\\_leaf}(a_{t})\neq\texttt{rmost\\_leaf}(a_{1})$ then $R_{4}^{2}(1)=[\texttt{rmost\\_leaf}(a_{t})+1,\texttt{rmost\\_leaf}(a_{1})]$ else $R_{4}^{2}(1)=\texttt{NULL}$.
|  |  $\texttt{succ}(\pi_{1},2)=\texttt{NULL}$ |  If $\texttt{rmost\\_leaf}(a_{1})\neq b_{1}$ then $R_{4}(1)=[\texttt{rmost\\_leaf}(b_{1})+1,\texttt{rmost\\_leaf}(a_{1})]$ else $R_{4}(1)=\texttt{NULL}$
Table 2: Ranges for heavy sub-path $\pi_{1}\in\Pi$. |  |  Condition |  Range
---|---|---|---
$i\neq 1$ |  |  |
$R_{1}$ |  |  $R_{1}(i)=\texttt{NULL}$
$R_{2}$ |  |  $R_{2}(i)=[a_{i},b_{i}]$
|  $R_{3}$ |  $\texttt{succ}(\pi_{i},1)\neq\texttt{NULL}$ |  $R_{3}(i)=R_{3}^{1}(i)\cup R_{3}^{2}(i)$ 1. $R_{3}^{1}(i)$: $R_{3}^{1}(i)=[b_{i}+1,a_{i+1}-1]$. 2. $R_{3}^{2}(i)$: If $\texttt{rmost\\_leaf}(a_{i+1})\neq\texttt{rmost\\_leaf}(b_{i})$ then $R_{3}^{2}(i)=[\texttt{rmost\\_leaf}(a_{i+1})+1,\texttt{rmost\\_leaf}(b_{i})]$ else $R_{3}^{2}(i)=\texttt{NULL}$.
|  |  $\texttt{succ}(\pi_{i},1)=\texttt{NULL}$ |  If $\texttt{rmost\\_leaf}(b_{i})\neq\texttt{rmost\\_leaf}(b_{i})$ then $R_{3}(i)=[b_{i}+1,\texttt{rmost\\_leaf}(b_{i})]$ else $R_{3}(i)=\texttt{NULL}$
|  $R_{4}$ |  $\texttt{rmost\\_leaf}(a_{i})\neq b_{i}$ |  $R_{4}(i)=[\texttt{rmost\\_leaf}(b_{i})+1,\texttt{rmost\\_leaf}(a_{i})]$
|  |  $\texttt{rmost\\_leaf}(a_{i})=b_{i}$ |  $R_{4}(i)=\texttt{NULL}$
Table 3: Ranges for heavy sub-path $\pi_{i}\in\Pi$. Note that for $i\neq
1,\texttt{succ}(\pi_{i},2)=\texttt{NULL}$.

Characterising intersection of a path $Q$ with a heavy sub-path. Let $Q=(s,t)$
be a path in $\mathcal{P}$. Let the sequence of nodes in $Q$ be
$(s=u_{1},u_{2},\ldots,u_{z}=t),1\leq z\leq n$. Let $y$ be the first node in
the sequence such that $y\in V(P)$. From Lemma 7, it follows that $\Pi$
partitions the vertices of $P$, and thus $y$ belongs to a unique $\pi\in\Pi$.
Convention: For ease of presentation, in the rest of this section, $Q=(s,t)$
is a path in $\mathcal{P}$, and $y$ denotes the first vertex in
$(s=u_{1},u_{2},\ldots,u_{z}=t),1\leq z\leq n$ which is in $P$.
For path $P$ and path $Q\in\mathcal{P}$ we define the many-to-one function
$\alpha:\mathcal{P}\times\mathcal{P}\rightarrow\Pi\cup\\{\texttt{NULL}\\}$ as
follows.

$\alpha(P,Q)=\begin{cases}\texttt{NULL},&\text{if }V(P)\cap V(Q)=\phi\\\
\pi\in\Pi,&\text{ if }y\in V(\pi)\end{cases}$

As a consequence of the definition of $\alpha(P,Q)$ we have the following
lemma.

######  Lemma 18.

For $1\leq i\leq k$, $\alpha(P,Q)=\pi_{i}$ if and only if exactly one of the
following is true.

  1. 1.

$i=1$ and $s\in R_{1}(1)$ and $t\in V(T_{a_{1}})$.

  2. 2.

$s\in R_{2}(i)$

  3. 3.

$s\in R_{3}(i)$ and ${\texttt{lca}}(s,t)\leq b_{i}$

  4. 4.

$s\in R_{4}(i)$ and ${\texttt{lca}}(s,t)<b_{i}$

###### Proof.

Let $\alpha(P,Q)=\pi_{i}$ then the position of the starting node of $Q$ has
three possibilities relative to $\pi_{i}=(a_{i},b_{i})$. They are as follows:

  1. 1.

$s<a_{i}$: This can happen only when $i=1$. By Proposition 14, $a_{1}\in V(Q)$
and $y=a_{1}$. In this case, $s\in R_{1}(1)$ and $t\in V(T_{a_{1}})$. For
$i\neq 1$, any path $Q$ with $l\in R_{1}(i)$ and $t\in T_{a_{i}}$ will have to
pass through $b_{i-1}$. This implies $\alpha(P,Q)\neq\pi_{i}$ and thus a
contradiction.

  2. 2.

$a_{i}\leq s\leq b_{i}$: By Lemma 16, $s=y\in[a_{i},b_{i}]$ that is $s\in
R_{2}(i)$.

  3. 3.

$s>b_{i}$: In this case, $s\neq y$ and $y\in[a_{i},b_{i}]$. Depending on the
regions of $\pi_{i}$ as described above we have two possibilities as shown
below:

    1. (a)

$s\in R_{3}(i)$ and $\texttt{lca}(s,t)\leq b_{i}$. By Proposition 14,
$b_{i}\in V(Q)$ and $y=b_{i}$.

    2. (b)

$s\in R_{4}(i)$ and $\texttt{lca}(s,t)<b_{i}$. In this case,
$y\in[a_{i},b_{i}-1]$.

Exactly one of the conditions is satisfied as the ranges $R_{j}(i)$ are non-
overlapping and paths start in any one of the ranges. On the other hand, if
there exists an $i$ such that any one of the four conditions as given below is
true, then we show that $\alpha(P,Q)=\pi_{i}$.

  1. 1.

$s\in R_{1}(1)$ and $t\in V(T_{a_{1}})$: In this case, $y=a_{1}$ and since
$y\in V(\pi_{1})$, $\alpha(P,Q)=\pi_{1}$.

  2. 2.

$s\in R_{2}(i)$: In this case, $y=s$ and since $y\in V(\pi_{i})$,
$\alpha(P,Q)=\pi_{i}$.

  3. 3.

$s\in R_{3}(i)$ and $\texttt{lca}(s,t)\leq b_{i}$: Since $l\in R_{3}(i)$ and
$\texttt{lca}(l,r)\leq b_{i}$, $y=b_{i}$. Since $y\in V(\pi_{i})$,
$\alpha(P,Q)=\pi_{i}$.

  4. 4.

$s\in R_{4}(i)$ and $\texttt{lca}(s,t)<b_{i}$: Since $s\in R_{4}(i)$ and
$\texttt{lca}(s,t)<b_{i}$, $y\in[a_{i},b_{i}-1]$. Since $y\in V(\pi_{i})$,
$\alpha(P,Q)=\pi_{i}$.

∎

Function check$\alpha$. This is a useful function that returns true if
$\alpha(P,Q)=\pi_{i},\pi_{i}\in\Pi,$ based on conditions of Lemma 18.

######  Lemma 19.

For path $P\in\mathcal{P}$, given as input the index $i$ of a heavy sub-path
$\pi_{i}\in\Pi$, successors of $\pi_{1}\in\Pi$ and another path
$Q\in\mathcal{P}$, there exists a function
${\texttt{check}\alpha(i,Q,\Pi,\texttt{succ}(1,1),\texttt{succ}(1,2))}$ that
checks $\alpha(P,Q)=\pi_{i}$ in constant time.

###### Proof.

The check can be done in the following manner.

  1. 1.

Compute the interval ranges $R_{j},1\leq j\leq 4,$ of $\pi_{i}$ using its end
points and its successor stored in $\Pi$. If $i=1$ then we can get the
successors $\texttt{succ}(1,1)$ and $\texttt{succ}(1,2)$ from the input. If
$i\neq 1$ then it can be obtained from $\Pi$ as follows. For $i\neq 1$, it is
$\pi_{i+1}$ unless $\pi_{i+1}=\texttt{succ}(1,2)$ or $i=k$ where $k$ is the
number of heavy sub-paths in $\Pi$. Since there are only four ranges and from
Lemma 10, rmost_leaf takes constant time, the ranges can be computed in
constant time.

  2. 2.

Check if $\alpha(P,Q)=\pi_{i}$ based on Lemma 18. It takes constant time as
the four checks are based on comparisons and from Lemma 10,
$\texttt{lca}(s,t)$ can be computed in constant time. If $\alpha(P,Q)=\pi_{i}$
then check$\alpha$ returns true.

Thus, check$\alpha$ checks $\alpha(P,Q)=\pi_{i}$ in constant time. ∎

For $\pi\in\Pi$, let $\beta(\pi)=\\{Q\mid Q\in\mathcal{P}\text{ and
}\alpha(P,Q)=\pi\\}$. We have the following lemma.

######  Lemma 20.

For all distinct
$\pi,\pi^{\prime}\in\Pi,\beta(\pi)\cap\beta(\pi^{\prime})=\phi$.

###### Proof.

For each $\pi\in\Pi$, $\beta(\pi)$ is the pre-image of $\pi$ under the
function $\alpha$. Since $\alpha$ is a function, it follows that if
$\pi\neq\pi^{\prime}$, $\beta(\pi)\cap\beta(\pi^{\prime})=\phi$. ∎

Let the neighbourhood of a path be the set of all paths that have non-empty
intersection with it. We have the following theorem regarding neighbourhood.

######  Lemma 21.

Let $N(P)$ denote the neighbourhood of $P$.
$N(P)=\biguplus_{\pi\in\Pi}\beta(\pi)$.

###### Proof.

For a path $Q\in N(P)$, $\alpha(P,Q)\neq NULL$, and thus $Q$ is an element of
$\beta(\pi)$ for some $\pi\in Pi$. By Lemma 20, for each pair of distinct
$\pi,\pi^{\prime}$, $\beta(\pi)\cap\beta(\pi^{\prime})=\phi$. Thus
$N(P)=\biguplus_{\pi\in\Pi}\beta(\pi)$. ∎

##  4 The Succinct Data Structure

In this section, we present the construction of the succinct representation
followed by the implementation of the queries. The input to our construction
procedure is $(T,\mathcal{P})$ obtained from the path graph $G$ using Gavril’s
method [11] where $T$ is the clique tree and
$\mathcal{P}=\\{P_{1},\ldots,P_{n}\\}$ is the set of paths in it such that the
paths correspond to vertices of $G$ and have a non-empty intersection of their
vertex sets if and only if the corresponding vertices are adjacent. The
construction procedure starts by pre-processing the clique tree as explained
in the previous section followed by storing it and the paths in a space
efficient manner. We demonstrate a polynomial time construction mechanism
without worrying about the most optimal way.

Figure 4: Succinct representation for the path graph $G$ of Figure 1. Top left
diagram shows the paths as points in a grid. Bottom left shows the path
aliases stored in the wavelet tree. The right side shows the $l_{i}$ and
$r_{i}$ values of paths, the balanced parentheses representation of the pre-
processed clique tree along with the $F$ and $J$ data structures.

###  4.1 Construction of the Succinct Data Structure

Our succinct data structure for path graphs has two main parts - the clique
tree $T$ and the paths $\mathcal{P}=\\{P_{1},\ldots,P_{n}\\}$ in it. The
construction uses other compact data structures [19] which are of the types:
ordinal tree, bit vector, wavelet tree, and array of sorted integers. In the
next two sections we will explain the construction and storage of the clique
tree and the paths in it.

####  4.1.1 Storing the Clique Tree

In this section we explain how the clique tree $T$ and its BP representation
is stored succinctly.

Clique tree $T$. By Remark 4, the clique tree has at most $n$ nodes and is an
ordinal tree. It is stored using $2n+o(n)$ bits using the data structure of
Lemma 10.

Bit-vector $BP$. The balanced parentheses representation of $T$ is stored
using the data structure of Lemma 11 in bit-vector $BP$ using $2n+o(n)$ bits.
In $BP$ the open and close parenthesis are represented by bit 1 and 0,
respectively. For every node $v$ in $T$ there exists two indices $i$ and $j$
in $BP$ where $i<j$ such that $BP[i]=1$ and $BP[j]=0$. For some $1\leq i\leq
2n$, if $BP[i]=1$ and $BP[i-1]=0$ then they represent the open and close
parenthesis of nodes $v,u\in V(T)$ that have a common parent $w$. Since $T$ is
ordinal, in the order of children of $w$, $u$ comes immediately before $v$ and
it is called $v$’s previous sibling. The following three methods are supported
by $BP$:

  1. 1.

$\texttt{getPreorder}(i)$: For $1\leq i\leq 2n$ such that $BP[i]=1$, returns
the pre-order label of the node which has its open parenthesis at $i$ in $BP$.
It is implemented by $\texttt{rank}(BP,1,i)$ for $i\neq 0$ and for $i=0$ it
returns $1$.

  2. 2.

$\texttt{getIndex}(v)$: Returns the index of the open parenthesis of $v\in
V(T)$ in $BP$. It is implemented by $\texttt{select}(BP,1,v)$.

  3. 3.

$\texttt{getHPStartNode}(v)$: Returns the start node of heavy path $\pi$ that
contains $v\in V(T)$ in constant time. If $v$ is not the first child, that is,
it is adjacent to its parent by a light edge, then $v$ itself is returned else
the method returns
$\texttt{getPreorder}(\texttt{select}(BP,0,\texttt{rank}(BP,0,\texttt{getIndex}(v)))+1)$.

######  Lemma 22.

For $v\in V(T)$, ${\texttt{getHPStartNode}}(v)$ returns in constant time the
starting node of heavy path $\pi$ that contains $v$.

###### Proof.

We need to show that the method getHPStartNode as implemented above indeed
obtains the start node of $\pi$ in constant time. As we use constant time
methods of Lemma 11, getHPStartNode also completes in constant time. To show
that getHPStartNode returns the starting node of $\pi$ we consider the two
cases depending on $v$:

  1. 1.

When $v$ is the root node of $T$ i.e. $v=1$: $\texttt{getIndex}(v)$ returns 1
when $v=1$ and $\texttt{select}(BP,0,\texttt{rank}(BP,0,1))$ returns 0.
Further, getPreorder on input 1 returns 1. Thus, getHPStartNode returns $v$
when input $v$ is the root node, as it is the start node of $\pi$.

  2. 2.

When $v$ is not the root node of $T$ i.e. $v\neq 1$: Let $BP[i]$ be the open
parenthesis of $v$ and $x$ denote the starting node of $\pi$. Also, let
$BP[j]$ be the closing parenthesis of the previous sibling of $x$ in $BP$.
Since $BP[j+1]$ is the open parenthesis of $x$, the length of path from $v$ to
$x$ is $l=i-j-1$. The base case is when $l=0$ that is when $v$ is the starting
node of $\pi$. In this case, getHPStartNode returns $v$ itself. When $l>0$,
$\texttt{getIndex}(v)$ returns the position $i$ of the open parenthesis of $v$
in $BP$. $\texttt{select}(BP,0,\texttt{rank}(BP,0,i))$ returns $j$, the index
of the closing parenthesis of the previous sibling of $x$.
$\texttt{getPreorder}(j+1)$ thus returns the start node of $\pi$ correctly.

∎

####  4.1.2 Storing the Paths $P_{1},\ldots,P_{n}$

To store path $P_{i},1\leq i\leq n$ we need to store its starting node $l_{i}$
and its ending node $r_{i}$ in a space efficient way. Let
$M=(M_{1},\ldots,M_{n})$ and $N=(N_{1},\ldots,N_{n})$ be the sequence of
starting and ending nodes of paths sorted in non-decreasing order,
respectively. For $1\leq i\leq n$, $M[i]$ is the starting node of path
$P_{i}$. On the other hand, for $1\leq i\leq n$, $N[i]$ is the $i-$th ending
node in the non-decreasing sorted order of ending nodes.

Bit-vectors $F$ and $J$. $M$ and $N$ are stored in data structures $F$ and
$J$, respectively, using the data structure of Lemma 12 taking $2n+o(n)$ bits
each.

######  Proposition 23.

For $1\leq i\leq n,{\texttt{accessNS}}(F,i)$ returns $M[i]$ stored in $F$ in
constant time.

######  Proposition 24.

For $1\leq i\leq n,{\texttt{accessNS}}(J,i)$ returns $N[i]$ stored in $J$ in
constant time.

$F$ supports the following useful function too:

  * •

$\texttt{getPathCount}(d)$: Returns the number of paths that start at node
$d\in V(T)$. When $\texttt{select}(F,1,d)$ is well defined and
$F[\texttt{select}(F,1,d)+1]=0$, the count is obtained using the expression
$\texttt{rank}(F,0,\texttt{select}(F,1,d+1))-\texttt{rank}(F,0,\texttt{select}(F,1,d))$.
In all other cases the function returns 0.

######  Lemma 25.

For $x\in V(T)$, method ${\texttt{getPathCount}}(x)$ returns
$|\\{P_{i}:P_{i}\in\mathcal{P},l_{i}=x\\}|$ where $l_{i}$ is the starting node
of path $P_{i}$ in constant time.

###### Proof.

Let input $x\in[n]$ be a valid $l_{i}$ value of some path in $\mathcal{P}$,
that is, $\texttt{select}(F,1,d)$ is well defined and
$F[\texttt{select}(F,1,d)+1]=0$. If the $l_{i}$ value $x$ is repeating in $F$
then there will be a contiguous sequence of two or more 0’s between the $x$-th
1 and the $x+1-$th 1. Let $n_{1}$ be the number of 0’s before the $x+1-$st 1.
It can be obtained using the expression
$\texttt{rank}(F,0,\texttt{select}(F,1,d+1))$. Let $n_{2}$ be the number of
0’s before the $x-$th 1. $n_{2}$ can be obtained using the expression
$\texttt{rank}(F,0,\texttt{select}(F,1,d))$. The number of times $x$ is
repeating is $n_{1}-n_{2}$. As per Lemma 11 all these operations can be done
in constant time. ∎

Next, we need to associate the path $P_{i}$ with its starting and ending nodes
stored in $F$ and $J$. Starting node of $P_{i}$ is available directly from $F$
using $\texttt{accessNS}(F,i)$ whereas to get the ending node we need to
associate it with its ending node’s position in $J$. This association is
established using a wavelet tree as described below.

Wavelet tree $S$. For each path $P_{i},1\leq i\leq n$ we assign the tuple
$(f_{i},j_{i})$ where $f_{i}$ and $j_{i}$ are indices of the $l_{i}$ and
$r_{i}$ values in $M$ and $N$ respectively. Since paths are numbered based on
the non-decreasing order of their starting nodes, $i=f_{i}$. In other words,
$(f_{i},j_{i})$ acts as an alias for path $P_{i}=(l_{i},r_{i})$ and they have
the following property.

######  Lemma 26.

Let $\mathcal{P}^{\prime}=\\{(f_{1},j_{1}),\ldots,(f_{n},j_{n})\\}$ be the set
of aliases of paths in $\mathcal{P}$. The following are true:

  1. 1.

$1\leq k\neq l\leq n,f_{k}\neq f_{l}$ and $j_{k}\neq j_{l}$

  2. 2.

$\mathcal{P}^{\prime}$ can be stored using the wavelet tree $S$ using $n\log
n+o(n\log n)$ bits of space such that $S$ supports the following method:

    1. (a)

${\texttt{accessWT}}(S,i)$: For $i\in[n]$, returns $j_{i}$ in $O(\log n)$ time
where $N[j_{i}]$ is the ending node of path $P_{i}$.

    2. (b)

${\texttt{searchWT}}(S,[i_{1},i_{2}],[j_{1},j_{2}])$: For
$i_{1},i_{2},j_{1},j_{2}\in[n]$, returns $\\{i\mid
P_{i}\in\mathcal{P}^{\prime},f_{i}\in[i_{1},i_{2}]\text{ and
}j_{i}\in[j_{1},j_{2}]\\}$ in $O(\log n)$ time per path.

    3. (c)

${\texttt{countWT}}(S,[i_{1},i_{2}],[j_{1},j_{2}])$: For
$i_{1},i_{2},j_{1},j_{2}\in[n]$, returns $\mid\\{i\mid
P_{i}\in\mathcal{P}^{\prime},f_{i}\in[i_{1},i_{2}]\text{ and
}j_{i}\in[j_{1},j_{2}]\\}\mid$ in $O(\log n)$ time.

###### Proof.

The proof is as follows:

  1. 1.

$P_{i},1\leq i\leq n$ has its starting and ending nodes stored at unique
indices $f_{i}$ and $j_{i}$ in $M$ and $N$, respectively. This ensures that
for $1\leq k\neq l\leq n,f_{k}\neq f_{l}$ and $j_{k}\neq j_{l}$.

  2. 2.

For path $P_{i},1\leq i\leq n$, the wavelet tree of Lemma 13 stores
$(f_{i},j_{i})$, where $M[i]$ and $N[j_{i}]$ are the starting and ending nodes
of $P_{i}$. accessWT, searchWT, and countWT functions can be directly
delegated to the access, search, and count functions of the wavelet tree of
Lemma 13. The time complexities also follow from Lemma 13.

∎

Function pathep. Given a path index $i,1\leq i\leq n,$ we can now obtain its
$l_{i}$ and $r_{i}$ values using the method pathep. The method takes $i$ as
input and returns $(l_{i},r_{i})$ in $O(\log n)$ time as follows.

  1. 1.

$l_{i}=\texttt{accessNS}(F,i)$.

  2. 2.

$r_{i}=\texttt{accessNS}(J,\texttt{accessWT}(S,i))$.

######  Lemma 27.

For $1\leq i\leq n$, ${\texttt{pathep}}(i)$ returns $(l_{i},r_{i})$ of $P_{i}$
in $O(\log n)$ time.

###### Proof.

First we show that $\texttt{pathep}(i)$ returns the $l_{i}$ value of path $i$
correctly. The $l_{i}$ value of $i$ is the number of 1’s before the $i-$th 0
in $F$ which is obtained by $\texttt{accessNS}(F,i)$. Now, we show that the
correct $r_{i}$ value is returned by $\texttt{pathep}(i)$. To get the $r_{i}$
value which is stored in $J$ we have to get the index $j$ of path $i$ in $J$.
This can be obtained by querying $S$. We obtain the $r_{i}$ value from $J$ by
$\texttt{accessNS}(J,\texttt{accessWT}(S,i))$. Since accessNS takes constant
time as per Lemma 12 and accessWT takes $O(\log n)$ time as per Lemma 26, the
total time taken is $O(\log n)$ time. ∎

Function $\texttt{maprange}^{F}$/$\texttt{maprange}^{J}$. Given range
$[l,l^{\prime}]$ of starting nodes of paths as input, $\texttt{maprange}^{F}$
outputs the range $[j,j^{\prime}]$ where $j$ is the first index in $M$ such
that $M[j]\geq l$ and $j^{\prime}$ is the last index in $M$ such that
$M[j^{\prime}]\leq l^{\prime}$.

  1. 1.

$j$ is obtained using the expression
$\texttt{rank}(F,0,\texttt{select}(F,1,l))+1$ that returns the index in $M$ of
the first occurrence of $l$ or a value greater than $l$ but less than or equal
to $l^{\prime}$.

  2. 2.

To obtain $j^{\prime}$ we use the following steps:

    1. (a)

If $M[\texttt{rank}(F,1,\texttt{select}(F,1,l^{\prime})+1)]=l^{\prime}$ then
return
$\texttt{rank}(F,0,\texttt{select}(F,1,l^{\prime})+1)+\texttt{getPathCount}(l^{\prime})-1$.
In other words, if $l^{\prime}$ is present in $M$ then $j^{\prime}$ is the
index of the last $l^{\prime}$ in $M$. To account for the repeating
$l^{\prime}$ we add to the the first occurrence of $l^{\prime}$ in $M$ one
less than the number of times the $l^{\prime}$ value repeats.

    2. (b)

If $M[\texttt{rank}(F,1,\texttt{select}(F,1,l^{\prime})+1)]\neq l^{\prime}$
then return
$\texttt{rank}(F,0,\texttt{select}(F,1,l^{\prime}))$. If $l^{\prime}$ is not
present then $M[j^{\prime}]$ is a value that is less than $l^{\prime}$ but
greater than or equal to $l$.

$M[z],z\in[n]$ can be obtained using $\texttt{accessNS}(F,z)$.

######  Lemma 28.

Given a range $[l,l^{\prime}]$ of starting nodes where $l,l^{\prime}\in[n]$,
${\texttt{maprange}^{F}}(l,l^{\prime})$ returns the range $[j,j^{\prime}]$ in
constant time where $j$ and $j^{\prime}$ are the smallest and largest indices
in $M$ such that $M[j]\geq l$ and $M[j^{\prime}]\leq l^{\prime}$.

###### Proof.

First we will show that $j$ is computed correctly by the expression
$\texttt{rank}(F,0,\texttt{select}(F,1,l))+1$. In the unary encoding in $F$,
$\texttt{select}(F,1,l)$ identifies the position $i$ of the $l-$th 1. If $l$
is present in $F$ then $F[i+1]$ is a 0 else its a 1. If $F[i+1]=0$ then
$\texttt{rank}(F,0,i)+1$ returns the index $j$ of $l$ in $M$. On the other
hand, if $F[i+1]=1$ then let $k$ be the smallest number such that $F[i+k]=0$.
In this case, $\texttt{rank}(F,0,i)+1$ returns the smallest index $j$ in $M$
of $l^{\prime\prime}>l$. Next, we show that $j^{\prime}$ is returned
correctly. If $l^{\prime}$ is present in $M$ then
$\texttt{rank}(F,0,\texttt{select}(F,1,l^{\prime})+1)$ returns the index
$j^{\prime\prime}$ of the first $l^{\prime}$ in $M$. The largest index in $M$
of $l^{\prime}$ is obtained by adding $\texttt{getPathCount}(l^{\prime})-1$ to
$j^{\prime\prime}$. On the other hand, if $l^{\prime}$ is not in $M$ then
$\texttt{rank}(F,0,\texttt{select}(F,1,l^{\prime}))$ returns the largest index
$j$ in $M$ of $l^{\prime\prime}<l^{\prime}$. By Lemma 11, rank and select can
be completed in constant time. Also, by Lemma 12, accessNS takes constant
time. Thus, $\texttt{maprange}^{F}$ completes in constant time. ∎

We have a similar function, $\texttt{maprange}^{J}$ for mapping the range
$[r,r^{\prime}]$ of ending nodes of paths to range $[j,j^{\prime}]$ such that
$j$ is the smallest index in $N$ such that $N[j]\geq r$ and $j^{\prime}$ is
the largest index in $N$ such that $N[j^{\prime}]\leq r^{\prime}$.

######  Lemma 29.

Given a range $[r,r^{\prime}]$ of ending nodes where $r,r^{\prime}\in[n]$,
${\texttt{maprange}^{J}}(r,r^{\prime})$ returns the range $[j,j^{\prime}]$ in
constant time where $j$ and $j^{\prime}$ are the smallest and largest indices
in $N$ such that $N[j]\geq r$ and $N[j^{\prime}]\leq r^{\prime}$.

Bit-vector D. Bit vector $D$ of size $n$ stores for each path a 1 if the path
intersects with more than $\log n$ other paths else a 0. It supports the
following function.

  * •

$\texttt{isLargeDegree}(i)$: Returns true if $D[i]=1$ else false in constant
time.

######  Lemma 30.

There exists an $n\log n+o(n\log n)$-bit succinct data structure for path
graphs.

###### Proof.

The space taken by the components of the succinct data structure for path
graphs are as follows:

  1. 1.

The clique tree $T$ and its $BP$ representation takes $O(n)$ bits of space.
This follows from Lemma 10 and 11.

  2. 2.

To store the end points of paths in $\mathcal{P}$ we have bit vectors $F$,
$J$. From Lemma 12 this also takes $O(n)$ bits.

  3. 3.

The wavelet tree stores the indices of paths in $M$ and $N$ and from Lemma 26
takes $n\log n+o(n\log n)$ bits.

  4. 4.

To improve the degree query we have the $n$ bit vector $D$.

The space complexity of the succinct representation is dominated by the space
required for wavelet tree $S$. Thus, our representation takes $n\log n+o(n\log
n)$ bits. This representation is succinct as it uses the permitted storage for
succinct representation of interval graphs [4] that is a proper sub-class of
path graphs [3]. ∎

###  4.2 Adjacency and Neighbourhood Queries

In this section, we will present efficient implementations of adjacency and
neighbourhood queries using the succinct representation as constructed in
Section 4.1. In this section, as a consequence of Lemma 30, the succinct
representation for path graph $G$ is denote as $(T,\mathcal{P})$. Adjacency
query, as will be shown in Lemma 33, takes two path indices $i,j\in[n]$ and
the succinct representation $(T,\mathcal{P})$ as input and returns true if the
paths $P_{i}$ and $P_{j}$ have a non-empty intersection. The neighbourhood
query, as will be shown in Lemma 34, takes a single path index $i\in[n]$ and
the succinct representation $(T,\mathcal{P})$ as input and returns the list of
paths that have non-empty intersection with of the path $P_{i}$. The
implementation of the queries depend on the following:

  1. 1.

Computing paths $P=(l,r)$ and $Q=(s,t)$ corresponding to $i$ and $j$,
respectively using pathep and $p=\texttt{lca}(l,r)$ in $O(\log n)$ time.

  2. 2.

Computing $\Pi,k,\texttt{succ}(1,1)$ and $\texttt{succ}(1,2)$. From Lemma 31
that follows, Algorithm 1 can do this in $O(\log n)$ time.

  3. 3.

Computing $\beta(\pi)$ for $\pi\in\Pi$. From Lemma 32 that follows,
$\beta(\pi)$ can be computed in $O(d\log n)$ time where $d$ is the number of
paths returned by $\beta(\pi)$.

1 Function  _compute $\Pi$(_$l,r$_)_:

2 $p\leftarrow\texttt{lca}(l,r)$

3 $k\leftarrow 0$

4 $\Pi=\Pi^{\prime}=\texttt{succ}(1,1)=\texttt{succ}(1,2)=\texttt{NULL}$

5 if  _ $l\neq p$_ then

6 compute$\Pi$_Helper(_$p,l,\Pi,k$_)

7 compute$\Pi$_Helper(_$p,r,\Pi^{\prime},k$_)

8 Add second entries of $\Pi$ and $\Pi^{\prime}$ as $\texttt{succ}(1,1)$ and
$\texttt{succ}(1,2)$ respectively

9 Concatenate $\Pi^{\prime}$ to $\Pi$ preserving the order $\prec$

10

11 else

12 compute$\Pi$_Helper(_$l,r,\Pi,k$_)

13 if  _first entry in $\Pi$ has equal starting and ending nodes_ then

14 If starting node of the first entry in $\Pi$ is the parent of starting node
of the second entry then $\texttt{succ}(1,1)$ is the second entry in $\Pi$ and
$\texttt{succ}(1,2)=\texttt{NULL}$

15

16 else

17 If ending node of the first entry in $\Pi$ is the parent of the starting
node of the second entry then $\texttt{succ}(1,1)$ is the second entry in
$\Pi$ and $\texttt{succ}(1,2)=\texttt{NULL}$

18

19

20

21Function  _compute $\Pi$_Helper(_$l,r,\Pi,k$_)_:

22 if  _$l >r$_ then

23 return

24

25 $p=l$

26 $u\leftarrow\texttt{getHPStartNode}(r)$

27

28 Increment $k$

29 if  _$u >=p$_ then

30 Add $(u,r)$ to beginning of $\Pi$

31 compute$\Pi$_Helper(_$p,\texttt{parent}(u),\Pi,k$_)

32

33 else

34 Add $(p,r)$ to beginning of $\Pi$

35

36

Algorithm 1 Given path $P=(l,r)$ as input, function $\texttt{compute}\Pi$
computes $\Pi$, $k$, $\texttt{succ}(1,1)$, and $\texttt{succ}(1,2)$. We assume
that $\texttt{parent}(v)=0$ when $v$ is the root of the tree.

######  Lemma 31.

Given a path $P=(l,r)$, ${\texttt{compute$\Pi$}}(l,r)$ computes $\Pi$, $k$,
${\texttt{succ}}(1,1)$, and ${\texttt{succ}}(1,2)$ for it in $O(\log n)$ time.

###### Proof.

First we show that $\texttt{compute}\Pi$ of Algorithm 1 computes the heavy
sub-paths of $P$ as in Lemma 8. Function $\texttt{compute}\Pi$ depends on the
function compute$\Pi$_Helper to compute the heavy sub-paths. Paths are of two
types depending on whether the lca is same as its starting node. Based on this
distinction different steps are executed in the function
$\texttt{compute}\Pi$; see Line 5 of Algorithm 1.

  1. 1.

Type 1 paths: If lca of $P$ is not equal to $l$ then the heavy sub-paths that
comprise the sub-path from $p$ to $l$ are computed first. This is followed by
computing the heavy sub-paths that comprise the sub-path from $p$ to $r$. This
is done using the function compute$\Pi$_Helper as shown in Line 6 and 7 of
Algorithm 1. compute$\Pi$_Helper$(p,l,\Pi,k)$ computes the heavy sub-paths
recursively till $\pi_{1}$; see Line 6 of Algorithm 1. Starting at $l$, the
starting node of the heavy sub-path to which it belongs is obtained by using
getHPStartNode; see Line 21 of Algorithm 1. The set of heavy sub-paths are
computed in this manner till $p$ is reached; see Line 23 to 25 of Algorithm 1.
Similar steps are performed for compute$\Pi$_Helper$(p,r,\Pi,k)$; see Line 7
of Algorithm 1. This gives us the end points of the heavy sub-paths of $P$.

  2. 2.

Type 2 paths: If lca of $P$ is equal to $l$ then the heavy sub-paths
comprising the only sub-path from $l=p$ to $r$ is computed using the function
compute$\Pi$_Helper as shown in Line 11 of Algorithm 1. Heavy sub-paths for
type 1 paths are also computed just as heavy sub-paths for type 1; see Line 11
to 15 in Algorithm 1.

It takes $O(\log n)$ time to compute heavy sub-paths as there are $O(\log n)$
light edges (or heavy sub-paths) as per Lemma 8 and as per Lemma 22,
getHPStartNode takes constant time. From Lemma 10, lca and parent also take
constant time. Since function $\texttt{compute}\Pi$ calls compute$\Pi$_Helper
only a constant number of times, the complexity of the $\texttt{compute}\Pi$
function is also $O(\log n)$. ∎

From Lemma 21, we know that the neighbourhood query depends on computing
$\beta(\pi)$ for all $\pi\in\Pi$. Next, we show that $\beta(\pi)$ can be
computed in $O(d_{\pi}\log n)$ time where $d_{\pi}$ is
$|\beta(\pi)=\\{Q|Q\in\mathcal{P}\text{ and }\alpha(P,Q)=\pi\\}|$. By an abuse
of terminology, $d_{\pi}$ is called the degree of $\pi$.

######  Lemma 32.

Given index $i$ of $\pi_{i}\in\Pi$, there exists a function
${\texttt{compute}\beta(i,\Pi,\texttt{succ}(1,1),\texttt{succ}(1,2))}$ that
returns $\beta(\pi_{i})=\\{Q|Q\in\mathcal{P}\text{ and
}\alpha(P,Q)=\pi_{i}\\}$ in $O(d_{\pi_{i}}\log n)$ time where $d_{\pi_{i}}$ is
the degree of $\pi_{i}$.

###### Proof.

First we will show that there exists a function
$\texttt{compute}\beta(i,\Pi,\texttt{succ}(1,1),\texttt{succ}(1,2))$ that
computes $\beta(\pi_{i})$ correctly. The high level steps of function
$\texttt{compute}\beta$ are as follows.

  1. 1.

Compute the interval ranges $R_{j},1\leq j\leq 4,$ of $\pi_{i}$ using its end
points and its successor stored in $\Pi$. If $i=1$ then the successors are
directly available in the input else it can be obtained from $\Pi$ as follows.
For $i\neq 1$, it is $\pi_{i+1}$ unless $\pi_{i+1}=\texttt{succ}(1,2)$ or
$i=k$ where $k$ is the number of heavy sub-paths in $\Pi$.

  2. 2.

The next step is to identify all $Q\in\mathcal{P}$ that satisfy
$\alpha(P,Q)=\pi_{i}$. The ranges of starting and ending nodes of such paths
can be obtained from the conditions of Lemma 18. Using these ranges the paths
can be retrieved by issuing orthogonal range search queries on wavelet tree
$S$ of Lemma 26. The ranges corresponding to first two conditions of Lemma 18
can be directly obtained. For the last two conditions we use Lemma 17.

  3. 3.

searchWT from Lemma 26 is used to perform the orthogonal range search on
wavelet tree $S$.

As there are only four interval ranges for $\pi_{i}$ and from Lemma 10,
rmost_leaf takes constant time, the interval ranges of $\pi_{i}$ can be
computed in constant time. From these interval ranges the ranges for
orthogonal range search can be obtained using Lemma 18. This can be done in
constant time as from Lemma 10, lca takes constant time. searchWT takes
$O(d\log n)$ time per range query where $d$ is the number of paths in
$\mathcal{P}$ with starting and ending nodes in the input range. There is no
over counting of paths between range search queries as no path satisfies more
than one condition due to Lemma 18. Since there are only four orthogonal range
queries to be issued for any heavy sub-path, $\texttt{compute}\beta$ completes
in $O(d_{\pi_{i}}\log n)$ time. ∎

Adjacency query in $O(\log n)$ time. Given indices of paths $i,j\in[n]$ and
$(T,\mathcal{P})$ as input, adjacency query returns true if paths
corresponding to $i$ and $j$, namely $P$ and $Q$, have a non-empty
intersection in $T$. Adjacency of paths with indices $i$ and $j$ can be
checked as shown in Algorithm 2. We have the following lemma.

1

2 Function  _adjacency(_$i,j$_)_:

3 Obtain paths $P=\texttt{pathep}(i)$ and $Q=\texttt{pathep}(j)$. Let
$P=(l,r)$ and $Q=(s,t)$.

4 Initialize $k\leftarrow 0$ and $\Pi$ to empty

5
$(\Pi,k,\texttt{succ}(1,1),\texttt{succ}(1,2))\leftarrow\texttt{compute}\Pi(l,r)$

6 For each $1\leq i\leq k$ return true if
$\texttt{check}\alpha(i,Q,\Pi,\texttt{succ}(1,1),\texttt{succ}(1,2))$ of Lemma
19 returns true

7

Algorithm 2 Given two path indices $i,j\in[n]$, the function adjacency checks
if the paths corresponding to them have a non-empty intersection.

######  Lemma 33.

Given two path indices $i,j\in[n]$ and $(T,\mathcal{P})$ as input, the
function ${\texttt{adjacency}(i,j)}$ checks if paths corresponding to $i$ and
$j$ have a non-empty intersection in $O(\log n)$ time.

###### Proof.

By definition, if $\alpha(P,Q)=\pi$ for $\pi\in\Pi$ then $Q$ and $P$ are
adjacent. The existence of such a heavy sub-path can be tested as shown in
Line 5 of Algorithm 2. Paths $P=(l,r)$ and $Q=(s,t)$ corresponding to $i$ and
$j$, respectively, can be obtained in $O(\log n)$ time using pathep due to
Lemma 27. By Lemma 31, $\Pi,k,$ and the successors of $\pi_{1}$ can be
computed in $O(\log n)$ time. For each heavy sub-path $\pi\in\Pi$, the
conditions of Lemma 18 can be checked in constant time using
$\texttt{check}\alpha$ of Lemma 19. Also, from Lemma 10, rmost_leaf can be
computed in constant time. Since by Lemma 8$,\Pi$ contains at most $O(\log n)$
heavy sub-paths, the total time taken is $O(\log n)$. ∎

Neighbourhood query. Given a path index $i\in[n]$ and $(T,\mathcal{P})$, the
neighbourhood query returns the neighbours of path $P$ corresponding to index
$i$; see Lemma 21 for definition of neighbours of a path. Let $N(P)$ be
initialized to empty. $N(P)$ can be obtained as shown in Algorithm 3. We call
$|N(P)|$ the degree of $P$. We have the following lemma.

1

2 Function  _neighbourhood(_$i$_)_:

3 Obtain end points $(l,r)$ of $P$ using $\texttt{pathep}(i)$

4 Initialize $k\leftarrow 0$ and $\Pi$ to empty

5 Compute $(\Pi,k,\texttt{succ}(1,1),\texttt{succ}(1,2))$ for $P$ using the
$\texttt{compute}\Pi(l,r)$ function

6 For each $\pi\in\Pi$ add $\texttt{compute}\beta(\pi)$ of Lemma 32 to $N(P)$.

Algorithm 3 Given path index $i$, the function neighbourhood enumerates the
paths that have non-empty intersection with $P$.

######  Lemma 34.

Given path index $i\in[n]$ of path $P\in\mathcal{P}$ and $(T,\mathcal{P})$ as
input, the function ${\texttt{neighbourhood}}(i)$ returns the set of
neighbours of $P$ in $O(d_{P}\log n)$ time where $d_{P}$ is the degree of $P$.

###### Proof.

From Lemma 21, the neighbours of $P$ are the paths in
$\biguplus\limits_{i=1}^{k}\beta(\pi_{i})$. The end points of $P$ can be
obtained in $O(\log n)$ time using pathep due to Lemma 27. From Lemma 31, we
know that compute$\Pi$ takes $O(\log n)$ time and from Lemma 32, we know that
$\texttt{compute}\beta$ takes $O(d_{\pi}\log n)$ time for each $\pi\in\Pi$
where $d_{\pi}$ is the number of paths that $\alpha$ maps to $\pi$. The time
taken by neighbourhood is sum of the time taken by $\texttt{pathep},$
$\texttt{compute}\Pi$ and at most $k$ iterations of $\texttt{compute}\beta$.
Since by Lemma 21, we know that none of the neighbours are over-counted the
total time taken is $O(d_{P}\log n)$ where
$d_{P}=\sum\limits_{i=1}^{k}d_{\pi_{i}}$ where $d_{P}$ is the degree of path
$P$. ∎

Degree query. Degree of path $P$ can be obtained by two different methods
depending on the degree of the path. We use a bit vector $D$ as described in
Section 4.1. We have two methods for computing degree of $P$ with index $i$
depending on $\texttt{isLargeDegree}(i)$.

  1. 1.

$\texttt{isLargeDegree}(i)$ is true: We modify Algorithm 3 for neighbourhood
to return the count of the orthogonal range search instead of the paths by
using countWT of Lemma 26 instead of searchWT.

  2. 2.

$\texttt{isLargeDegree}(i)$ is false: We run the Algorithm 3 for neighbourhood
without modification and count the number of paths returned.

######  Lemma 35.

Given path index $i\in[n]$ of path $P\in\mathcal{P}$ and $(T,\mathcal{P})$ as
input, the function ${\texttt{degree}}(i)$ returns the degree of $P$ in
$\min\\{O(\log^{2}n),O(d_{P}\log n)\\}$ time where $d_{P}$ is the degree of
$P$.

###### Proof.

As described above, two different methods are used depending on whether
$\texttt{isLargeDegree}(i)$ is true or not. Thus, we have the following two
cases:

  1. 1.

$\texttt{isLargeDegree}(i)$ is true: countWT of Lemma 26 takes $O(\log n)$
time. Since there are $O(\log n)$ heavy sub-paths as per Lemma 8, the total
time is $O(\log^{2}n)$.

  2. 2.

$\texttt{isLargeDegree}(i)$ is false: By Lemma 34, Algorithm 3 takes
$O(d_{P}\log n)$ time. Thus, degree also takes $O(d_{P}\log n)$ time.

Since we run only one of the two depending on which is better, the time taken
by degree query is $\min\\{O(\log^{2}n),O(d_{P}\log n)\\}$. ∎

###### Proof of Theorem 1.

Lemma 30 shows that there exists a succinct representation for path graphs
that takes $n\log n+o(n\log n)$ bits. Given this representation as input,
Lemma 33 shows that adjacency between vertices can be checked in $O(\log n)$
time. Similarly, given this representation as input Lemma 34 and 35 show that
for vertex $u\in V(G)$ with degree $d_{u}$, neighbourhood and degree queries
are supported in $O(d_{u}\log n)$ and $\min\\{O(\log^{2}n),O(d_{u}\log n)\\}$
time, respectively. Hence, Theorem 1. ∎

##  5 The Space-Efficient Data Structure

We present an $O(n\log^{2}n)$-bit space-efficient representation for path
graphs that supports faster adjacency and degree queries in comparison to the
succinct representation presented in Section 4. The approach we take is to
represent a path graph using the succinct data structure for interval graphs
due to Acan et al. [4]. To represent the path graph using the interval graph
representation in [4] we end up having multiple copies of each vertex, and the
adjacency between vertices could be witnessed in different interval graphs in
our transformation. Our data structure stores these interval graphs using the
representation of [4], along with an additional table to keep track of the
copies of the vertices and edges. This transformation has an interesting
contrast to the succinct data structure in Section 4; there the path graph is
represented using the clique tree and the adjacency queries are transformed to
range queries.

The path graph $G$ is presented as $(T,\mathcal{P})$, where $T$ is a clique
tree of $G$ and $\mathcal{P}=\\{P_{1},\ldots,P_{n}\\}$ is the set of paths in
$T$. Consider the heavy path tree $\mathcal{T}$ of $T$. Let $\mathcal{H}$
denote the set of heavy paths of $T$.
Convention: Let $M$ denote $|V(T)|$. It follows from Remark 4 that $M$ and
$|\mathcal{H}|$ are at most $n$. $P_{v}$ denotes the path in $\mathcal{P}$
corresponding to vertex $v\in V(G)$. For a node $w\in\mathcal{T}$, we use
$H_{w}$ to denote the heavy path in $T$ associated with the node $w$. The
level number of a node in ${\cal T}$ is one more than the number of edges on
the path to it from the root; thus the level number of the root is 1. $K$
denotes the number of levels in $\mathcal{T}$ and level $l$ consists of the
heavy paths which are at that level in ${\cal T}$. From Lemma 6, $\mathcal{T}$
has at most $\lceil\log n\rceil$ levels and each path $P$ in $\mathcal{T}$ has
at most $2\lceil\log n\rceil$ edges.

######  Lemma 36.

For any $P,Q\in\mathcal{P}$, there exists a node $v$ in $\mathcal{T}$ such
that $\Phi^{-1}(v)$ has a non-empty intersection with the path $P\cap Q$.

###### Proof.

From Lemma 7, we know that nodes of $T$ are partitioned among the nodes of
$\mathcal{T}$. This implies nodes of $P\cap Q$ belong to some $v\in
V(\mathcal{T})$. Thus, for some $v\in V(\mathcal{T})$, $\Phi^{-1}(v)$
intersects with the path $P\cap Q$. ∎

######  Lemma 37.

For $u$ and $v$ in $V(G)$, $P_{u}$ and $P_{v}$ have a non-empty intersection
in $T$ if and only if one of the following is true:

  1. 1.

there is a light edge $\\{w,w^{\prime}\\}$ in $\mathcal{T}$ such that $P_{u}$
and $P_{v}$ both intersect $H_{w}$ and $H_{w^{\prime}}$

  2. 2.

there is exactly a node $w$ in $\mathcal{T}$ such that $P_{u}\cap H_{w}$ and
$P_{v}\cap H_{w}$ have a non-empty intersection.

###### Proof.

If $V(P_{u})\cap V(P_{v})\neq\phi$ then there are two possibilities:

  1. 1.

there exist $t_{1},t_{2}\in V(P_{u})\cap V(P_{v})$ and $t_{1}\in V(H_{w})$ and
$t_{2}\in V(H_{w^{\prime}})$ such that there exists a light edge
$\\{w,w^{\prime}\\}$ in $\mathcal{T}$.

  2. 2.

there exists only one $H_{w}\in\mathcal{H}$ that contains all nodes in
$V(P_{u})\cap V(P_{v})$ for some $w\in V(\mathcal{T})$. In this case,
$P_{u}\cap H_{w}$ and $P_{v}\cap H_{w}$ have a non-empty intersection.

Conversely, if $P_{u}$ and $P_{v}$ both intersect heavy paths $H_{w}$ and
$H_{w^{\prime}}$ where $w,w^{\prime}\in V(\mathcal{T})$ then $P_{u}$ and
$P_{v}$ share the light edge $\\{w,w^{\prime}\\}$. Thus, they intersect in
$T$. If $P_{u}\cap H_{w}$ and $P_{v}\cap H_{w}$ intersect then by definition
$P_{u}$ and $P_{v}$ intersect in $T$. ∎

Interval graph associated with heavy path $H$. For a heavy path $H$ associated
with a node in $\mathcal{T}$ of level number $l$, $G_{H}$ is a graph whose
vertices are defined as follows: for each $1\leq i\leq n$, if $P_{i}\cap
H\neq\phi$ then there is a vertex corresponding to $P_{i}\cap H$ in
$V(G_{H})$. Two vertices are adjacent in $G_{H}$ if the corresponding paths
have a non-empty intersection, otherwise they are not adjacent.

######  Lemma 38.

Let $H\in\mathcal{H}$. Then $G_{H}$ is an interval graph.

###### Proof.

The vertices of $G_{H}$ correspond to paths in $\mathcal{P}$ that have non-
empty intersection with $H$. Thus, it follows that each vertex of $G_{H}$
corresponds to a sub-path of $H$, which is equivalently an interval in the set
$\\{1,2,\ldots,|V(H)|\\}$. Thus, $G_{H}$ is an interval graph. ∎

######  Lemma 39.

Let $P_{u}$ and $P_{v}$ be paths in $T$. $P_{u}\cap P_{v}\neq\phi$ if and only
if there exist a heavy path $H\in{\cal T}$ such that in the interval graph
$G_{H}$, the vertices corresponding to $P_{u}\cap H$ and $P_{v}\cap H$ are
adjacent.

###### Proof.

The proof follows directly from Lemma 37. ∎

It follows from the above lemma that each edge in $G$ has a representative in
the interval graph associated with at least one of the heavy paths in ${\cal
T}$. Thus, it is natural to group all the interval graphs into the levels
associated with the heavy paths in ${\cal T}$.
Interval graph associated with a level $l$ in ${\cal T}$. Let $S_{l}$ be the
set of nodes in $\mathcal{T}$ at level $l$. For each $l$, define
$U_{l}=\\{G_{H_{w}}\mid w\in S_{l}\\}$. In other words, $U_{l}$ is the
collection of interval graphs associated with each heavy path at level $l$.
Thus, the vertex set and edge set of $U_{l}$ is the union of vertex sets and
edge sets of $G_{H_{w}}$ for all $w\in S_{l}$. Clearly, $U_{l}$ is an interval
graph. We next show that the number of vertices in $U_{l}$ is at most twice
the number of vertices in $G$, that is, at most twice the number of paths in
${\cal P}$.

######  Lemma 40.

Let $P_{v}$ be a path in ${\cal P}$ and $l$ be a level number in ${\cal T}$.
There exists at most two nodes $w$ and $w^{\prime}$ at level $l$ of
$\mathcal{T}$ such that $G_{H_{w}}$ and $G_{H_{w^{\prime}}}$ have a vertex
each corresponding to the paths $P_{v}\cap H_{w}$ and $P_{v}\cap
H_{w^{\prime}}$. Therefore, the number of vertices in the interval graph
$U_{l}$ is at most $2n$.

###### Proof.

We know from Lemma 8 that the nodes of $P_{v}$ are partitioned into heavy sub-
paths, each of which is contained in a heavy path. Since each heavy path
corresponds to a node in ${\cal T}$, it follows that $P_{v}$ naturally defines
a path $P$ in ${\cal T}$. From Proposition 9, it follows that $P$ has at most
two nodes in level $l$. Thus, for each level $l$, $P_{v}$ has a non-empty
intersection with at most two heavy paths whose nodes are at level $l$ in
${\cal T}$. Consequently, $U_{l}$ has at most $2n$ vertices. ∎

In Section 5.1, we present the data structure to store the set of interval
graphs $\\{U_{l}\mid 1\leq l\leq K\\}$ and additional tables to respond to the
adjacency and neighborhood queries.

###  5.1 Construction of the Space Efficient Data Structure

The main goal of this section is to prove the space complexity part of Theorem
2. Given the $(T,\mathcal{P})$ representation for a path graph $G$ with $n$
vertices, the space-efficient data structure is constructed by the following
steps:

  1. 1.

Compute the heavy path decomposition of clique tree $T$ and the heavy path
tree $\mathcal{T}$ from $T$ as guaranteed in Section 2.2.

  2. 2.

Construct the ordinal clique tree $T$ as explained in Section 3.

  3. 3.

Store the set of interval graphs $\\{U_{l}\mid 1\leq l\leq K\\}$ using [4] and
a table called PIT that stores, for every level $1\leq l\leq K$, the labels of
vertices in $G_{l}$ corresponding to paths in $\mathcal{P}$; by Lemma 40 there
are two labels per path at a level $l$.

The construction of the data structure takes polynomial time and
implementation details are left out. The components of the space-efficient
representation are as follows.

Array, $F$. This is a one dimensional array of length $M$. $F[a]=i$ where $i$
is the index, in $\prec_{{\cal H}}$, of the heavy path which contains $a\in
V(T)$. So to store the heavy paths to which all nodes of $T$ belong we need
$O(n\log n)$ bits. The following function is supported by $F$.

  * •

$\texttt{getHeavyPath}(a)$: Returns the heavy path number of $H\in\mathcal{H}$
to which $a\in V(T)$ belongs in constant time.

Array, $L$. This is a one dimensional array of length $|\mathcal{H}|$.
$L[i]=l$ where $l$ is the level in $\mathcal{T}$ to which heavy path
$H_{i}\in\mathcal{H}$ belongs. Each entry in the array uses $O(\log\log n)$
bits, since from Lemma 6, there are $O(\log n)$ levels in $\mathcal{T}$. Since
$|\mathcal{H}|\leq n$, the total space taken by $L$ is $O(n\log\log n)$ bits.
The following function is supported.

  * •

$\texttt{getLevel}(j)$: Returns in constant time the level to which heavy path
$H_{j}\in\mathcal{H}$, for $j\in[n]$, belongs in $\mathcal{T}$.

Array, $E$. This is a $K\times 2n$ two dimensional array. Each row corresponds
to a level of $\mathcal{T}$ and column corresponds to a vertex in $U_{l},1\leq
l\leq K$; by Lemma 40, $U_{l}$ has at most $2n$ vertices. $E[l][v]=i$ where
$i$ is the index of the path $P_{i}\in\mathcal{P}$ that has non-empty
intersection with a heavy path $H$ at level $l$ and $v$ is the vertex in
$G_{l}$ corresponding to $P_{i}\cap H$. For vertex labels that are not present
in $U_{l}$, $E[l][v]$ stores 0. The total space taken by $E$ is
$O(n\log^{2}n)$ as there are $2n\log n$ entries and each entry takes $\log n$
bits.

  * •

$\texttt{getPathIndex}(l,v)$: Returns the path index stored at $E[l][v]$ in
constant time given $1\leq l\leq K$ and $1\leq v\leq 2n$ as input.

The Path Intersection Table (PIT). $PIT$ is an $n\times K$ two dimensional
array of records with rows corresponding to paths of $\mathcal{P}$ and columns
to the levels of $\mathcal{T}$. For path index $i$ and level $l$, each record
consists of a bit and two vertex labels $v,v^{\prime}\in V(G_{l})$ such that
$v$ denotes $P_{i}\cap H_{w}$ and $v^{\prime}$ denotes $P_{i}\cap
H_{w^{\prime}}$ for some heavy paths $H_{w}$ and $H_{w^{\prime}}$
corresponding to nodes $w,w^{\prime}\in V(\mathcal{T})$ at level $l$. The
entries in $PIT$ are as follows:

  1. 1.

$PIT[i][l]=1$, if the path $P_{i}$ has non-empty intersection with some heavy
path at level $l$ else $PIT[i][l]=0$. Storing this information takes $n\log n$
bits.

  2. 2.

$PIT[i][l]$ stores the labels of the two vertices in interval graphs
$G_{H_{w}}$ and $G_{H_{w^{\prime}}}$ corresponding to $P_{i}\cap H_{w}$ and
$P_{i}\cap H_{w^{\prime}}$ where $w,w^{\prime}\in V(\mathcal{T}$ at level $l$.
If $P_{i}$ does not belong to the level $l$ then we store NULL. If $P_{i}$
belongs to the level $l$ but to only one interval graph, say $G_{H_{w}}$, then
$PIT[i][l]$ stores the label of the vertex in $G_{H_{w}}$. Each entry of the
PIT takes at most $2\log n$ bits, since by Lemma 40 there are at most two
labels for a path per level.

$PIT$ has $n\log n$ entries and each entry takes $O(\log n)$ bits. Thus, total
space needed is $O(n\log^{2}n)$. PIT is constructed as follows. Note that as
per Proposition 15, each heavy path in $\mathcal{H}$ is an interval.

  1. 1.

Initialize an array of counters $c[l]\leftarrow 0$ for each level $1\leq l\leq
K$.

  2. 2.

For each $i\in[n]$ perform the following steps.

    1. (a)

For each $a\in V(P_{i})$ and the heavy path
$j\leftarrow\texttt{getHeavyPath}(a)$ such that $a$ is the first vertex of
$P_{i}$ that is also in $H_{j}$, do the following steps.

      1. i.

$l\leftarrow\texttt{getLevel}(j)$.

      2. ii.

Store new vertex label $c[l]\leftarrow c[l]+1$ corresponding to path
$P_{i}\cap H_{j}$ at level $l$ at $PIT[i][l]$.

The following functions are supported.

  1. 1.

$\texttt{isPresent}(i,l)$: Returns true if $PIT[i][l]=1$ in constant time for
path index $i\in[n]$ and the level $1\leq l\leq K$.

  2. 2.

$\texttt{getVertices}(i,l)$: Returns the vertex labels stored at $PIT[i][l]$
in constant time for path index $i\in[n]$ and level $1\leq l\leq K$. The
vertices are ordered based on the total order of the heavy paths that define
them.

The Interval Graph Table (IT). $IT$ is a one dimensional array of length $K$.
As a consequence of Lemma 38, $U_{l},1\leq l\leq K,$ is an interval graph. For
level $l$, $IT[l]$ stores $U_{l}$ using the method of Acan et al. [4]. Thus,
the total space taken by IT is $O(n\log^{2}n)$. IT can be constructed in
polynomial time as follows. Populate $IT[l]$, for each level $l$ of
$\mathcal{T}$, using the following steps.

  1. 1.

Let $S_{l}$ be the set of heavy paths at level $l$. Obtain $S_{l}$ from $L$
and sort it in non-decreasing order.

  2. 2.

Let UNUSED=0 and USED=1. For each $w\in S_{l}$ and path
$P_{i}\in\mathcal{P},i\in[n],$ do the following after initializing the bit
vector $B$ of length $2n$ to UNUSED.

    1. (a)

If $P_{i}\cap H_{w}\neq\phi$ then add the vertex returned by
$\texttt{getVertices}(i,l)$ that is marked UNUSED in $B$ to $V(G_{H_{w}})$.
Once a vertex corresponding to a path in $PIT$ is added to the interval graph
it is marked as USED in $B$.

    2. (b)

For every vertex $u$ added to $V(G_{H_{w}})$, add $u$ into a temporary array
$\texttt{TEMP}[w]$ along with $V(P_{i}\cap H_{w})$.

  3. 3.

For every $w\in S_{l}$, add edges to interval graph $G_{H_{w}}$ as follows.

    1. (a)

For all pairs of vertex labels $u$ and $v$ in $\texttt{TEMP}[w]$ where $u$
corresponds to $P_{i}\cap H_{w}$ and $v$ corresponds to $P_{j}\cap H_{w}$, add
edge $\\{u,v\\}$ to $E(G_{H_{w}})$ if $V(P_{i}\cap H_{w})\cap V(P_{j}\cap
H_{w})\neq\phi$.

  4. 4.

Finally, we get $U_{l}=\\{G_{H_{w}}\mid w\in S_{l}\\}$.

$U_{l}$ thus obtained can now be stored using the data structure of [4]. The
following functions are supported by IT.

  1. 1.

$\texttt{adjacentIG}(u,v,l)$: Returns true if $u,v\in V(U_{l})$ are adjacent
in constant time. This adjacency check is delegated to the interval graph
representation of [4]. [4] supports constant time adjacency query.

  2. 2.

$\texttt{neighbourhoodIG}(u,l)$: Returns the neighbours of vertex $u\in
V(U_{l})$ in $O(d_{u})$ time where $d_{u}$ is the degree of vertex $u$. The
query is delegated to the interval graph representation of [4]. [4] returns
neighbours in constant time per neighbour.

Array $R$. This is an $n\times 2$ two dimensional array. For
$P_{i}\in\mathcal{P}$, $R[i][1]=a_{i}$ and $R[i][2]=b_{i}$ where $a_{i}$ and
$b_{i}$ are the lowest and highest levels to which heavy paths
$H_{w},H_{w^{\prime}}\in\mathcal{H}$ belong in $\mathcal{T}$ such that
$H_{w}\cap P_{i}\neq\phi$ and $H_{w^{\prime}}\cap P_{i}\neq\phi$. Since
$P_{i}$ is a path, it has non-empty intersection with some heavy path at all
the levels in the range $[a_{i},b_{i}]$. We say, $P_{i}$ spans the levels from
$a_{i}$ to $b_{i}$ and denote this range by an interval
$I_{i}=[a_{i},b_{i}],1\leq a_{i}\leq b_{i}\leq K$. Each row of $R$ consists of
two values, each taking $O(\log\log n)$ bits since $K\leq\log n$. $R$ takes a
total space of $O(n\log\log n)$ bits.
The following functions are supported by $R$:

  1. 1.

$\texttt{getEndPoints}(i)$: Returns the end points of $I_{i}$ for path
$P_{i}\in\mathcal{P}$ in constant time for path index $i\in[n]$.

  2. 2.

$\texttt{getMinLevel}(i,j)$: Returns the left end point of $I_{i}\cap I_{j}$
in constant time for path indices $i,j\in[n]$ if $I_{i}\cap I_{j}\neq\phi$
else returns 0. The function returns:

    1. (a)

if $b_{i}<a_{j}$ or $b_{j}<a_{i}$ then 0

    2. (b)

else if $a_{i}\leq b_{j}$ then $a_{i}$

    3. (c)

else if $a_{j}\leq b_{i}$ then $a_{j}$

Array $A$. This is a one dimensional array of length $M$. $A[a],1\leq a\leq
M,$ stores the list of paths that have their lca at node $a\in V(T)$. A path
have only one lca and it takes $\log n$ bits to store this information as
$M\leq n$. For $n$ paths it takes $O(n\log n)$ bits. The following function is
supported.

  * •

$\texttt{getPathsLCA}(a)$: Returns paths in $\mathcal{P}$ with lca at node
$a\in V(T)$ in constant time.

Heavy path tree $\mathcal{T}$. The heavy path tree of clique tree $T$ is
stored using the method of Lemma 10 in $\mathcal{T}$. Since $T$ is an ordinal
tree, $\mathcal{T}$ is also ordinal. $\mathcal{T}$ takes $2n+o(n)$ bits and
supports all the methods of ordinal trees as supported by the data structure
of Lemma 10.

Array $H$. This is a one dimensional array of length $|\mathcal{H}|$; see
Figure 5 for an example. Let $w\in V(\mathcal{T})$ have $n_{w}$ children.
Contents of $H$ are as follows.

  * •

$H[w]$ stores a one dimensional array $C$ of length $n_{w}$ with a location
for each of the children of $w$.

  * •

$H[w]=\texttt{NULL}$ if $w$ does not have any children.

Since $\mathcal{T}$ is an ordinal tree, the children of a node are ordered.
For the $i-$th child of $w$, denoted $c$, with $n_{c}$ children, $C[i]$ stores
a one dimensional array $D$ of length $n_{c}+1$. Contents of $D$ are as
follows.

  * •

$D[j][1]=d,1\leq j\leq n_{c},$ where $d$ is the $j-$th child of $c$ and
$D[j][2]$ contains a list that stores the paths that contain edges $\\{d,c\\}$
and $\\{c,w\\}$ where $w,c,d$ belong to consecutive levels
$l_{1}<l_{2}<l_{3}$, respectively, in $\mathcal{T}$.

  * •

$D[n_{c}+1][1]=\texttt{NULL}$ and $D[n_{c}+1][2]$ stores the list of paths
that contain only $\\{c,w\\}$ and no light edge incident on $c$ in the sub-
tree rooted at $c$.

  * •

If $c$ does not have a child then $D[1][1]=\texttt{NULL}$ and $D[1][2]$
contains the list of paths that contain light edge $\\{c,w\\}$.

$C$ and $D$ are of size $O(n\log n)$ bits as they store entries for edges of
$\mathcal{T}$ which, as a consequence of Remark 4, is at most $n-1$. Thus,
$H$, $C$, and $D$ take a total of $O(n\log n)$ bits. The following function is
supported.

  * •

$\texttt{getDistinctPaths}(w_{1},w_{2},w_{3})$: Returns, in constant time, the
list of paths that contain light edge $\\{w_{1},w_{2}\\}$ but not
$\\{w_{2},w_{3}\\}$ where $\\{w_{1},w_{2}\\},\\{w_{2},w_{3}\\}\in
E(\mathcal{T})$ and $w_{1},w_{2},w_{3}$ lie on consecutive levels
$l_{1}<l_{2}<l_{3}$, respectively, in $\mathcal{T}$.

Figure 5: A part of an example heavy path tree $\mathcal{T}$, is shown on the
left side and array $H$ is shown on the right side. $H[w]$ contains $C$ with
three entries corresponding to its children $\\{a_{1},a_{2},a_{3}\\}$. The
array $D$ corresponding to child $a_{2}$ at $C[2]$ is also shown. The first
entry in the list stored at $D$ corresponds to $c_{1}$ and is associated with
a list containing only one entry, $P_{1}$. This means $P_{1}$ contains light
edge $\\{c_{1},a_{2}\\}$ and $\\{a_{2},w\\}$. The last entry in $D$ is NULL
which implies there is no path that starts at $a_{2}$ and contains light edge
$\\{a_{2},w\\}$. Notice that the $D$ corresponding to child $c_{2}$ of
$a_{2}$, contains $P_{2}$ as the last entry.

######  Lemma 41.

Let $\mathcal{T}$ be the ordinal heavy path tree and
$\\{w_{1},w_{2}\\},\\{w_{2},w_{3}\\}\in E(\mathcal{T})$ be two light edges
such that $w_{1},w_{2},w_{3}$ lie on consecutive levels $l_{1}<l_{2}<l_{3}$,
respectively, in $\mathcal{T}$. There exists a function that returns the list
of paths that contain $\\{w_{1},w_{2}\\}$ but not $\\{w_{2},w_{3}\\}$ in
constant time per path returned.

###### Proof.

The function $\texttt{getDistinctPaths}(w_{1},w_{2},w_{3})$ is implemented as
follows.

  1. 1.

$r\leftarrow\texttt{child\\_rank}(w_{2})$. child_rank is a function supported
by ordinal tree $\mathcal{T}$ that returns the number of siblings to the left
of $w_{2}$. It takes constant time as per Lemma 10.

  2. 2.

Obtain array $D$ from $C[r+1]$ stored in $H[w_{1}]$. Let $L^{\prime}$ denote
the list obtained by concatenating the lists stored at $D$ except the list
corresponding to $w_{3}$.

  3. 3.

Return $L^{\prime}$.

child_rank takes constant time as per Lemma 10. Concatenating each list into
one takes constant time per list concatenated. As each list contains at least
one neighbour, the time taken is $O(1)$ per path returned. ∎

######  Lemma 42.

There exists an $O(n\log^{2}n)$-bit space-efficient data structure for path
graphs.

###### Proof.

The space taken by the components of the space-efficient data structure for
path graphs are as follows:

  1. 1.

Array $F$ that contains the heavy paths to which each node of $T$ belongs
takes $O(n\log n)$ bits.

  2. 2.

Array $L$ stores the level to which each heavy path belongs taking
$O(n\log\log n)$ bits. $R$ stores the ranges of levels in ${\cal T}$ that a
path spans taking $O(n\log\log n)$ bits.

  3. 3.

For every level $l$, the path index corresponding to each of the vertex labels
in $U_{l}$ is stored in array $E$ using $O(n\log^{2}n)$ bits. $PIT$ stores the
levels to which paths in $\mathcal{P}$ belong. For each level $l$, the vertex
labels in $U_{l}$ corresponding to a path in $\mathcal{P}$ is stored using
$O(n\log^{2}n)$ bits. For each level $l$, $IT$ stores the interval graph
$U_{l}$ taking $O(n\log^{2}n)$ bits using the representation of [4].

Thus, the entire space-efficient data structure uses $O(n\log^{2}n)$ bits. ∎

###  5.2 Adjacency and Neighbourhood Queries

Next, we present the algorithms for the adjacency, neighborhood and degree
queries and their time complexities. We have the following useful lemmata that
we will use in the implementation of the queries.

######  Lemma 43.

Consider paths with indices $i,j\in[n]$ such that $[l_{1},l_{2}]$ is the
maximal range of levels with $PIT[i][l]=PIT[j][l]=1$ for all
$l\in[l_{1},l_{2}]$. If paths $P_{i}$ and $P_{j}$ do not intersect in
$U_{l_{1}}$ then they do not intersect at any level $l>l_{1}$.

###### Proof.

If paths $P_{i},P_{j}\in\mathcal{P}$ do not intersect in $U_{l_{1}}$ then
there are two possibilities:

  1. 1.

They intersect two different heavy paths at level $l_{1}$ in the heavy path
tree. In this case, they will not intersect in any level greater than $l_{1}$
as they are contained in two different branches of the heavy path tree.

  2. 2.

They intersect the same heavy path at level $l_{1}$ but different heavy paths
at levels greater than $l_{1}$. Thus, at any level $l>l_{1}$ they are in
different branches of the heavy path tree and so will not intersect.

Hence, the lemma. ∎

######  Lemma 44.

Let $P=(l,r)$ and $Q=(s,t)$ be two paths in $\mathcal{P}$ with sequence of
heavy sub-paths $\Pi_{P}$ and $\Pi_{Q}$, respectively. Also, let $V(P)\cap
V(Q)\neq\phi$ such that there does not exist a light edge $e$ such that $e\in
E(P)\cap E(Q)$. The following are true.

  1. 1.

There exists exactly one $\pi\in\Pi_{P},\pi^{\prime}\in\Pi_{Q}$ and heavy path
$H=(h_{1},h_{2})$ such that $V(\pi)\cap V(\pi^{\prime})\cap V(H)\neq\phi$.

  2. 2.

Further, either $E(P)\subseteq E(T_{h_{1}})$ or $E(Q)\subseteq E(T_{h_{1}})$
where $T_{h_{1}}$ is the sub-tree rooted at $h_{1}$.

  3. 3.

The lowest numbered node of $\pi$ is either the ${\texttt{lca}(l,r)}$ or it is
$h_{1}$ such that light edge $\\{h_{1},{\texttt{parent}(h_{1})}\\}\in E(P)$.

  4. 4.

Either, ${\texttt{lca}}(l,r)\in V(\pi)$ or ${\texttt{lca}}(s,t)\in V(\pi)$.

###### Proof.

The proof is as follows:

  1. 1.

$V(P)\cap V(Q)$ is contained in some $H\in\mathcal{H}$, since by Lemma 7, the
nodes of $T$ are partitioned among the heavy paths. There is exactly one such
$H$, as $V(P)\cap V(Q)$ does not have pair of nodes $u,v$ such that
$\\{u,v\\}$ is a light edge in $T$.

  2. 2.

We consider two cases here.

    1. (a)

$h_{1}$ is the root of $T$: In this case, trivially $E(P)\subseteq
E(T_{h_{1}})$ and $E(Q)\subseteq E(T_{h_{1}})$ since $T_{h_{1}}=T$.

    2. (b)

$h_{1}$ is not the root of $T$: If both $P$ and $Q$ do not contain light edge
$\\{\texttt{parent}(h_{1}),h_{1}\\}$, then $E(P)\subseteq E(T_{h_{1}})$ and
$E(Q)\subseteq E(T_{h_{1}})$. Else, since $P$ and $Q$ do not share a light
edge, either $\\{\texttt{parent}(h_{1}),h_{1}\\}\in E(P)$ or
$\\{\texttt{parent}(h_{1}),h_{1}\\}\in E(Q)$. Without loss of generality, let
it be an element of $E(P)$. Then, $E(Q)\subseteq E(T_{h_{1}})$. Thus, if $P$
and $Q$ do not share a light edge, at least one of the paths must be contained
inside $T_{h_{1}}$.

  3. 3.

Based on the earlier proved statement, we have two cases:

    1. (a)

$E(P)\subseteq E(T_{h_{1}})$: In this case, $\texttt{lca}(l,r)\in V(\pi)$ and
is the lowest numbered node in $\pi$.

    2. (b)

$E(P)\nsubseteq E(T_{h_{1}})$: In this case, $h_{1}\in V(\pi)$ and is the
lowest numbered node in $\pi$.

  4. 4.

There are two possibilities based on the lowest numbered node in $\pi$.

    1. (a)

If the lowest numbered vertex of $\pi$ is the $\texttt{lca}(l,r)$ then the
statement follows trivially.

    2. (b)

If the lowest numbered vertex of $\pi$ is $h_{1}$ such that light edge
$\\{h_{1},\texttt{parent}(h_{1})\\}\in E(P)$ then $\texttt{lca}(s,t)\in
V(\pi)\cap V(\pi^{\prime})$; since $E(Q)\subseteq E(T_{h_{1}})$. Hence, the
result.

∎

######  Lemma 45.

For every $a\in V(T)$ there exists $P=(l,r)$ in $\mathcal{P}$ such that
$a={\texttt{lca}}(l,r)$.

###### Proof.

Every $a\in V(T)$ corresponds to a maximal clique of $G$. We categorise
maximal cliques of $G$ in the following manner.

  1. 1.

Maximal clique $C\in\mathcal{C}$ contains a simplicial vertex $v\in V(G)$: Let
$P_{v}=(a,a)$ be the path corresponding to $v$ where $a\in V(T)$ is the node
corresponding to $C$. Then, $\texttt{lca}(a,a)=a$ and the statment follows.

  2. 2.

Maximal clique $C\in\mathcal{C}$ does not contain a simplicial vertex: Since
$C$ is a maximal clique, $V(C)\nsubseteq V(C^{\prime})$ for
$C^{\prime}\in\mathcal{C}$ and $C\neq C^{\prime}$. Let $a\in V(T)$ be the node
corresponding to $C$. If all the vertices of $C$ correspond to paths that
contain $\texttt{parent}(a)$ then $C\subseteq C^{\prime}$ where $C^{\prime}$
is the maximal clique corresponding to $\texttt{parent}(a)$. Thus, at least
one of the following must be true:

    1. (a)

there is a path containing $a$ that starts at a descendant of $a$ and ends at
another descendant of $a$, or

    2. (b)

there is a path that starts at $a$ and ends at a descendant of $a$.

Let that path be $P=(l,r)$. Then, $\texttt{lca}(l,r)=a$.

∎

Adjacency query. The adjacency query of Algorithm 4 takes the index $i,j$ of
paths $P,Q\in\mathcal{P}$ and the space-efficient representation constructed
in Section 5.1 as input and checks if $P_{i},P_{j}\in\mathcal{P}$ have a non-
empty intersection.

1

2 Function  _adjacency(_$i,j$_)_:

3 $l={\texttt{getMinLevel}}(i,j)$

4 if  _$l\neq 0$_ then

5 $\\{u_{1},u_{2}\\}\leftarrow{\texttt{getVertices}}(i,l)$

6 $\\{v_{1},v_{2}\\}\leftarrow{\texttt{getVertices}}(j,l)$

7 if  _for any pair
$\\{a,b\\}\in\\{\\{u_{1},v_{1}\\},\\{u_{1},v_{2}\\},\\{u_{2},v_{1}\\},\\{u_{2},v_{2}\\}\\}$
${\texttt{adjacentIG}}(a,b,l)$ is true_ then

8 return true

9

10

11 return false

12

Algorithm 4 For path graph $(T,\mathcal{P})$ and two paths
$P_{i},P_{j}\in\mathcal{P}$, the function checks if $V(P_{i})\cap
V(P_{j})\neq\phi$.

######  Lemma 46.

Given path indices $i,j\in[n]$ and the space-efficient representation as
input, the function ${\texttt{adjacency}}(i,j)$ checks if paths corresponding
to $i$ and $j$ have a non-empty intersection in constant time.

###### Proof.

Due to Lemma 43 it is only required to check if $P_{i}$ and $P_{j}$ intersect
in level $\texttt{getMinLevel}(i,j)$. If $\texttt{getMinLevel}(i,j)\neq 0$
then in Line 6 of Algorithm 4 we check if any one of the four pairs of vertex
labels paths $P_{i}$ and $P_{j}$ in interval graph $U_{l}$ are adjacent. The
vertex labels for paths $P_{i}$ and $P_{j}$ in $U_{l}$ are obtained using the
function $\texttt{getVertices}(i,l)$ and $\texttt{getVertices}(j,l)$,
respectively in Lines 4 and 5. The adjacency check in the interval graph is
done using the function adjacenctIG in Line 6. Since getMinLevel, getVertices
and adjacenctIG are constant time functions adjacency check can be completed
in constant time. ∎

Neighbourhood query. The neighbourhood query can be implemented as shown in
Algorithm 5. It takes the path index and the space-efficient representation
constructed in Section 5.1 as input and lists all the paths that have a non-
empty intersection with the input path.

1

2 Function  _neighbourhood(_$i$_)_:

3 Set $N_{i},E_{1},E_{2}$ to NULL

4 $[l,r]\leftarrow\texttt{getEndPoints}(i)$

5 $p\leftarrow\texttt{lca}(l,r)$

6 while  _$l\neq p$_ do

7 Add getPathsLCA(l) to $N_{i}$

8 $c\leftarrow\texttt{parent}(l)$

9 if  _${\texttt{getHeavyPath}}(l)\neq{\texttt{getHeavyPath}}(c)$_ then

10 Add $\\{c,l\\}$ to end of $E_{1}$

11

12 $l\leftarrow c$

13

14 $h\leftarrow\texttt{getHeavyPath}(l)$

15 $L\leftarrow\texttt{getLevel}(h)$

16 $\\{v_{1},v_{2}\\}\leftarrow\texttt{getVertices}(i,L)$

17 Add $\texttt{neighbourhoodIG}(v_{1},L)$ to $N_{i}$

18 while  _$r\neq p$_ do

19 Add getPathsLCA(r) to $N_{i}$

20 $c\leftarrow\texttt{parent}(r)$

21 if  _${\texttt{getHeavyPath}}(r)\neq{\texttt{getHeavyPath}}(c)$_ then

22 Add $\\{c,r\\}$ to end of $E_{2}$

23

24 $r\leftarrow c$

25

26 Concatenate $E_{2}$ to the end of $E_{1}$ and assign it to $E$

27 $e^{\prime}\leftarrow\texttt{NULL}$

28 foreach  _$e=(w^{e}_{1},w^{e}_{2})$ in $E$_ do

29 if  _$e^{\prime}={\texttt{NULL}}$_ then

30 Add $\texttt{getDistinctPaths}(w_{1}^{e},w_{2}^{e},{\texttt{NULL}})$ to
$N_{i}$

31

32 else

33 Add $\texttt{getDistinctPaths}(w_{1}^{e},w_{2}^{e},w_{2}^{e^{\prime}})$ to
$N_{i}$

34

35 $e^{\prime}\leftarrow e$

36

37

Algorithm 5 For space-efficient representation of path graph $(T,\mathcal{P})$
and an input path $P_{i}\in\mathcal{P}$, the function returns its neighbours.

######  Lemma 47.

Given the space-efficient data structure for $G$ and the index $i$ of path
$P\in\mathcal{P}$ as input, ${\texttt{neighbourhood}}(i)$ returns the
neighbours of $P$ in $O(d)$ time where $d$ is the degree of $P$.

###### Proof.

We will prove that Algorithm 5 enumerates neighbours of $P$ at least once and
at most a constant number of times. It follows from Lemma 37 that intersecting
paths are of two types, namely, ones with no common light edge and ones with
at least one light edge. We have the following cases.

  1. 1.

Neighbours that share no light edge with $P$: Let $\Pi$ be the set of heavy
sub-paths of $P$. From Lemma 44, neighbours with no common edges with $P$ are
characterised by $\texttt{lca}(s,t)\in V(\pi)$ and/or $\texttt{lca}(l,r)\in
V(\pi)$ where $\pi\in\Pi$. In Lines 5 to 10 and Lines 15 to 20 of Algorithm 5,
the paths with lca in any node $u\in V(\pi)$ are added to $N_{i}$ using the
function getPathsLCA. Further, in Lines 11 to 14, neighbours of $P$, for
instance, $Q$ such that $V(P)\cap V(Q)\cap V(H)\neq\phi$ such that
$H\in\mathcal{H}$ and $\texttt{lca}(l,r)\in V(H)$, are added to $N_{i}$. Thus,
neighbours that share no light edge with $P$ will be counted at least once. A
path $Q$ that has lca in $V(\pi)$ for a $\pi\in\Pi$ such that
$\texttt{lca}(l,r)\in V(\pi)$ will be counted at most twice.

  2. 2.

Neighbours that share at least one light edge with $P$: Let
$p=\texttt{lca}(l,r)$. In Lines 23 to 28 of Algorithm 5, the light edges that
are encountered as we traverse from $l$ to $p$ and $r$ to $p$, respectively,
are considered. getDistinctPaths is used to add paths that contain these light
edges to $N_{i}$. getDistinctPaths do not repeat paths that are counted on
light edges already visited as $P$ is traversed from $l$ to $p$. Also,
getDistinctPaths do not repeat paths that are counted on light edges already
visited as $P$ is traversed from $r$ to $p$. Thus, every neighbour sharing a
light edge with $P$ is counted exactly once.

Some neighbours of $P$ can share a light edge with it and also satisfy, for
some $\pi\in\Pi$, $\texttt{lca}(s,t)\in V(\pi)$ or $\texttt{lca}(l,r)\in
V(\pi)$. In this case too, they will be over-counted at most a constant number
of times.
Functions getEndPoints, lca, getPathsLCA, getHeavyPath, getLevel,
neighbourhoodIG, and getDistinctPaths are constant time functions. Loops at
Line 5 and 15 repeat a maximum of $O(d)$ times since as per Lemma 45, each
node in $V(P)$ is a maximal clique that contributes at least one distinct
neighbour. By the same argument, the loop at Line 23 repeats $O(d)$ times as
the number of edges in $P$ is $O(d)$. Hence, the time complexity of the
neighbourhood query is $O(d)$. ∎

Degree query. The degree of each vertex can be stored using $n\log n$ bits and
the degree query can be solved in constant time.

###### Proof of Theorem 2.

Lemma 42 shows that there exists an $O(n\log^{2}n)$ bit space-efficient data
structure for path graphs. Given this representation as input Lemma 46 shows
that adjacency between vertices can be checked in constant time. Similarly,
using this representation, Lemma 47 shows an $O(d)$ neighbourhood query. Also,
degree query is satisfied in constant time by accessing it from an array.
Thus, we conclude Theorem 2. ∎

##  6 Conclusion

In this work, we designed efficient data structures for path graphs. In the
future, we believe some of the following directions would be interesting to
explore regarding path graphs.

  1. 1.

The best implementations of BFS and DFS are of significant interest as many
other problems for path graphs use them as subroutines. In the work by Acan et
al. [4], for interval graphs we can see that the representation permits very
efficient BFS and DFS algorithms. Can we perform BFS/DFS efficiently on path
graphs assuming our representation?

  2. 2.

Can we show time/space trade-off lower bounds for our data structures? More
specifically, can we prove tight space lower bound of redundancy with respect
to query time?

  3. 3.

Are there other graph classes amenable to our techniques for designing
succinct data structures?

##  7 Reference

## References

  * [1] D. D. Sleator and R. E. Tarjan,  “A data structure for dynamic trees,”  Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing, p. 114–122, 1981.
  * [2] V. Mäkinen and G. Navarro,  “Rank and select revisited and extended,”  Theoretical Computer Science, vol. 387, no. 3, pp. 332–347, 2007\.
  * [3] M. C. Golumbic,  Algorithmic Graph Theory and Perfect Graphs,  North-Holland Publishing Co., NLD, 2004.
  * [4] H. Acan, S. Chakraborty, S. Jo, and S. R. Satti,  “Succinct data structures for families of interval graphs,”  WADS, vol. 11646, 2019.
  * [5] S. Chakraborty and K. Sadakane,  “Indexing graph search trees and applications,”  in 44th MFCS, 2019, pp. 67:1–67:14.
  * [6] J. I. Munro and V. Raman,  “Succinct representation of balanced parentheses and static trees,”  SIAM J. Comput., vol. 31, no. 3, pp. 762–776, 2001.
  * [7] L. C. Aleardi, O. Devillers, and G. Schaeffer,  “Succinct representations of planar maps,”  Theor. Comput. Sci., vol. 408, no. 2-3, pp. 174–187, 2008.
  * [8] A. Farzan and S. Kamali,  “Compact navigation and distance oracles for graphs with small treewidth,”  Algorithmica, vol. 69, no. 1, pp. 92–116, 2014.
  * [9] A. Farzan and J. I. Munro,  “Succinct encoding of arbitrary graphs,”  Theor. Comput. Sci., vol. 513, pp. 38–52, 2013.
  * [10] J. I. Munro and K. Wu,  “Succinct data structures for chordal graphs,”  in ISAAC, 2018, vol. 123 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 67:1–67:12.
  * [11] F. Gavril,  “A recognition algorithm for the intersection graphs of paths in trees,” 1978.
  * [12] C. L. Monma and V. K.-W. Wei,  “Intersection graphs of paths in a tree,”  J. Comb. Theory, Ser. B, vol. 41, no. 2, pp. 141–181, 1986.
  * [13] Reinhard Diestel,  Graph Theory,  Springer Publishing Company, Incorporated, 5th edition, 2017.
  * [14] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein,  Introduction to Algorithms, Third Edition,  The MIT Press, 3rd edition, 2009.
  * [15] R. Grossi and G. Ottaviano,  “Fast compressed tries through path decompositions,”  ACM J. Exp. Algorithmics, vol. 19, Jan. 2015.
  * [16] P. Ferragina, R. Grossi, A. Gupta, R. Shah, and J. S. Vitter,  “On searching compressed string collections cache-obliviously,”  2008, PODS ’08, p. 181–190, ACM.
  * [17] G. Navarro and K. Sadakane,  “Fully functional static and dynamic succinct trees,”  ACM Trans. Algorithms, vol. 10, no. 3, May 2014.
  * [18] R. Raman, V. Raman, and S. R. Satti,  “Succinct indexable dictionaries with applications to encoding _k_ -ary trees, prefix sums and multisets,”  ACM Trans. Algorithms, vol. 3, no. 4, pp. 43, 2007.
  * [19] G. Navarro,  Compact Data Structures - A Practical Approach,  Cambridge University Press, 2016.
  * [20] Alexander Golynski, J. Ian Munro, and S. Srinivasa Rao,  “Rank/select operations on large alphabets: A tool for text indexing,”  in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, USA, 2006, SODA ’06, p. 368–373, Society for Industrial and Applied Mathematics.