11institutetext: ITMO University, St. Petersburg, Russia
22institutetext: TU Berlin, Berlin, Germany

# Self-Adjusting Linear Networks
with Ladder Demand Graph

Vitaly Aksenov 11 Anton Paramonov 11 Iosif Salem 22 Stefan Schmid 22

###### Abstract

Self-adjusting networks (SANs) have the ability to adapt to communication
demand by dynamically adjusting the workload (or demand) embedding, i.e., the
mapping of communication requests into the network topology. SANs can thus
reduce routing costs for frequently communicating node pairs by paying a cost
for adjusting the embedding. This is particularly beneficial when the demand
has structure, which the network can adapt to. Demand can be represented in
the form of a demand graph, which is defined by the set of network nodes
(vertices) and the set of pairwise communication requests (edges). Thus,
adapting to the demand can be interpreted by embedding the demand graph to the
network topology. This can be challenging both when the demand graph is known
in advance (offline) and when it revealed edge-by-edge (online). The
difficulty also depends on whether we aim at constructing a static topology or
a dynamic (self-adjusting) one that improves the embedding as more parts of
the demand graph are revealed. Yet very little is known about these self-
adjusting embeddings.

In this paper, the network topology is restricted to a line and the demand
graph to a ladder graph, i.e., a $2\times n$ grid, including all possible
subgraphs of the ladder. We present an online self-adjusting network that
matches the known lower bound asymptotically and is 12-competitive in terms of
request cost. As a warm up result, we present an asymptotically optimal
algorithm for the cycle demand graph. We also present an oracle-based
algorithm for an arbitrary demand graph that has a constant overhead.

###### Keywords:

Ladder graph Self-adjusting networks Traffic patterns online algorithms.

##  1 Introduction

Traditional networks are static and demand-oblivious, i.e., designed without
considering the communication demand. While this might be beneficial for all-
to-all traffic, it doesn’t take into account temporal or spatial locality
features in demand. That is, sets of nodes that temporarily cover the majority
of communication requests may be placed diameter-away from each other in the
network topology. This is a relevant concern as studies on datacenter network
traces have shown that communication demand is indeed bursty and skewed [3].

Self-adjusting networks (SANs) are optimized towards the traffic they serve.
SANs can be static or dynamic, depending on whether it is possible to
reconfigure the embedding (mapping of communication requests to the network
topology) in between requests, and offline or online, depending on whether the
sequence of communication requests is known in advance or revealed piece-wise.
In the online case, we assume that the embedding can be adjusted in between
requests at a cost linear to the added and deleted edges, thus, bringing
closer frequently communicating nodes. Online algorithms for SANs aim to
reduce the sum of routing and reconfiguration (re-embedding) costs for any
communication sequence.

We can express traffic in the form of a demand graph that is defined by the
set of nodes in the network and the set of pairwise communication requests
(edge set) among them. Knowing the structure of the demand graph could allow
us to further optimize online SANs, even though the demand is still revealed
online. That is, by re-embedding the demand graph to the network we optimize
the use of network resources according to recent patterns in demand.

To the best of our knowledge, the only work on demand graph re-embeddings to
date is [2], where the network topology is a line and the demand graph is also
a line. The authors presented an algorithm that serves $m=\Omega(n^{2})$
requests at cost $O(n^{2}\log n+m)$ and showed that this complexity is the
lower bound. The problem is inspired by the Itinerant List Update Problem [11]
(ILU). To be more precise, the problem in [2] appears to be the restricted
version of the online Dynamic Minimum Linear Arrangement problem, which is
another reformulation of ILU.

Contributions. In this work, we take the next step towards optimizing online
SANs for more general demand graphs. We restrict the network topology to a
line, but assume that the demand graph is a ladder, i.e., a $2\times n$ grid.
We assume that before performing a request, we can re-adjust the line graph by
performing several swaps of two neighbouring nodes, paying one for each swap.
We present a 12-competitive online algorithm that embeds a ladder demand graph
to the line topology, thus, asymptotically matching the lower bound in [2].
This algorithm can be applied to any demand graph that is a subgraph of the
ladder graph and that when all edges of the demand graph are revealed the
topology is optimal and no more adjustments occur. We also optimally solve the
case of cycle demand graphs, which is a simple generalization of the line
demand graph, but is not a subcase of the ladder due to odd cycles. Finally,
we provide a generic algorithm for arbitrary demand graphs, given an oracle
that computes an embedding with the cost of requests bounded by the bandwidth.

A solution for the ladder is the first step towards the $n\times m$ grid
demand graph. Moreover, a ladder (and a cycle) has a constant _bandwidth_ ,
i.e., a minimum value over all embeddings onto a target line graph of a
maximal path between the ends of an edge (request). It can be shown that given
a demand graph $G$ the best possible complexity per request is the bandwidth.

Related work. Avin et al. [2], consider a fixed line (host) network and a line
demand graph. Their online algorithm re-embeds the demand graph to the host
line graph with minimum number of swaps on the embedding. Both [1, 6] present
constant-competitive online algorithms for a fixed and complete binary tree,
where nodes can swap and the demand is originating only from the source.
However, these two works do not consider a specific demand graph. Moreover,
[5] studied optimal but static and bounded-degree network topologies, when the
demand is known. Self-adjusting networks have been formally organized and
surveyed in [7]. Other existing online SAN algorithms consider different
models. The most distinct difference is our focus on online re-embedding while
keeping a fixed host graph (i.e., a line) compared to other works that focus
on changing the network topology. The latter is what, for example, SplayNet
[12] is proposing, where tree rotations change the form of the binary search
tree network, without optimizing for a specific family of demand patterns.

Online demand graph re-embedding also relates to dynamically re-allocating
network resources to follow traffic patterns. In [4], the authors consider a
fixed set of clusters of bounded size, which contain all nodes and migrate
nodes online according to the communication demand. But more broadly, [8]
assumes a fixed grid network and migrates tasks according to their
communication patterns.

Also, relevant problems, from a migration point of view, are the classic list
update problem (LU) [13], the related Itinerant List Update (ILU) problem
[11], and the Minimum Linear Arrangement (MLA) problem [10]. In contrast to
those problems, we study an online problem where requests occur between nodes.

Roadmap.  Section 2 describes the model and background. Section 3 contains the
summary of our three contributions (ladder, cycle, general demand graph) and
their high-level proofs. Section 4 presents the algorithm and analysis for
ladder demand graphs. Some technical details are deferred to the appendix.

##  2 Model and Background

Let us introduce the notation that we are going to use throughout the paper.
Let $V(H)$ and $E(H)$ be the sets of vertices and edges in graph $H$,
respectively. Sometimes, we just use $V$ and $E$ if the graph $H$ is obvious
from the context. Let $d_{H}(u,v)$ be the distance between $u$ and $v$ in
graph $H$.

Let $N$ be the network topology and $\sigma$ be a sequence of pairwise
communication requests between nodes in $N$. Let the demand graph $G$ be the
graph built over the nodes in $N$ and the pairs of nodes that appear in
$\sigma$, i.e.
$G=(V(N),\\{\sigma_{i}=(s_{i},d_{i})\,|\,\sigma_{i}\in\sigma\\})$. We assume
that the demand graph is of a certain type and our overall goal will be to
embed the demand graph $G$ onto the actual network topology $N$ at a minimum
cost. This is non-trivial as requests are selected from $G$ by an online
adversary and $G$ is not known in advance. In the following, we formalize
demand graph embedding and topology reconfiguration.

A configuration (or an embedding) of $G$ (the demand graph) in a graph $N$
(the host network) is an injection of $V(G)$ into $V(N)$; $C_{G\rightarrow N}$
denotes the set of all such configurations. A configuration $c\in
C_{G\rightarrow N}$ is said to serve a communication request $(u,v)\in E(G)$
at the cost $d_{N}(c(u),c(v))$. A finite communication sequence
$\sigma=(\sigma_{1},\ldots,\sigma_{m})$ is served by a sequence of
configurations $c_{0},c_{1},\ldots,c_{m}\in C_{G\rightarrow N}$. The cost of
serving $\sigma$ is the sum of serving each $\sigma_{i}$ in $c_{i}$ plus the
reconfiguration cost between subsequent configurations $c_{i}$ and $c_{i+1}$.
The reconfiguration cost between $c_{i}$ and $c_{i+1}$ is the number of
migrations necessary to change from $c_{i}$ to $c_{i+1}$; a migration swaps
the images of two neighbouring nodes $u$ and $v$ under $c$ in $N$. Moreover,
$E_{i}=\\{\sigma_{1},\ldots,\sigma_{i}\\}$ denotes the first $i$ requests of
$\sigma$ interpreted as a set of edges on $V$. We present algorithms for an
online self-adjusting linear network: a network whose topology forms a
1-dimensional grid, i.e., a line.

######  Definition 1 (Working Model)

Let $G$ be the demand graph, $n$ be the number of vertices in $G$,
$N=(\\{1,\ldots,n\\},\\{(1,2),(2,3),\ldots,(n-1,n)\\}$ be a line (or list)
graph $L_{n}$ (host network), $c$ be a configuration from $C_{G\rightarrow
N}$, and $\sigma$ be a sequence of communication requests. The cost of serving
$\sigma_{i}=(u,v)\in\sigma$ is given by $|c(u)-c(v)|$, i.e., the distance
between $u$ and $v$ in $N$. Migrations can occur before serving a request and
can only occur between nodes configured on adjacent vertices in $N$.

In the following we introduce notions relevant to our new results.

###### Definition 2

A _correct embedding_ of a graph $G$ into graph $N$ is an injective mapping
$\varphi:V(G)\rightarrow V(N)$ that preserves edges, i.e.

$\displaystyle\begin{cases}\forall u,v\in V(G)\text{ with }u\neq
v\Rightarrow\varphi(u)\neq\varphi(v)\\\ (u,v)\in
E(G)\Rightarrow(\varphi(u),\varphi(v))\in E(N)\end{cases}$

######  Definition 3 (Bandwidth)

Given a graph $G$, the _Bandwidth_ of an embedding $c\in C_{G\rightarrow
L_{n}}$ is equal to the maximum over all edges $(u,v)\in E$ of $|c(u)-c(v)|$,
i.e., the distance between $u$ and $v$ on $L_{n}$. $\mathrm{Bandwidth}(G)$ is
the minimum bandwidth over all embeddings from $C_{G\rightarrow L_{n}}$.

###### Remark 1

The $\mathrm{Bandwidth}$ computation of an arbitrary graph is an NP-hard
problem [9].

To save the space, we typically omit the proofs of lemmas and theorems in this
paper and put them in Appendix 0.C. Here we define the $2\times n$ grid or
ladder graph for which we get the main results of our paper.

###### Definition 4

A graph $Ladder_{n}=(V,E)$ is represented as follows. The vertices $V$ are the
nodes of the grid $2\times n$ —
$\\{(1,1),(1,2),\ldots,(1,n),(2,1),(2,2),\ldots,(2,n)\\}$. There is an edge
between vertices $(x_{1},y_{1})$ and $(x_{2},y_{2})$ iff
$|x_{1}-x_{2}|+|y_{1}-y_{2}|=1$.

###### Lemma 1

$\mathrm{Bandwidth}(Ladder_{n})=2$.

###### Proof

The bandwidth is greater than 1, because there are nodes of degree three. The
bandwidth of 2 can be achieved via the “level-by-level” enumeration as shown
on the figure.

Figure 1: Optimal ladder numeration.

###### Lemma 2

For each subgraph $S$ of a graph $G$,
$\mathrm{Bandwidth}(S)\leq\mathrm{Bandwidth}(G)$.

###  2.1 Background

Let us overview the previous results from [2]. In that work, both the demand
and the host graph (network topology) were the line graph $L_{n}$ on $n$
vertices. It was shown that there exists an algorithm that performs
$O(n^{2}\log n)$ migrations in total, while serving the requests themselves in
$O(1)$. By that, if the number of requests is $\Omega(n^{2}\log n)$ then each
request has $O(1)$ amortized cost.

######  Theorem 2.1 (Avin et al. [2])

Consider a linear network $L_{n}$ and a linear demand graph. There is an
algorithm such that the total time spent on migrations is $O(n^{2}\log n)$,
while each request is performed in $O(1)$ omitting the migrations.

We give an overview of this algorithm. At each moment in time, we know some
subgraph of the line demand graph. For each new communication request, there
are two cases: 1) the edge from the demand graph is already known — then, we
do nothing; 2) the new edge is revealed. In the second case, this edge
connects two connected components. We just move the smallest component on the
line network closer to the largest component. The move of each node in one
reconfiguration does not exceed $n$. Since, the total number of
reconfigurations in which the node participates does not exceed $\log n$, we
have $O(n^{2}\log n)$ upper bound on the algorithm. From [2],
$\Omega(n^{2}\log n)$ is also the lower bound on the total cost. Thus, the
algorithm is asymptotically optimal in the terms of complexity.

###### Corollary 1

If $|\sigma|=\Omega(n^{2}\log n)$ the amortized service cost per request is
$O(1)$.

The algorithms are not obliged to perform migrations at all, but the sum of
costs for $\Theta(n^{2})$ requests can be lower-bounded with $\Omega(n^{2}\log
n)$.

######  Theorem 2.2 (Lower bound, Avin et al. [2])

For every online algorithm $ON$ there is a sequence of requests $\sigma_{ON}$
of length $\Theta(n^{2})$ with the demand graph being a line, such that
$cost(ON(\sigma_{ON}))=\Omega(n^{2}\log n)$.

That implies $\Omega(\log n)$ optimality factor since any offline algorithm
knowing the whole request sequence $\sigma$ in advance can simply reconfigure
the network to match the (line) demand graph by paying $\Theta(n^{2})$ in the
worst case.

##  3 Summary of contributions

In this work we present self-adjusting networks with a line topology for a
demand graph that is either a cycle, or a $2\times n$ grid (ladder), or an
arbitrary graph. We study offline and online algorithms on how to best embed
the demand graph on the line graph, such that the embedding cost is minimized.
The online case is more challenging, as the demand graph is revealed edge-by-
edge and the embedding changes, with a cost. The result for the cycle follows
from [2] almost directly. However the result for the ladder is non-trivial and
requires new techniques; it is not simple to reconfigure a subgraph on a
$2\times n$ grid after revealing a new edge in order to get $O(n^{2}\log n)$
cost of modifications in total. We give an overview of each case below.

###  3.1 Cycle demand graph

We start with the following observation. Let $C_{n}$ be a cycle graph on $n$
vertices, i.e., $E(C_{n})=\\{(1,2),\ldots,(n-1,n),(n,1)\\}$. Then,
$\mathrm{Bandwidth}(C_{n})=2$. We give a brief description of how the
algorithm works. We start with the same algorithm as for the line (Section
2.1): while the number of revealed edges is not more than $n-1$, we can
emulate the algorithm for the line. When the last edge appears we restructure
the whole embedding in order to get bandwidth $2$, which is the cycle
bandwidth. For the whole restructuring using swaps, we pay no more than
$O(n^{2})$. This cost is less than the total time spent on the reconstruction
$\Omega(n^{2}\log n)$.

###### Theorem 3.1

Suppose the demand graph is $C_{n}$. There is an algorithm such that the total
cost spent on the migrations is $O(n^{2}\log n)$ and each request is performed
in $O(1)$. In particular, if the number of requests is $\Omega(n^{2}\log n)$
each request has $O(1)$ amortized cost.

The full proof appears in Appendix 0.A.

###### Remark 2

The lower bound with $\Omega(n^{2}\log n)$ that was presented for a line
demand graph still holds in the case of a cycle, since the cycle contains the
line as the subgraph. Thus, our algorithm is optimal.

###  3.2 Ladder demand graph

Now, we state the main result of the paper — the algorithm for the case when
the demand graph is an ladder.

###### Theorem 3.2

Suppose a demand graph is an ladder. There is an algorithm such that the total
cost spent on the migrations is $O(n^{2}\log n)$ and each request is performed
in $O(1)$. In particular, if the number of requests is $\Omega(n^{2}\log n)$
each request has $O(1)$ amortized cost.

We provide a brief description of the algorithm. We say that an ladder has $n$
levels from left to right: i.e., the nodes $(1,x)$ and $(2,x)$ are on the same
level $x$ (see Figure 1). On a high-level, we use the same algorithmic
approach as in Theorem 2.1 for the line demand graph. The main difference is
that instead of embedding the demand graph right away onto the line network,
at first, we “quasi-embed” the graph onto the $2n$-ladder graph, which then we
embed onto the line. By “quasi-embedding” we mean a relaxation of the
embedding defined earlier: at most three vertices of the demand graph are
mapped on each level of the ladder.

Suppose for a moment that we have a dynamic algorithm that quasi-embeds the
graph onto the $2n$-ladder. Given this quasi-embedding we can then embed the
$2n$-ladder onto the line $L_{n}$. We consequently go through from level $1$
to level $2n$ of our ladder and map (at most three) vertices from the level to
the line in some order (see Theorem 1). Such a transformation from the ladder
to the line costs only a constant multiplication overhead.

We explain briefly how to design a dynamic quasi-embedding algorithm with the
desired complexity. At first, we present a static quasi-embedding algorithm,
i.e., we are given a subgraph of the ladder and we need to quasi-embed it.
This algorithm consists of three parts: embed a tree, embed a cycle, embed
everything together. To embed a tree we find a special path in it, named
trunk. We embed this trunk from left to right: one vertex per level. All the
subgraphs connected to trunk are pretty simple and can be easily quasi-
embedded in parallel to the trunk (see Figure 2). To embed a cycle we just
have to decide which orientation it should have. To simplify the algorithm we
embed only the cycles of length at least $6$, omitting the cycles of length
$4$. This decision increases the multiplicative constant of the cost. Finally,
we embed the whole graph: we construct its cycle-tree decomposition and embed
cycles and trees one by one from left to right.

Now, we give a high-level description of our dynamic algorithm. We maintain
the invariant that all the components are quasi-embedded. When an already
served request appears, we do nothing. The complication comes from a newly
revealed edge-request. There are two cases. The first one is when the edge
connects nodes in the same component — thus, there is a cycle. We redo only
the part of the quasi-embedding of the component around the new cycle; the
rest of the component remains. In the second case, the edge connects two
components. We move the smaller component to the bigger one as in Theorem 2.1.
The bigger component does not move and we redo the quasi-embedding of the
smaller one.

Figure 2: Quasi-correct embedding of a tree

Now, we briefly calculate the complexity of the dynamic algorithm. For the
requests of the first case, if the nodes are on the cycle for the first time
(this event happens only once for each node), we pay $O(n)$ for it. Otherwise,
there are already nodes in the cycle. In this case we make sure to re-embed
the existing cycle in a way that all the nodes are moved for a $O(1)$
distance. As for the neighboring nodes, it can be shown that each node is
moved only once as a part of the cycle neighborhood, so we also bound this
movement with $O(n)$ cost. This gives us $O(n^{2})$ complexity in total — each
node is moved by at most $O(n)$. For the requests of the second case, we
always move the smaller component and, thus, we pay $O(n^{2}\log n)$ in total:
each node can be moved by $O(n)$ at most $O(\log n)$ times, i.e., any node can
be at most $\log n$ times in the “smaller” component. Our algorithm matches
the lower bound, since the ladder contains $L_{n}$ as a subgraph.

###  3.3 General graph

We finish the list of contributions with a general result; the case where the
demand graph is an arbitrary graph $G$. The full proofs are available at
Appendix 0.D.

###### Theorem 3.3

Suppose we are given a (demand) graph $G$ and an algorithm $B$, that for any
subgraph $S$ of $G$ outputs an embedding $c\in C_{S\rightarrow L_{|V(G)|}}$
with bandwidth less than or equal to $\lambda\cdot\mathrm{Bandwidth}(G)$ for
some $\lambda$. Then, for any sequence of requests $\sigma$ with a demand
graph $G$ there is an algorithm that serves $\sigma$ with a total cost of
$O(|E(G)|\cdot|V(G)|^{2}+\lambda\cdot\mathrm{Bandwidth}(G)\cdot|\sigma|)$. In
particular, if the number of requests is $\Omega(|E(G)|\cdot|V(G)|^{2})$ each
request has $O(\lambda\cdot\mathrm{Bandwidth}(G))$ amortized cost.

Here we give a brief description of the algorithm. Suppose that the current
configuration $c_{i}$ is the embedding of the current demand graph $G_{i}$
onto $L_{|V(G)|}$ after $i$ requests. Now, we need to serve a new request in
$\lambda\cdot\mathrm{Bandwidth}(G_{i})\leq\lambda\cdot\mathrm{Bandwidth}(G)$.
If the corresponding edge already exists in the demand graph, we simply serve
the request without the reconfiguration. Now, suppose the request reveals a
new edge and we get the demand graph $G_{i+1}$. Using the algorithm $B$ we get
the configuration (embedding) $c_{i+1}$ that has
$\lambda\cdot\mathrm{Bandwidth}(G_{i+1})\leq\lambda\cdot\mathrm{Bandwidth}(G)$.
To serve the request fast, we should rebuild the configuration $c_{i}$ into
the configuration $c_{i+1}$. By using the swap operations on the line we can
get from $c_{i}$ to $c_{i+1}$ in $O(|V(G)|^{2})$ operations: each vertex moves
by at most $V(G)$. After the reconfiguration we can serve the request with the
desired cost.

A new edge appears at most $|E(G)|$ times while the reconfiguration costs
$|V(G)|^{2}$. Each request is served in $\lambda\cdot\mathrm{Bandwidth}(G)$.
Thus, the total cost of requests $\sigma$ is
$O(|E(G)|\cdot|V(G)|^{2}+\lambda\cdot\mathrm{Bandwidth}(G)\cdot|\sigma|)$.

###### Lemma 3

Given a demand graph $G$. For each online algorithm $ON$ there is a request
sequence $\sigma_{ON}$ such that $ON$ serves each request from $\sigma_{ON}$
for a cost of at least $\mathrm{Bandwidth}(G)$.

##  4 Embedding a ladder demand graph

We present our algorithms for embedding a demand graph that is a subgraph of
the ladder graph ($2\times n$-grid) on the line graph. We first present the
offline case, where the demand graph is known in advance (Section 4.1). Then
we present the dynamic case, where requests are revealed online, revealing
also the demand graph and thus possibly changing the current embedding
(Section 4.2). Finally, we discuss the cost of the dynamic case in Section
4.3.

Though our final goal is to embed a demand graph into the line, we will first
focus on how to embed a partially-known demand graph into $Ladder_{N}$, where
$N$ is large enough to make the embedding possible, i.e., not more then $2n$.
When we have such an embedding one might construct an embedding from
$Ladder_{N}$ into $Line_{n}$, simply composing it with a level by level (see
the proof of Lemma 1) embedding of $Ladder_{N}$ to $Line_{2N}$ and then by
omitting empty images we get $Line_{n}$. Such a mapping of $Ladder_{N}$ to
$Line_{2N}$ enlarges the bandwidth for at most a factor of 2, but
significantly simplifies the construction of our embedding.

###### Definition 5

An ladder graph $l$ consists of two line-graphs on $n$ vertices $l_{1}$ and
$l_{2}$ with additional edges between the lines: $\\{(l_{1}[i],l_{2}[i])\mid
i\in[n]\\}$, where $l_{j}[i]$ is the $i$-th node of the line-graph $l_{j}$. We
call the set of two vertices, $\\{l_{1}[i],l_{2}[i]\\}$, the $i$-th level of
the ladder and denote it as $level_{Ladder_{n}}(i)$ or just $level(i)$ if it
is clear from the context. We refer to $l_{1}[i]$ and $l_{2}[i]$ as
$level(i)[1]$ and $level(i)[2]$, respectively. We say that $level\langle
v\rangle=i$ for $v\in V(Ladder_{n})$ if $v\in level_{Ladder_{n}}(i)$. We refer
to $l_{1}$ and $l_{2}$ as the sides of the ladder.

###  4.1 Static quasi-embedding

We start with one of the basic algorithms — how to quasi-embed on $Ladder_{N}$
with large $N$ any graph that can be embedded in $Ladder_{n}$. We present a
tree and cycle embedding and then we show how to to combine them in embedding
a general component (by first doing a cycle-tree decomposition). The whole
algorithm is presented in Appendix 0.B.1.

####  4.1.1 Tree embedding

In this case, our task is to embed a tree on a ladder graph. We start with
some definitions and basic lemmas.

###### Definition 6

Consider some correct embedding $\varphi$ of a tree $T$ into $Ladder_{n}$. Let
$r=\arg\max\limits_{v\in V(T)}level\langle\varphi(v)\rangle$ and
$l=\arg\min\limits_{v\in V(T)}level\langle\varphi(v)\rangle$ be the
“rightmost” and “leftmost” nodes of the embedding, respectively. The trunk of
$T$ is a path in $T$ connecting $l$ and $r$. The trunk of a tree $T$ for the
embedding $\varphi$ is denoted with $trunk_{\varphi}(T)$.

###### Definition 7

Let $T$ be a tree and $\varphi$ be its correct embedding into $Ladder_{n}$.
The level $i$ of $Ladder_{n}$ is called _occupied_ if there is a vertex $v\in
V(T)$ on that level, i.e., $\varphi(v)\in level_{Ladder_{n}}(i)$.

###### Statement 1

For every occupied level $i$ there is $v\in trunk_{\varphi}(T)$ such that
$v\in level(i)$.

###### Proof

By the definition of the trunk, an image goes from the minimal occupied level
to the maximal. It cannot skip a level since the trunk is connected and the
correct embedding preserves connectivity.

The trunk of a tree in an embedding is a useful concept to define since the
following hold for it. The proofs for the lemmas in this section appear in
Appendix 0.C.

###### Lemma 4

Let $T$ be a tree correctly embedded into $Ladder_{n}$ by some embedding
$\varphi$. Then, all the connected components in
$T\,\setminus\,trunk_{\varphi}(T)$ are line-graphs.

###### Lemma 5

For the tree $T$ and for each node $v$ of degree three (except for maximum two
of them) we can verify in polynomial time if for any correct embedding
$\varphi$, $trunk_{\varphi}(T)$ passes through $v$ or not.

_Support nodes_ are the nodes of two types: either a node of degree three
without neighbours of degree three or a node that is located on some path
between two nodes with degree three. The path through passing through all
support nodes is called _trunk core_. We denote this path for a tree $T$ as
$trunkCore(T)$. Intuitively, the trunk core consists of vertices that lie on a
trunk of any embedding. It can be proven that the support nodes appear in the
trunk of every correct embedding (proof appears in the appendix).

###### Definition 8

Let $T$ be a tree. All the connected components in
$T\,\setminus\,trunkCore(T)$ are called _simple-graphs_ of tree $T$.

###### Lemma 6

The simple-graphs of a tree $T$ are line-graphs.

###### Definition 9

The edge between a simple-graph and the trunk core is called a _leg_. The end
of a leg in the simple-graph is called a _head_ of the simple-graph. The end
of a leg in the trunk core is called a _foot_ of the simple-graph.

If you remove the head of a simple-graph and it falls apart into two connected
components, such simple-graph is called _two-handed_ and those parts are
called its _hands_. Otherwise, the graph is called _one-handed_ , and the sole
remaining component is called a _hand_. If there are no nodes in the simple-
graph but just a head it is called zero-handed.

Figure 3: Hands, Legs, and Trunk core.

###### Definition 10

A simple-graph connected to some end node of the trunk core is called _exit-
graph_. A simple-graph connected to an inner node of the trunk core is called
_inner-graph_.

Please note that the next definition is about a much larger ladder graph,
$Ladder_{N}$, rather than $Ladder_{n}$. Here, $N$ is equal to $2n$ to make
sure that we have enough space to embed.

###### Definition 11

An embedding $\varphi:V(G)\rightarrow V(Ladder_{N})$ of a graph $G$ into
$Ladder_{N}$ is called _quasi-correct_ if:

  * •

$(u,v)\in E(G)\Rightarrow(\varphi(u),\varphi(v))\in E(Ladder_{N})$, i.e.,
images of adjacent vertices in $G$ are adjacent in the grid.

  * •

There are no more than three nodes mapped into each level of $Ladder_{N}$,
i.e., the two grid nodes on each level are the images of no more than three
nodes.

We can think of a quasi-correct embedding as an embedding into levels of the
grid with no more than three nodes embedded to the same level. Then, we can
compose this embedding with an embedding of a grid into the line which is the
enumeration level by level. More formally if a node $u$ is embedded to level
$i$ and a node $v$ is embedded to level $j$ and $i<j$ then the resulting
number of $u$ on the line is smaller than the number of $v$, but if two nodes
are embedded to the same level, we give no guarantee.

###### Lemma 7

Any graph mapped into the ladder graph by the quasi-correct embedding
described above can be mapped onto the line level by level with the property
that any pair of adjacent nodes are embedded at the distance of at most five.

Assume, we are given a tree $T$ that can be embedded into $Ladder_{n}$.
Furthermore, there are two special nodes in the tree: one is marked as R
(right) and another one is marked as L (left). It is known that there exists a
correct embedding of $T$ into $Ladder_{n}$ with R being the rightmost node,
meaning no node is embedded more to the right or to the same level, and L
being the leftmost node.

We now describe how to obtain a quasi-correct embedding of $T$ onto
$Ladder_{N}$ with R being the rightmost node and L being the leftmost one
while $L$ is mapped to $ImageL$ — some node of the $Ladder_{N}$. Moreover, our
embedding obeys the following invariant.

######  Invariant 1 (Septum invariant)

For each inner simple-graph, its foot and its head are embedded to the same
level and no other node is embedded to that level.

Figure 4: Example of a quasi-correct embedding

We embed a path between $L$ and $R$ simply horizontally and then we orient
line-graphs connected to it in a way that they do not violate our desired
invariant. It can be shown that it is always possible if $T$ can be embedded
onto $Ladder_{n}$. The pseudocode is in Appendix Algorithm 1.

Suppose now that not all information, such as $R$, $L$, and $ImageL$, is
provided. We explain how we can embed a tree $T$. We first get the _trunk
core_ of the given tree. This can be done by following the definition. Now the
idea would be to first embed the trunk core and its inner line-graphs using a
tree embedding presented earlier with $R$ and $L$ to be the ends of the trunk
core. Then, we embed exit-graphs strictly horizontally “away” from the trunk
core. That means, that the hands of exit-graphs that are connected to the
right of the trunk core are embedded to the right, and the hands of those
exit-graphs that are connected to the left of the trunk core are embedded to
the left. An example of the quasi-correct embedding is shown in Figure 4.

If a tree does not have a trunk core, then its structure is quite simple (in
particular it has no more than two nodes of degree three). Such a tree can be
embedded without conflicts. The pseudocode appears in Appendix Algorithm
0.B.1.1.

####  4.1.2 Cycle embedding

Now, we show how to embed a cycle into $Ladder_{N}$. First, we give some
important definitions and lemmas.

###### Definition 12

A _maximal_ cycle $C$ of a graph $G$ is a cycle in $G$ that cannot be
enlarged, i.e., there is no other cycle $C^{\prime}$ in $G$ such that
$V(C)\subsetneq V(C^{\prime})$.

###### Definition 13

Consider a graph $G$ and a maximal cycle $C$ of $G$. A whisker $W$ of $C$ is a
line graph inside $G$ such that: 1) $V(W)\neq\emptyset$ and $V(W)\cap
V(C)=\emptyset$. 2) There exists only one edge between the cycle and the
whisker $(w,c)$ for $w\in V(W)$ and $c\in V(C)$. Such $c$ is called a _foot_
of $W$. The nodes of $W$ are enumerated starting from $w$. 3) $W$ is maximal,
i.e., there is no $W^{\prime}$ in $G$ such that $W^{\prime}$ satisfies
previous properties and $V(W)\subsetneq V(W^{\prime})$.

Figure 5: Cycle and its Whiskers.

###### Definition 14

Suppose we have a graph $G$ that can be correctly embedded into $Ladder_{n}$
by $\varphi$ and a cycle $C$ in $G$. Whiskers $W_{1}$ and $W_{2}$ of $C$ are
called adjacent (or neighboring) for the embedding $\varphi$ if $\forall
i\leq\min(|V(W_{1})|,|V(W_{2})|)\ (\varphi(W_{1}[i])$, $\varphi(W_{2}[i]))\in
E(Ladder_{n})$.

###### Lemma 8

Suppose we have a graph $G$ that can be correctly embedded into $Ladder_{n}$
and there exists a maximal cycle $C$ in $G$ with at least $6$ vertices with
two neighbouring whiskers $W_{1}$ and $W_{2}$ of $C$, i.e.,
$(\text{foot}(W_{1}),\text{foot}(W_{2}))\in E(G)$. Then, $W_{1}$ and $W_{2}$
are adjacent in any correct embedding of $G$ into $Ladder_{N}$.

###### Definition 15

Assume we have a graph $G$ and a maximal cycle $C$ of length at least $6$. The
frame for $C$ is a subgraph of $G$ induced by vertices of $C$ and
$\\{W_{1}[i],W_{2}[i]\mid i\leq\min(|V(W_{1})|,|V(W_{2})|)\\}$ for each pair
of adjacent whiskers $W_{1}$ and $W_{2}$. Adding all the edges
$\\{(W_{1}[i],W_{2}[i])\mid i\leq\min(|V(W_{1})|,|V(W_{2})|)\\}$ for each pair
of adjacent whiskers $W_{1}$ and $W_{2}$ makes a frame _completed_.

Figure 6: Cycle, its frame, and edges (dashed) to make the frame completed

Given a cycle $C$ of length at least six and its special nodes $L,R\in V(C)$,
we construct a correct embedding of $C$ into $Ladder_{N}$ with $level\langle
L\rangle\leq level\langle u\rangle\leq level\langle R\rangle\ \forall u\in
V(C)$, while $L$ is mapped into the node $ImageL$.

We first check if it is possible to satisfy the given constraints of placing
the $L$ node to the left and a $R$ node to the right. If it is indeed
possible, we place $L$ to the desired place $ImageL$ and then we choose an
orientation (clockwise or counterclockwise) following which we could embed the
rest of the nodes, keeping in mind that $R$ must stay on the rightmost level.
The pseudocode appears in Appendix Algorithm 3.

Now, suppose that not all information, such as $R$, $L$, and $ImageL$, is
provided. We reduce this problem to the case when the missing variables are
known. This subtlety might occur since there are inner edges in the cycle. In
this case, we choose missing $L/R$ more precisely in order to embed an inner
edge vertically. For more intuition, please see Figures 7(a) and 7(b). A
dashed line denotes an inner edge. The pseudocode appears in the Appendix
(Algorithm 4).

(a) Incorrect cycle embedding

(b) Correct cycle embedding

Figure 7: Cycle embeddings.

####  4.1.3 Embedding a connected component of the demand graph

Combining the previous results, we can now explain how to embed onto
$Ladder_{N}$ a connected component $S$ that can be embedded onto $Ladder_{n}$.

###### Definition 16

By the cycle-tree decomposition of a graph $G$ we mean a set of maximal cycles
$\\{C_{1},\ldots C_{n}\\}$ of $G$ and a set of trees
$\\{T_{1},\ldots,T_{m}\\}$ of $G$ such that

  * •

$\bigcup\limits_{i\in[n]}V(C_{i})\cup\bigcup\limits_{i\in[m]}V(T_{i})=V(G)$

  * •

$V(C_{i})\cap V(C_{j})=\emptyset\ \forall i\neq j$

  * •

$V(T_{i})\cap V(T_{j})=\emptyset\ \forall i\neq j$

  * •

$V(T_{i})\cap V(C_{j})=\emptyset\ \forall i\in[m],j\in[n]$

  * •

$\forall i\neq j\ \forall u\in V(T_{i})\ \forall v\in V(T_{j})\ (u,v)\notin
E(G)$

We start with an algorithm on how to make a cycle-tree decomposition of $S$
assuming no uncompleted frames. To obtain a cycle-tree decomposition of a
graph: 1) we find a maximal cycle; 2) we split the graph into two parts by
logically removing the cycle; 3) we proceed recursively on those parts, and,
finally, 4) we combine the results together maintaining the correct order
between cycle and two parts (first, the result for one part, then the cycle,
and then the result for the second part). Since we care about the order of the
parts, we say that it is a _cycle-tree decomposition chain_. The decomposition
pseudocode appears in the Appendix Algorithm 5.

We describe how to obtain a quasi-correct embedding of $S$. We preprocess $S$:
1) we remove one edge from cycles of size four; 2) we complete uncompleted
frames with vertical edges. Then, we embed parts of $S$ from the cycle-tree
decomposition chain one by one in the relevant order using the corresponding
algorithm (either for a cycle or for a tree embedding) making sure parts are
glued together correctly. The pseudocode appears in Appendix Algorithm
0.B.1.3.

###  4.2 Online quasi-embedding

In the previous subsection, we presented an algorithm on how to quasi-embed a
static graph. Now, we will explain how to operate when the requests are
revealed in an online manner. The full version of the algorithm is presented
in Appendix 0.B.2.

There are two cases: a known edge is requested or a new edge is revealed. In
the first case the algorithm does nothing since we already know how to quasi-
correctly embed the current graph and, thus, we already can embed into the
line network with constant bandwidth. Thus, further, we will consider only the
second case.

We describe how one should change the embedding of the graph after the
processing of a request in an online scenario. At each moment some edges of
the demand graph $Ladder_{n}$ are already revealed, forming connected
components. After an edge reveal we should reconfigure the target line graph.
For that, instead of line reconfiguration we reconfigure our embedding to
$Ladder_{N}$ that is then embedded to the line level by level and introduces a
constant factor. So, we can consider the reconfiguration only of $Ladder_{N}$
and forget about the target line graph at all. When doing the reconfiguration
of an embedding we want to maintain the following invariants:

  1. nosep

The embedding of any connected component is quasi-correct.

  2. nosep

For each tree in the cycle-tree decomposition its embedding respects Septum
invariant 1.

  3. nosep

There are no maximal cycles of length $4$.

  4. nosep

Each cycle frame is completed with all “vertical” edges even if they are not
yet revealed.

  5. nosep

There are no conflicts with cycle nodes, i.e., each cycle node is the only
node mapped to its image in the embedding to $Ladder_{N}$.

For each newly revealed edge there are two cases: either it connects two nodes
from one connected component or not. We are going to discuss both of them.

####  4.2.1 Edge in one component

The pseudocode appears in Appendix Algorithm 8. If the new edge is already
known or it forms a maximal cycle of length four, we simply ignore it.
Otherwise, it forms a cycle of length at least six, since two connected nodes
are already in one component. We then perform the following steps:

  1. 1.

Get the completed frame of a (possibly) new cycle.

  2. 2.

Logically “extract” it from the component and embed maintaining the
orientation (not twisting the core that was already embedded in some way).

  3. 3.

Attach two components appeared after an extraction back into the graph,
maintaining their relative order.

####  4.2.2 Edge between two components

The pseudocode appears in Appendix Algorithm 0.B.2.2. In order to obtain an
amortization in the cost, we always “move” the smaller component to the bigger
one. Thus, the main question here is how to glue a component to the existing
embedding of another component. The idea is to consider several cases of where
the smaller component will be connected to the bigger one. There are three
possibilities:

  1. 1.

It connects to a cycle node. In this case, there are again two possibilities.
Either it “points away” from the bigger component meaning that the cycle to
which we connect is the one of the ends in the cycle-tree decomposition of the
bigger component. Here, we just simply embed it to the end of the cycle-tree
decomposition while possibly rotating a cycle at the end.

Or, the smaller component should be placed somewhere between two cycles in the
cycle-tree decomposition. Here, it can be shown that this small graph should
be a line-graph, and we can simply add it as a whisker, forming a larger
frame.

  2. 2.

It connects to a trunk core node of a tree in the cycle-tree decomposition. It
can be shown that in this case the smaller component again must be a line-
graph. Thus, our only goal is to orient it and possibly two of its inner
simple-graphs neighbours to maintain the Septum invariant 1 for the
corresponding tree from the decomposition.

  3. 3.

It connects to an exit graph node of an end tree of the cycle-tree
decomposition. In this case, we straightforwardly apply a static embedding
algorithm of this tree and the smaller component from scratch. Please, note
that only the exit graphs of the end tree will be moved since the trunk core
and its inner graphs will remain.

###  4.3 Complexity of the online embedding

Now, we calculate the cost of our online algorithm (a more detailed discussion
on the cost of the algorithm appears at Appendix 0.C.5): how many swaps we
should do and how much we should pay for the routing requests. Recall that we
first apply the reconfiguration and, then, the routing request.

We start with considering the routing requests. Their cost is $O(1)$ since
they lie pretty close on the target line network, i.e., by no more than $12$
nodes apart. This bound holds because the nodes are quasi-correctly embedded
on $Ladder_{N}$, two adjacent nodes at $G$ are located not more than four
levels apart (in the worst case, when we remove an edge of a cycle with length
four) where each level of the quasi-correct embedding has at most three images
of nodes of $G$. Thus, on the target line graph, if we enumerate level by
level, the difference between any two adjacent nodes of $G$ is at most $12$.

Then, we consider the reconfiguration. We count the total cost of each case of
the online algorithm before all the edges are revealed.

In the first case, we add an edge in one component. By that, either a new
frame is created or some frame was enlarged. In both cases, only the nodes,
that appear on some frame for the first time, are moved. Since, a node can be
moved only once to be mapped on a frame and it is swapped at most $N=O(n)$
times to move to any position, the total cost of this type of reconfiguration
is at most $O(n^{2})$. Also, there are several adjustments that could be done:
1) the “old” frame can rotate by one node, and 2) possibly, we should flip the
first inner-graphs of two components connected to the frame. In the first
modification, each node at the frame can only be “rotated” once, thus, paying
$O(n)$ cost in total. In the second modification, inner-graph can change
orientation at most once in order to satisfy the Septum invariant (Invariant
1), thus, paying $O(n^{2})$ cost in total — each node can move by at most
$N=O(n)$.

In the second case, we add an edge in between two components. At first, we
calculate the time spent on the move of the small component to the bigger one:
each node is moved at most $O(\log n)$ times since the size of the component
always grows at least two times, the number of swaps of a vertex is at most
$N=O(n)$ to move to any place, thus, the total cost is $O(n^{2}\log n)$.
Secondly, there are two more modification types: 1) a rotation of a cycle, and
2) some simple-graphs can be reoriented. The cycle can be rotated only once,
thus, we should pay at most $O(n)$ there. At the same time, each simple-graph
can be reoriented at most once to satisfy the Septum invariant (Invariant 1),
thus, the total cost is $O(n^{2})$ for that type of a reconfiguration.

To summarize, the total cost of requests $\sigma$ is $O(n^{2}\log n)$ for the
whole reconfiguration plus $O(|\sigma|)$ per requests. This matches the lower
bound that was obtained for the line demand graph. The same result holds for
any demand graph that is the subgraph of the ladder of size $n$.

###### Theorem 4.1

The online algorithm for embedding the ladder demand graph of size $n$ on the
line graph has total cost $O(n^{2}\log n+|\sigma|)$ for a sequence of
communication requests $\sigma$.

##  5 Conclusion

We presented methods for statically or dynamically re-embedding a ladder
demand graph (or a subgraph of it) on a line, both in the offline and online
case. As side results, we also presented how to embed a cycle demand graph and
a meta-algorithm for a general demand graph. Our algorithms for the cycle and
the ladder cases match the lower bounds. Our work is a first step towards a
tight bound on dynamically re-embedding more generic demand graphs, such as
arbitrary grids.

## References

  * [1] Avin, C., Bienkowski, M., Salem, I., Sama, R., Schmid, S., Schmidt, P.: Deterministic self-adjusting tree networks using rotor walks. In: 2022 IEEE 42nd International Conference on Distributed Computing Systems (ICDCS). pp. 67–77. IEEE (2022)
  * [2] Avin, C., van Duijn, I., Schmid, S.: Self-adjusting linear networks. In: International Symposium on Stabilizing, Safety, and Security of Distributed Systems. pp. 368–382. Springer (2019)
  * [3] Avin, C., Ghobadi, M., Griner, C., Schmid, S.: On the complexity of traffic traces and implications. Proceedings of the ACM on Measurement and Analysis of Computing Systems 4(1), 1–29 (2020)
  * [4] Avin, C., Loukas, A., Pacut, M., Schmid, S.: Online balanced repartitioning. In: International Symposium on Distributed Computing. pp. 243–256. Springer (2016)
  * [5] Avin, C., Mondal, K., Schmid, S.: Demand-aware network design with minimal congestion and route lengths. IEEE/ACM Transactions on Networking (2022)
  * [6] Avin, C., Mondal, K., Schmid, S.: Push-down trees: optimal self-adjusting complete trees. IEEE/ACM Transactions on Networking 30(6), 2419–2432 (2022)
  * [7] Avin, C., Schmid, S.: Toward demand-aware networking: a theory for self-adjusting networks. ACM SIGCOMM Computer Communication Review 48(5), 31–40 (2019)
  * [8] Batista, D.M., da Fonseca, N.L.S., Granelli, F., Kliazovich, D.: Self-adjusting grid networks. In: 2007 IEEE international conference on communications. pp. 344–349. IEEE (2007)
  * [9] Díaz, J., Petit, J., Serna, M.: A survey of graph layout problems. ACM Computing Surveys (CSUR) 34(3), 313–356 (2002)
  * [10] Hansen, M.D.: Approximation algorithms for geometric embeddings in the plane with applications to parallel processing problems. In: 30th Annual Symposium on Foundations of Computer Science. pp. 604–609. IEEE Computer Society (1989)
  * [11] Olver, N., Pruhs, K., Schewior, K., Sitters, R., Stougie, L.: The itinerant list update problem. In: International Workshop on Approximation and Online Algorithms. pp. 310–326. Springer (2018)
  * [12] Schmid, S., Avin, C., Scheideler, C., Borokhovich, M., Haeupler, B., Lotker, Z.: Splaynet: Towards locally self-adjusting networks. IEEE/ACM Trans. Netw. 24(3), 1421–1433 (2016)
  * [13] Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Communications of the ACM 28(2), 202–208 (1985)

##  Appendix 0.A The algorithm for the Cycle

We start with the most simple generalization result — when the demand graph is
the cycle on $n$ vertices.

###### Theorem 3.1

Suppose the demand graph is $C_{n}$. There is an algorithm such that the total
cost spent on the migrations is $O(n^{2}\log n)$ and each request is performed
in $O(1)$. In particular, if the number of requests is $\Omega(n^{2}\log n)$
each request has $O(1)$ amortized cost.

###### Proof

The idea of the algorithm is to act as in the algorithm described in [2] for
the list demand graph until revealed edges do not form a cycle. Once they do
we perform a total reconfiguration enumerating nodes of $C_{n}$ with

$\displaystyle\begin{cases}i\rightarrow 2i-1,\text{ if
}i\leq\lceil\frac{n}{2}\rceil\\\ i\rightarrow 2(n-i+1),\text{
otherwise}\end{cases}$

so, for each pair of adjacent nodes the difference of their numbers is at most
2. The enumeration can be seen on Figure 8.

More formally. Let $G_{i}=(V,E_{i})$ — the demand graph after $i$ requests,
and $G_{0}=(V,\emptyset)$. We want to maintain the invariant that each $G_{i}$
is embedded in a way that all adjacent nodes are at a distance of at most $2$.
Moreover, if there is a line subgraph of $G_{i}$ then it is embedded as a
line, i.e., the embedding preserves edges. We present an algorithm that
maintains this invariant by induction.  Figure 8: Cycle enumeration with
Bandwidth $2$

y

This invariant holds for $G_{0}$. We assume that the invariant holds for
$G_{i-1}$ and a new request $\sigma_{i}$ arrives. If $\sigma_{i}$ is already
present in $E(G_{i-1})$ then the invariant holds, we do not reconfigure, and
pay at most $2$.

If now $G_{i}$ is a cycle we perform a total reconfiguration with the
enumeration with bandwidth $2$ described above. For that we pay $O(n^{2})$
that is less than $O(n^{2}\log n)$, and, thus, our complexity lies inside our
bounds. Note that once $G_{i}$ becomes a cycle we need no further
reconfigurations since all the edges are known and the invariant is
maintained.

The last case is when $\sigma_{i}$ is a new edge and $G_{i}$ still consists of
several connected components. We use the algorithm presented in [2].
$\sigma_{i}$ connects two different connected components, say $L_{1}$ and
$L_{2}$ forming a new list subgraph $L$. Suppose that
$|V(L_{1})|\leq|V(L_{2})|$. Our strategy would be to “drag” $L_{1}$ towards
$L_{2}$ that is if $L_{1}=\\{u_{1},\ldots,u_{l}\\}$,
$V(L_{2})=\\{v_{1},\ldots,v_{k}\\}$, $\sigma_{i}=(v_{k},u_{1})$. By the
invariant $L_{2}$ is embedded with $v_{p}$ at $q+p$ for some $q$ and we want
nodes of $L_{1}$ to be embedded with $u_{p}\rightarrow q+k-1+p$. So, we bring
each node of $L_{1}$ to its position performing required number of swaps.
Note, that this reconfiguration brings the embedding that supports the
invariant. Now, we analyze the cost of the algorithm processing the requests.

Due to the invariant each request is served with a cost of at most $2$. As for
the reconfiguration cost: a node can move a distance $\Theta(n)$ during
processing one request and it moves no more than $O(\log n)$ times: we either
form a cycle or merge two components. Thus, the total cost does not exceed
$O(n^{2}\log n)$.

##  Appendix 0.B Full algorithm for the ladder

###  0.B.1 Static quasi-embedding

####  0.B.1.1 Tree embedding

Assume, we are given a tree $T$ that can be embedded into $Ladder_{n}$.
Furthermore, there are two marked nodes in the tree: one is marked right and
the left. It is known that there is a correct embedding of $T$ with right
being the right-most node, meaning no node is embedded higher or to the same
level, and left being the left-most node.

We now describe how to obtain a quasi-correct embedding of $T$ with right
being the right-most node and left being the left-most one and $left$ mapped
to $leftImage$. Moreover, this embedding obeys the following invariant:

######  Invariant 2 (Septum invariant)

For each inner simple-graph its foot and its head are embedded to the same
level and no other node is embedded to that level.

We embed the $left-right$ path strictly vertically and then we orient line-
graphs connected to it in the way that they do not violate septum invariant.

See Algorithm 1.

Algorithm 1 Left-Right tree embedding

procedure RightLeftTreeEmbedding($T$, $left$, $right$, $leftImage$)

$P\leftarrow$ path from left to right

$leftSide\leftarrow side(leftImage)$

$leftLevel\leftarrow level\langle leftImage\rangle$

Embed $P[i]\rightarrow level(leftLevel-1+i)[leftSide]$

$L\leftarrow$ line-graphs connected to $P$

$Septa\leftarrow\\{level\langle foot(l)\rangle\mid l\in
L\\}\cup\\{level\langle left\rangle,level\langle right\rangle\\}$

for $l\in L$ do

$i\leftarrow level\langle foot(l)\rangle$

Embed $head(l)\rightarrow level(i)[other(leftSide)]$

Orient $l$ ensuring no nodes of $l\setminus\\{head(l)\\}$ are embedded to any
of levels from $Septa$

We now proceed with an embedding of a tree $T$ where $right$, $left$ and
$leftImage$ might or might not be given. In the case the variable is not given
we denote its value with $\mathrm{None}$.

The idea here would be to first embed the trunk core and its inner line-graphs
using Left-Right tree embedding and then to embed exit-graphs strictly
vertically ”away” from the trunk core. That means that the hands of exit-
graphs that are connected to to the right of the trunk core are embedded
increasingly and hands of those exit-graphs which are connected to the left of
the trunk core are embedded decreasingly.

If a tree does not have a trunk core, that means that its structure is rather
simple (in particular it has no more than two nodes of degree three), so we do
not care about conflicts.

See Algorithm 0.B.1.1.

2 Tree quasi-correct embedding

procedure TreeQuasiCorrectEmbedding($T$, $left$, $right$, $leftImage$)

if $leftImage=\mathrm{None}$ then

$leftImage\leftarrow level(1)[1]$

if $(left\neq\mathrm{None})\wedge(right\neq\mathrm{None})$ then

LeftRightTreeEmbedding($T$, $left$, $right$, $leftImage$)

return

else if $(left\neq\mathrm{None})\wedge(right=\mathrm{None})$ then

if $T$ has a trunk core then

$u,v\leftarrow$ ends of a trunk core

if $u$ between $v$ and $left$ then

$trunkRight\leftarrow v$

else

$trunkRight\leftarrow u$

$et\leftarrow$ exit-graphs connected to $trunkRight$

$S^{\prime}\leftarrow S\setminus et$

LeftRightTreeEmbedding($S^{\prime}$, $left$, $trunkRight$, $leftImage$)

for $e\in et$ do

$lvl\leftarrow level\langle trunkRight\rangle$

$side\leftarrow side(trunkRight)$

Embed $head(e)\rightarrow level(lvl+1)[side]$

for $h\in hands(e)$ do

for $i\in[length(h)]$ do

Embed $h[j]\rightarrow level(lvl+1+i)[side]$

else

$right\leftarrow$ arbitrary node of degree 1

LeftRightTreeEmbedding($T$, $left$, $right$, $leftImage$)

else if $(left=\mathrm{None})\wedge(right\neq\mathrm{None})$ then

if $T$ has a trunk core then

$u,v\leftarrow$ ends of a trunk core

if $u$ between $v$ and $right$ then

$trunkLeft\leftarrow v$

else

$trunkLeft\leftarrow u$

$eb\leftarrow$ exit-graphs connected to $trunkLeft$

$S^{\prime}\leftarrow S\setminus eb$

$leftImageLevel\leftarrow level\langle leftImage\rangle$

$leftImageSide\leftarrow side(leftImage)$

$vShift\leftarrow\max\limits_{e\in eb}\max\limits_{h\in hands(e)}length(h)$

$trunkLeftImage\leftarrow level(leftImageLevel+vShift)[leftImageSide]$

LeftRightTreeEmbedding($S^{\prime}$, $left$, $right$, $trunkLeftImage$)

for $e\in eb$ do

$lvl\leftarrow level\langle trunkLeft\rangle$

$side\leftarrow side(trunkLeft)$

Embed $head(e)\rightarrow level(lvl-1)[side]$

for $h\in hands(e)$ do

for $i\in[length(h)]$ do

Embed $h[j]\rightarrow level(lvl-1-i)[side]$

else

$left\leftarrow$ arbitrary node of degree 1

LeftRightTreeEmbedding($T$, $left$, $right$, $leftImage$)

else

if $T$ has a trunk core then

$trunkRight,\ trunkLeft\leftarrow$ ends of a trunk core

$et\leftarrow$ exit-graphs connected to $trunkRight$

$eb\leftarrow$ exit-graphs connected to $trunkLeft$

$S^{\prime}\leftarrow S\setminus et\setminus eb$

$leftImageLevel\leftarrow level\langle leftImage\rangle$

$leftImageSide\leftarrow side(leftImage)$

$vShift\leftarrow\max\limits_{e\in eb}\max\limits_{h\in hands(e)}length(h)$

$trunkLeftImage\leftarrow level(leftImageLevel+vShift)[leftImageSide]$

LeftRightTreeEmbedding($S^{\prime}$, $left$, $right$, $trunkLeftImage$)

for $e\in et$ do

$lvl\leftarrow level\langle trunkRight\rangle$

$side\leftarrow side(trunkRight)$

Embed $head(e)\rightarrow level(lvl+1)[side]$

for $h\in hands(e)$ do

for $i\in[length(h)]$ do

Embed $h[j]\rightarrow level(lvl+1+i)[side]$

for $e\in eb$ do

$lvl\leftarrow level\langle trunkLeft\rangle$

$side\leftarrow side(trunkLeft)$

Embed $head(e)\rightarrow level(lvl-1)[side]$

for $h\in hands(e)$ do

for $i\in[length(h)]$ do

Embed $h[j]\rightarrow level(lvl-1-i)[side]$

else

$right,left\leftarrow$ furthest nodes of degree 1

$P\leftarrow$ path from $left$ to $right$

Embed $P$ strictly monotone placing $left$ to $leftImage$

if there is a line-graph left then

$l\leftarrow$ left line-graph

$(u,v)\leftarrow(u,v)\in E(T)$ s.t. $u\in P,v\in l$

Embed $v$ to the same level, opposite side to $u$.

Embed $l$ to the opposite side to the side of $P$ preserving connectivity and
correctness

####  0.B.1.2 Cycle embedding

Given a cycle $C$ of length $\geq 6$ and nodes $left,right\in V(C)$ we
construct a correct embedding of $C$ into $Ladder_{\infty}$ with $level\langle
left\rangle\leq level\langle u\rangle\leq level\langle right\rangle\ \forall
u\in V(C)$ and $left$ placed to $leftImage$.

For convenience we assume that for every node $v$ there is a local consecutive
numeration starting at $v$. The number of node $u\in V(C)$ in this numeration
is referenced with $number_{v}(u)$. The node with number $i$ in local
numeration of $v$ is referenced with $C_{v}[i]$.

We first check if it is possible to satisfy the given constraints of placing
the $left$ node to left and a $right$ node to the right. If it is indeed
possible, we place $left$ to desired place and then choose an orientation
(clockwise or counterclockwise) following which we would embed the rest of the
nodes, keeping in mind that $right$ must stay on the highest level. See
Algorithm 3.

Algorithm 3 Left-Right cycle embedding

procedure LeftRightCycleEmbedding($C$, $left$, $right$, $leftImage$)

$h\leftarrow\frac{length(C)}{2}$

Ensure: $number_{left}(right)\in\\{h,h+1,h+2\\}$

$leftLevel\leftarrow level\langle leftImage\rangle$

$leftSide\leftarrow side(leftImage)$

if $(number_{left}(right)=h)\vee(number_{left}(right)=h+1)$ then

for $i\in[h]$ do

Embed $C_{left}[i]\rightarrow level(leftLevel+i-1)[leftSide]$

for $i\in[h]$ do

Embed $C_{left}[h+i]\rightarrow level(leftLevel+h-i)[other(leftSide)]$

else

Embed $left\rightarrow leftImage$

for $i\in[h]$ do

Embed $C_{left}[i+1]\rightarrow level(leftLevel+i-1)[other(leftSide)]$

for $i\in[h-1]$ do

Embed $C_{left}[h+1+i]\rightarrow level(leftLevel+h-i)[leftSide]$

Now, suppose that not all information, such as $right$, $left$, and
$LeftImage$, is provided. We will reduce this problem to the case when the
missing variables are known. Though the subtlety might occur due to the fact
that there are inner edges in the cycle. In this case we choose missing
$left/right$ more precisely in order to embed inner edge vertically. See
Algorithm 4.

Algorithm 4 Cycle embedding

procedure CycleEmbedding($C$, $left$, $right$, $leftImage$)

$h\leftarrow\frac{length(C)}{2}$

if $(left\neq\mathrm{None})\wedge(right\neq\mathrm{None})$ then

Ensure: $number_{left}(right)\in\\{h,h+1,h+2\\}$

if $leftImage=\mathrm{None}$ then

$leftImage\leftarrow level(1)[1]$

if $(left=\mathrm{None})\wedge(right=\mathrm{None})$ then

$left\leftarrow$ arbitrary node of $C$

if $C$ has an inner edge then

Choose $right$ out of $\\{C_{left}[h],C_{left}[h+2]\\}$ to respect the inner
edge

else

Choose $right$ out of $\\{C_{left}[h],C_{left}[h+2]\\}$ arbitrary

else if $(left\neq\mathrm{None})\wedge(right=\mathrm{None})$ then

if $C$ has an inner edge then

Choose $right$ out of $\\{C_{left}[h],C_{left}[h+2]\\}$ to respect the inner
edge

else

Choose $right$ out of $\\{C_{left}[h],C_{left}[h+2]\\}$ arbitrary

else if $(left=\mathrm{None})\wedge(right\neq\mathrm{None})$ then

if $C$ has an inner edge then

Choose $left$ out of $\\{C_{left}[h],C_{left}[h+2]\\}$ to respect the inner
edge

else

Choose $left$ out of $\\{C_{left}[h],C_{left}[h+2]\\}$ arbitrary
LeftRightCycleEmbedding($C$, $left$, $right$, $leftImage$)

####  0.B.1.3 Component embedding

Right now we explain on how to embed onto $Ladder_{N}$ a connectivity
component $S$ that can be embedded onto $Ladder_{n}$.

We start with an algorithm on how to make a cycle-tree decomposition chain of
$S$ assuming no uncompleted frames. To obtain a cycle-tree decomposition of a
graph: 1) we find a maximal cycle; 2) we split the graph into two parts by
logically removing the cycle; 3) we proceed recursively on those parts, and,
finally, 4) we combine the results together maintaining the correct order of
the chain components. See the Algorithm 5.

Algorithm 5 Cycle-Tree decomposition chain

function CycleTreeDecompositionChain($S$)

$S$ has no uncompleted frames

if $S$ is empty then

return $[]$

else if $S$ is a tree then

return $[S]$

else

$C\leftarrow$ arbitrary maximal cycle in $S$

$S_{1},S_{2}\leftarrow$ connectivity components of $S\setminus C$

$C_{1}\leftarrow CycleTreeDecompositionChain(S_{1})$

$C_{2}\leftarrow CycleTreeDecompositionChain(S_{2})$

if $C_{2}$ is empty then

return $[C]+C_{1}$

else

if $\exists u\in V(C_{2}[0]),\ v\in V(C),\ s.t.\ (u,v)\in E(S)$ then

return $C_{1}+[S]+C_{2}$

else

return $C_{2}+[S]+C_{1}$

Now, we describe how to obtain a quasi-correct embedding of $S$. We preprocess
$S$: 1) we remove one edge from cycles of size four; 2) we complete
uncompleted frames with vertical edges. After this preprocessing, we embed
parts of $S$ from the cycle-tree decomposition chain one by one in the
relevant order using the corresponding algorithm (either for a cycle or for a
tree embedding) making sure parts are glued together correctly.

As before, we have additional variables $left$, $right$ and $leftImage$ which
might or might not be given.

6 Connectivity component quasi-correct embedding

procedure Preprocess($S$)

$C\leftarrow$ maximal cycles of length 4 in $S$

for $c\in C$ do

remove arbitrary edge of $c$ from $S$

$F\leftarrow$ cycle frames in $S$

for $f\in F$ do

complete $F$

procedure ComponentEmbeddingLeftFixed($S$, $left$, $right$, $leftImage$)

if $S$ is a tree then

TreeQuasiCorrectEmbedding($S$, $left$, $right$, $leftImage$)

return

if $S$ is a cycle then

CycleEmbedding($S$, $left$, $right$, $leftImage$)

return

Preprocess($S$)

$C\leftarrow CycleTreeDecompositionChain(S)$

if $left\neq\mathrm{None}$ then

Reverse $C$ in the way that $left\in C[1]$

if $right\neq\mathrm{None}$ then

Reverse $C$ in the way that $right\in C[length(C)]$

for $i\in[length(C)]$ do

if $i=1$ then $u,v\leftarrow(u,v)\in E(S)$, s.t. $(u\in V(C[1]))\wedge(v\in
V(C[i+1])$

if $C[1]$ is a tree then

$cur\leftarrow C[1]\cup(u,v)$

TreeQuasiCorrectEmbedding($cur$, $left$, $v$, $leftImage$)

else

CycleEmbedding($C[1]$, $left$, $u$, $leftImage$)

else if $i=length(C)$ then

$u,v\leftarrow(u,v)\in E(S)$, s.t. $(u\in V(C[i-1]))\wedge(v\in V(C[i])$

$leftLevel\leftarrow level\langle u\rangle+1$

$leftSide\leftarrow side(u)$

$localLeftImage\leftarrow level(leftLevel)[leftSide]$

if $C[i]$ is a cycle then

CycleEmbedding($C[i]$, $v$, $right$, $localLeftImage$)

else

TreeQuasiCorrectEmbedding($C[i]$, $v$, $right$, $localLeftImage$)

else

$u_{1},v_{1}\leftarrow(u,v)\in E(S)$, s.t. $(u\in V(C[i-1]))\wedge(v\in
V(C[i])$

$leftLevel\leftarrow level\langle u_{1}\rangle+1$

$leftSide\leftarrow side(u_{1})$

$localLeftImage\leftarrow level(leftLevel)[leftSide]$

$u_{2},v_{2}\leftarrow(u,v)\in E(S)$, s.t. $(u\in V(C[i]))\wedge(v\in
V(C[i+1])$

if $C[i]$ is a cycle then

CycleEmbedding($C[i]$, $v_{1}$, $u_{2}$, $localLeftImage$)

else

$cur\leftarrow C[i]\cup(u_{2},v_{2})$

TreeQuasiCorrcetEmbedding($C[i]$, $v_{1}$, $v_{2}$, $localLeftImage$)

We finally notice that having a procedure to embed a component with a fixed
$leftImage$ it is easy to obtain a procedure which embeds with $rightImage$
fixed. We simply apply the ”$left$” procedure and then flip the result.

Algorithm 7 Component embedding right fixed

procedure ComponentEmbeddingRightFixed($S$, $left$, $right$, $rightImage$)

ComponentEmbeddingLeftFixed($S$, $right$, $left$, $rightImage$)

Flip the image of $S$ over horizontal axis maintaining the position of $right$

###  0.B.2 Dynamic algorithm

We describe how one should change the embedding of the graph after the
processing of a request in an online scenario. At each moment we have some
edges of a $Ladder_{n}$ already revealed forming connectivity components.
After an edge reveal we should reconfigure the target line graph. For that,
instead of line reconfiguration we reconfigure our embedding to $Ladder_{N}$
that is then embedded to the line line by line and introduce some constant
factor. So, we can consider the reconfiguration only of $Ladder_{N}$ and
forget about the target line graph at all. When doing the reconfiguration of
an embedding we want to maintain the following invariants:

  1. 1.

The embedding of any connectivity component is quasi-correct.

  2. 2.

For each tree in the cycle-tree decomposition its embedding respects Septum
invariant 1.

  3. 3.

There are no maximal cycles of length $4$.

  4. 4.

Each cycle frame is completed with all “vertical” edges even if they are not
yet revealed.

  5. 5.

There are no conflicts with cycle nodes, i.e., two nodes of a cycle do not map
to same node of $Ladder_{N}$.

For each newly revealed edge there are two cases: either it connects two nodes
from one connectivity component or not. We are going to discuss both of them.

####  0.B.2.1 Edge in one component

If the new edge is already known or it forms a maximal cycle of length four,
we simply ignore it. Otherwise, it forms a cycle of length at least six, since
two connected nodes are already in one component.

We then perform the following steps:

  1. 1.

Get the completed frame of a (possibly) new cycle.

  2. 2.

Logically “extract” it from the component and embed maintaining the
orientation (not twisting the core that was already embedded in some way).

  3. 3.

Attach two components appeared after an extraction back into the graph,
maintaining their relative order.

Algorithm 8 Process Edge In One Component

procedure ProcessEdgeOneComponent($S$, $(u,v)$)

if Edge $(u,v)$ already exists then

return

if Edge $(u,v)$ forms a maximal cycle of length 4 then

return

$C\leftarrow$ maximal cycle containing $u,v$

$F\leftarrow$ completed frame of $C$

$S_{1},S_{2}\leftarrow$ connectivity components of $S\setminus F$

$u_{1},v_{1}\leftarrow u,v:\ u\in V(F),v\in V(S_{1}),(u,v)\in E(S)$

$u_{2},v_{2}\leftarrow u,v:\ u\in V(F),v\in V(S_{2}),(u,v)\in E(S)$

if $level\langle u_{1}\rangle>level\langle u_{2}\rangle$ then

$Swap(S_{1},S_{2}),\ Swap(u_{1},u_{2}),\ Swap(v_{1},v_{2})$

CycleEmbedding($F$, $u_{1}$, $u_{2}$, $\mathrm{None}$)

ComponentEmbeddingTopFixed($S_{1}$, $\mathrm{None}$, $u_{1}$, $image(u_{1})$)

ComponentEmbeddingBotFixed($S_{2}$, $u_{2}$, $\mathrm{None}$, $image(u_{2})$)

####  0.B.2.2 Edge between two components

In order to obtain an amortization in the cost, we always “move” the smaller
component to the bigger one. Thus, the main question here is how to glue a
component to the existing embedding of another component.

The idea is to consider several cases of where the smaller component will be
connected to the bigger one. There are three possibilities:

  1. 1.

It connects to a cycle node. In this case there are again two possibilities.
Either it “points away” from the bigger component meaning that the cycle to
which we connect is the one of the ends in the cycle-tree decomposition of the
bigger component. Here, we just simply embed it to the end of the cycle-tree
decomposition while possibly rotating a cycle at the end.

Or, the smaller component should be placed somewhere between two cycles in the
cycle-tree decomposition. Here, it can be shown that this small graph should
be a line-graph, and we can simply add it as a whisker, forming a larger
frame.

  2. 2.

It connects to a trunk core node of a tree in the cycle-tree decomposition. It
can be shown that in this case the smaller component again must be a line-
graph. Thus, our only goal is to orient it and possibly two of its inner
simple-graphs neighbours to maintain the Septum invariant 1 for the
corresponding tree from the decomposition.

  3. 3.

It connects to an exit graph node of an end tree of the cycle-tree
decomposition. In this case, we straightforwardly apply a static embedding
algorithm of this tree and the smaller component from scratch. Please, note
that only the exit graphs of the end tree will be moved since the trunk core
and its inner graphs will remain.

9 Process edge between two components

procedure AddInnerWhisker($S$, $C$, $W$, $(u,v)$)

$S\leftarrow S\cup W\cup(u,v)$

$F\leftarrow$ completed frame of $C$

$S_{1},S_{2}\leftarrow$ connectivity components of $S\setminus F$

if $S_{1}$ is embedded above $S_{2}$ then

$Swap(S_{1},S_{2})$

$s_{1},t_{1}\leftarrow s,t:\ s\in V(F),t\in V(S_{1}),(s,t)\in E(S)$

$s_{2},t_{2}\leftarrow s,t:\ s\in V(F),t\in V(S_{2}),(s,t)\in E(S)$

CycleEmbedding($F$, $s_{1}$, $s_{2}$, $\mathrm{None}$)

ComponentEmbeddingTopFixed($S_{1}\cup(s_{1},t_{1})$, $\mathrm{None}$, $s_{1}$,
$image(s_{1})$)

ComponentEmbeddingBotFixed($S_{2}\cup(s_{2},t_{2})$, $s_{2}$, $\mathrm{None}$,
$image(s_{2})$)

procedure ProcessEdgeTwoComponents($S_{1}$, $S_{2}$, $(u,v)$)

Ensure: $u\in V(S_{1}),v\in V(S_{2})$

if $V(S_{1})<V(S_{2})$ then

$Swap(S_{1},S_{2}),\ Swap(u,v)$

$DC_{1}\leftarrow CycleTreeDecomposition(S_{1})$

Reverse $DC_{1}$ in a way $DC[i]$ is embeded under $DC[i+1]\ \forall i$

$A,i\leftarrow DC_{1}[i],i:\ u\in V(DC_{1}[i])$

if $A$ is a cycle then

if $length(DC_{1})=1$ then

if $A$ has an inner edge then

if $u$ is a top node then

$bot\leftarrow$ arbitrary bottom node of $A$

ComponentEmbeddingBotFixed($S_{1}\cup S_{2}\cup(u,v)$, $bot$, $\mathrm{None}$,
$\mathrm{None}$)

else

$top\leftarrow$ arbitrary top node of $A$

ComponentEmbeddingTopFixed($S_{1}\cup S_{2}\cup(u,v)$, $\mathrm{None}$, $top$,
$\mathrm{None}$)

else

ComponentEmbeddingBotFixed($S_{1}\cup S_{2}\cup(u,v)$, $\mathrm{None}$,
$\mathrm{None}$, $\mathrm{None}$)

else if $i=1$ then

$p,q\leftarrow p,q:\ p\in V(DC_{1}[i]),q\in V(DC_{1}[i+1]),(p,q)\in E(S_{1})$

if $(u,p)\in E(S_{1})$ then AddInnerWhisker($S_{1}$, $A$, $S_{2}$, $(u,v)$)

else

if $u$ is not a bottom node of $A$ then

Flip $A$ over diagonal containing $p$

ComponnetEmbeddingTopFixed($S_{2}$, $\mathrm{None}$, $u$, $image(u)$)

else if $i=length(DC_{1})$ then

$p,q\leftarrow p,q:\ p\in V(DC_{1}[i]),q\in V(DC_{1}[i-1]),(p,q)\in E(S_{1})$

if $(u,p)\in E(S_{1})$ then AddInnerWhisker($S_{1}$, $A$, $S_{2}$, $(u,v)$)

else

if $u$ is not a top node of $A$ then

Flip $A$ over diagonal containing $p$

ComponnetEmbeddingBotFixed($S_{2}$, $u$, $\mathrm{None}$, $image(u)$)

elseAddInnerWhisker($S_{1}$, $A$, $S_{2}$, $(u,v)$)

if $A$ is a tree then

if $u\in$ extended trunk core of $A$ then

Embed $v\rightarrow opposite(u)$

$l_{1},l_{2}\leftarrow$ $u$ neighbouring inner simple-graphs

Orient $S_{2},l_{1},l_{2}$ to maintain Septum invariant in $A$

else if $u\in$ inner simple-graph then

$S_{1}\leftarrow S_{1}\cup S_{2}\cup(u,v)$

$l\leftarrow$ inner simple graph containing $u$

Orient $l$ to maintain Septum invariant in $A$

else if $u\in$ exit-graph then

if $i=1$ then

if $length(DC_{1})=1$ then

$p\leftarrow$ arbitrary highest node of $S_{1}$

$q\leftarrow$ additional temporary node

else

$p,q\leftarrow p,q:\ p\in V(DC_{1}[i]),q\in V(DC_{1}[i+1]),(p,q)\in E(S_{1})$

ComponentEmbeddingTopFixed($A\cup S_{2}\cup(p,q)$, $\mathrm{None}$, $q$,
$image(q)$)

else if $i=length(DC_{1})$ then

$p,q\leftarrow p,q:\ p\in V(DC_{1}[i]),q\in V(DC_{1}[i-1]),(p,q)\in E(S_{1})$

ComponentEmbeddingBotFixed($A\cup S_{2}\cup(p,q)$, $q$, $\mathrm{None}$,
$image(q)$)

##  Appendix 0.C Proofs and Analysis

###  0.C.1 Strategy

At the very beginning there are no requests and we don’t know any request-
edges. Requests come one at a time, possibly, revealing new edges. Known edges
form connectivity components which are all subgraphs of the request graph. Our
strategy would be to maintain such enumeration $\sigma$ of vertices that for
each connectivity component $S$

$\displaystyle\max\limits_{(u,v)\in E(S)}|\sigma(u)-\sigma(v)|\leq 12$ (1)

We call this property of an enumeration the proximity property.

So, if we receive the request which was already known, we do nothing since the
property persists. But if the new edge comes, we might perform a re-
enumeration $\sigma$ on the vertices to maintain the property.

###  0.C.2 Bandwidth of subgraphs

###### Definition 17

Consider two connected graphs $S$ and $G$. The correct embedding of $S$ into
$G$ is a mapping $\varphi:V(S)\rightarrow V(G)$ such that:

  * •

$\varphi$ is injective

  * •

$(u,v)\in E(S)\rightarrow(\varphi(u),\varphi(v))\in E(G)$

If $\varphi$ is not injective, i.e. there are nodes $u,v$, s.t.
$\varphi(u)=\varphi(v)$, we say that there is a conflict between $u$ and $v$.

###### Lemma 2

For each subgraph $S$ of a graph $G$,
$\mathrm{Bandwidth}(S)\leq\mathrm{Bandwidth}(G)$.

###### Proof

Let $\varphi$ be a correct embedding of $S$ into $G$. And let $\sigma$ be the
enumeration on $G$ with which the $bandwidth(G)$ is achieved.

Let $U$ be the finite set of unique natural numbers. For $v\in U$ we define
$ord_{U}(v)=|\\{u\mid u\in U,u\leq v\\}|$.

We now define the enumeration $\sigma_{S}$ of $S$ as follows:

$\displaystyle U=\\{\sigma(\varphi(v))\mid v\in S\\}$
$\displaystyle\sigma_{S}(v)=ord_{U}(\sigma(\varphi(v)))$

We state that $\max\limits_{(u,v)\in E(S)}|\sigma_{S}(u)-\sigma_{S}(v)|\leq
bandwidth(G)$. This follows from two facts:

  * •

For every $(u,v)\in E(S)$

$\displaystyle|\sigma(\varphi(u))-\sigma(\varphi(v))|\leq bandwidth(G)$

since $(\varphi(u),\varphi(v))\in E(G)$

  * •

If U is a set of unique natural numbers than for every $u,v\in U$

$\displaystyle|ord_{U}(u)-ord_{U}(v)|\leq|u-v|$

Then, for each edge $(u,v)\in E(S)$ we get the following inequalities:

$\displaystyle|\sigma_{S}(u)-\sigma_{S}(v)|=|ord_{U}(\sigma(\varphi(u)))-ord_{U}(\sigma(\varphi(v)))|$
$\displaystyle\leq|\sigma(\varphi(u))-\sigma(\varphi(v))|\leq bandwidth(G)$

We know that all the graphs that appear during the requests processing
(revealing the edges) are subgraphs of $Ladder_{n}$. Thus, by Lemma 2 we
conclude that their $bandwidth\leq 2$. And we can use the embedding function
from this Lemma to enumerate each subgraph $S$ of $Ladder_{n}$ with
$\sigma_{S}$.

###### Remark 1

We do not need to worry about the top and bottom bounds of $Ladder_{n}$ when
performing an embedding. In fact, we can perform an embedding of $S$ into the
$Ladder_{\infty}$ and, since $S$ is connected and the embedding preserves
connectivity, the whole image of $S$ will be within some $Ladder_{m}$ (for
$m\geq n$) which is enough to obtain a requested $bandwidth\leq 2$.

###  0.C.3 Connectivity component structure

Requests come with time possibly revealing new edges of a request graph and
forming connectivity components which are subgraphs of the request graph.

One connectivity component can be decomposed into cycles and trees. Let us now
provide some statements about tree and cycle embedding.

Tree embedding

###### Definition 6

Consider some correct embedding $\varphi$ of a tree $T$ into $Ladder_{n}$. Let
$r=\arg\max\limits_{v\in V(T)}level\langle\varphi(v)\rangle$ be the
“rightmost” node of the embedding and
$l=\arg\min\limits_{v\in V(T)}level\langle\varphi(v)\rangle$ be the “leftmost”
node of the embedding. The trunk of $T$ is a path in $T$ connecting $l$ and
$r$. The trunk of a tree $T$ for the embedding $\varphi$ is denoted with
$trunk_{\varphi}(T)$.

###### Definition 7

Let $T$ be a tree and $\varphi$ be its correct embedding into $Ladder_{n}$.
The level $i$ of $Ladder_{n}$ is called _occupied_ if there is a vertex $v\in
V(T):\ \varphi(v)\in level_{Ladder_{n}}(i)$.

###### Statement 1

For every occupied level $i$ there is $v\in trunk_{\varphi}(T)$ such that
$v\in level(i)$.

###### Proof

By the definition of the trunk, an image goes from the minimal occupied level
to the maximal. It cannot skip a level since the trunk is connected and the
correct embedding preserves connectivity.

The trunk of a tree in an embedding is an useful concept to define since the
following holds for it.

###### Lemma 4

Let $T$ be a tree correctly embedded into $Ladder_{n}$ by some embedding
$\varphi$. Then, all the connected components in $T\setminus
trunk_{\varphi}(T)$ are line-graphs.

###### Proof

Suppose that it is not true and then there should exist a subgraph $S$ of $T$
such that $V(S)\cap V(trunk_{\varphi}(T))=\emptyset$ and $S$ contains a node
of degree three. Since there is a node of degree three in $S$ we can state
that there are two nodes of $S$, say $u$ and $v$ with the same level
($level\langle\varphi(v)\rangle=level\langle\varphi(u)\rangle$). But the image
of the tree trunk passes through all occupied levels of the grid by Statement
1. Hence, either $u$ or $v$ $\in trunk_{\varphi}(T)$ which contradicts the
assumption.

The bad thing about the trunk is that it depends on the embedding. And there
can be several correct embeddings of the same tree giving different trunks.
So, we introduce the concept of a trunk core which alleviates this issue. But
at first, we prove some technical statements.

###### Statement 2

For the tree $T$, disregarding the correct embedding $\varphi$, the
$trunk_{\varphi}(T)$ must pass through a node of degree three if it has no
neighbours of degree three. If there are two adjacent nodes with degree three,
the trunk must pass through at least one of them.

###### Proof

First, consider the case of a node with no neighbours of degree three. Let’s
call it $a$. To prove by contradiction we assume that the trunk does not pass
through $a$. Let’s call $a$-s neighbours $b,c$ and $d$. W.l.o.g assume that

$\displaystyle\varphi(a)=level(i)[1]$ (2)
$\displaystyle\varphi(b)=level(i-1)[1]$ (3)
$\displaystyle\varphi(c)=level(i)[2]$ (4)
$\displaystyle\varphi(d)=level(i+1)[1]$ (5)

Since the trunk does not pass through $a$ and by Statement 1 it passes through
the level $i$ it should pass through $c$. If $c$ has degree one, the trunk
contains one node from level $i$, and does not contain any node from $i+1$,
thus, this trunk cannot contain the topmost node. If $c$ has degree two, we
say that its second neighbour is mapped to $level(i-1)[2]$. The case when it
is mapped to $level(i+1)[2]$ is symmetric. But then trunk does not pass
through the $i+1$ level which contradicts the Statement 1.

Now, coming to the case with two adjacent nodes of degree three, we have two
adjacent nodes $a$ and $b$ of degree three. And let $c,d$ be the rest
neighbours of $a$ and $e,f$ be the rest neighbours of $b$. If $a$ and $b$ are
embedded to the same level, then by Statement 1 the trunk passes through at
least one of them. Suppose now that $a$ and $b$ are on different levels, say

$\displaystyle\varphi(a)=level(i)[1]$ (6)
$\displaystyle\varphi(b)=level(i+1)[1]$ (7)
$\displaystyle\varphi(c)=level(i)[2]$ (8)
$\displaystyle\varphi(d)=level(i-1)[2]$ (9)
$\displaystyle\varphi(e)=level(i+1)[2]$ (10)
$\displaystyle\varphi(f)=level(i+2)[1]$ (11)

Since the edge $(a,b)$ is a bridge between two connected components of a tree
and the trunk contains nodes form both components the trunk should pass
through the edge $(a,b)$, so it passes through both $a$ and $b$.

###### Lemma 5

For the tree $T$ for each node $v$ of degree three (except for maximum two of
them) we can verify in polynomial time if for any correct embedding $\varphi$
$trunk_{\varphi}(T)$ passes through $v$ or not.

###### Proof

We call a pair of adjacent nodes of degree three _“paired”_ nodes. We call a
node of degree three with no neighbours of degree three _“single”_.

If the tree contains not more than two nodes of degree three, the statement is
trivial. So, we suppose that there exist at least three nodes of degree three.

The trunk passes through the single nodes by Statement 2. Thus we are
interested in paired nodes. Consider such pair. Let’s call its nodes $a$ and
$b$. By the Statement 2 we know that either $a$ or $b$ is in the trunk.

By the assumption there exist either another single node or other paired
nodes. If there is a single node, let’s call it $c$, we know that it is in the
trunk. $c$ is reachable from $a$ and $b$ and since we have tree either $a$ is
on path from $b$ to $c$ or $b$ is on path from $a$ to $c$. W.l.o.g. assume $b$
is on a path from $a$ to $c$. But this implies that $b$ is in the trunk,
because if not, $a$ is, and, thus, there are two paths from $a$ to $c$ — the
trunk and the one containing $b$. Thus, we have a cycle, which is impossible
since we have a tree.

If there are no single nodes, there are paired nodes. We denote them with $u$
and $v$. $u$ and $v$ are reachable from $a$, thus, w.l.o.g. we can assume that
$u$ is on the path from $a$ to $v$. If now $b$ is on the path from $a$ to $u$,
we have the following: $a\rightarrow b\rightsquigarrow u\rightarrow v$. By
Statement 2 we know that the trunk must pass through either $u$ or $v$. Denote
the one the trunk passes through with $c$. We can reduce this case to the
previous one, if we take any $c=u$ or $c=v$. Applying the same reasoning we
deduce that $b$ must be in the trunk.

_Support nodes_ are the nodes of two types: either it is a single node, or it
is a node that is located on the path between two other nodes with degree
three. This Lemma shows that the support nodes appear in the trunk of every
correct embedding.

We make a path $P$ through support nodes. For any inner node of this path
which is paired there is no chance for its pair to be in a trunk if it is not
in $P$ already, because the trunk is a path. So, the only uncertainty remains
about at most one node in the pairs of end nodes.

###### Definition 18

Path $P$ constructed in Lemma 5 is called _trunk core_. We denote this path
for a tree $T$ as $trunkCore(T)$. Note that it can be embedded into
$Ladder_{n}$.

###### Definition 19

The embedding $\varphi$ of a line-graph $l$ on the grid is called monotone if
the nodes $\varphi(l[i])$ and $\varphi(l[j])$ are on the same level of the
grid only when they are adjacent on $T$.

###### Lemma 9

If a line graph is embedded preserving edges into $Ladder_{n}$ with no self-
intersections non-monotonically then one of the end-points shares a level with
a node of a path it is not adjacent with.

###### Proof

Denote a line graph $l$. Let’s say $i$ is the smallest index such that $l[i]$
shares level with some other non-adjacent node $l[j]$, $|i-j|>1$. W.l.o.g.
let’s assume that $l[i]$ is embedded to $level(k)[1]$. Since $i$ was chosen
the smallest $j>i$. Let us assume that $l[i-1]$ is embedded to
$level(k-1)[1]$. Then, since $l[j]$ is embedded to $level(k)[2]$, $l[i+1]$ is
embedded into $level(k+1)[1]$. We also state that $l[j-1]$ is embedded to
$level(k+1)[2]$, since if it is embedded into $level(k-1)[2]$, the path should
go from $l[i+1]$ to $l[j-1]$ (note that $i+1<j-1$) without passing through
level $k$ which is impossible. So we have the following embeddings:

$\displaystyle l[i]\rightarrow level(k)[1]$ (12) $\displaystyle
l[i-1]\rightarrow level(k-1)[1]$ (13) $\displaystyle l[j]\rightarrow
level(k)[2]$ (14) $\displaystyle l[j+1]\rightarrow level(k-1)[2]$ (15)

It is easy to see that $l[j+2]$ has no other options but to be embedded to
$level(k-2)[2]$. But then $l[i-3]$ should be embedded to $level(k-3)[1]$ and
so on $l[j+t]\rightarrow level(k-t)[2]$ and $l[i-t]\rightarrow level(k-t)[2]$
in general. We now take $t=\min(i-1,length(p)-j)$ so either $l[i-t]$ or
$l[j+t]$ is an end nodes and they both exist. They share level, so the lemma
is proved.

###### Lemma 10

The trunk core of a tree $T$ is always embedded in the monotone manner.

###### Proof

Trunk core connects nodes of degree three which cannot be embedded with any
other nodes of the trunk to the same level since then either a cycle appears
or we obtain a conflict. Thus, by the Lemma 9 trunk core must be embedded
monotonically.

From now on we assume that every mentioned tree can be embedded into the
$Ladder_{n}$.

###### Definition 20

Let $T$ be a tree. All the connectivity components in
$T\,\setminus\,trunkCore(T)$ are called _simple-graphs_ of tree $T$.

###### Lemma 6

Simple-graphs of a tree $T$ are line-graphs.

###### Proof

Note that all the nodes of degree three in $T$ are either in the trunk core or
they are adjacent to the trunk core. Hence after removing the nodes of the
trunk core no nodes of degree three are left and, thus, all the graphs left
are line-graphs.

###### Definition 9

The edge between a simple-graph and the trunk core is called a _leg_.

The end of a leg in the simple-graph is called a _head_ of the simple-graph.

The end of a leg in the trunk core is called a _foot_ of the simple-graph.

If you remove the head of a simple-graph and it falls apart into two connected
components, such simple-graph is called _two-handed_ and those parts are
called its _hands_. Otherwise, the graph is called _one-handed_ , and the sole
remaining component is called a _hand_. If there are no nodes in the simple-
graph but just a head it is called zero-handed.

###### Definition 10

A simple-graph connected to the end nodes of the trunk core is called _exit-
graph_.

###### Definition 10

A simple-graphs connected to the inner nodes of the trunk core is called
_inner-graph_.

Please note that the next definition is about a much larger ladder
$Ladder_{N}$ rather than $Ladder_{n}$. $N$ should be approximately equal to
$2\cdot n$.

###### Definition 11

An embedding $\varphi:V(G)\rightarrow V(Ladder_{N})$ of a graph $G$ into
$Ladder_{N}$ is called _quasi-correct_ if:

  * •

$(u,v)\in E(G)\Rightarrow(\varphi(u),\varphi(v))\in E(Ladder_{N})$, i.e.,
images of adjacent vertices in $G$ are adjacent in the grid.

  * •

There are no more than three nodes mapped into each level of $Ladder_{N}$,
i.e., the two grid nodes on each level are the images of no more than three
nodes.

We might think of a quasi-correct embedding as an embedding into levels of the
grid with no more than three nodes embedded to the same level. We then can
compose this embedding with an embedding of a grid into the line which is the
enumeration level by level. More formally if a node $u$ is embedded to the
level $i$ and a node $v$ is embedded to the level $j$ and $i<j$ then the
resulting number of $u$ on the line is smaller then the number of $v$, but if
two nodes are embedded to the same level, we give no guarantee.

###### Lemma 7

For any graph mapped into the ladder graph by the quasi-correct embedding as
described above can be mapped onto the line level by level with the property
that any pair of adjacent nodes are embedded at the distance of at most five.

###### Proof

Since two adjacent vertices are embedded to the levels with a number
difference of at most 1, we can state that there are no more than 4 nodes
between them in the line, since there are no more than 3 nodes per level.

####  0.C.3.1 Tree embedding strategy

We start with the discussion on how to embed a tree with
$|V(trunkCore(T))|\leq 1$. Such tree can have $\leq 3$ nodes of degree three,
since, otherwise, there are at least four nodes of degree three and the trunk
core has at least two nodes:

  * •

$\geq 2$ single nodes. In this case, they are both in the trunk core.

  * •

at least one single node and at least one paired nodes. In this case, one node
from a pair and a single node are in the trunk core.

  * •

at least two disjoint paired nodes. In this case, for each pair we know for
certain the member who is in the trunk, thus we again have at least two nodes
in the trunk core.

Further, we analyse the cases depending on the number of nodes of degree
three. We need the following technical Lemma.

###### Lemma 10

If there is a tree with three nodes of degree three $a$, $b$, and $c$ and
there are edges $(a,b)$ and $(b,c)$, then the third neighbour of $b$ is of
degree one and for any correct embedding $a$, $b$, and $c$ are embedded to the
different levels.

###### Proof

Consider a correct embedding $\varphi$. Say $\varphi(b)=level(i)[1]$. If now
$\varphi(a)=level(i)[2]$, both $level(i+1)[2]$ and $level(i-1)[2]$ are
occupied by neighbours of $a$, so no matter where we embed $c$, say to
$level(i+1)[1]$ there would be only one spare slot, $level(i+2)[1]$ in this
case, for two neighbours of $c$. Recall that we have a tree so $a$ and $c$
can’t share more then one neighbour.

So the only possible embedding up to the symmetry is

$\displaystyle\begin{cases}\varphi(b)=level(i)[1]\\\
\varphi(a)=level(i-1)[1]\\\ \varphi(c)=level(i+1)[1]\\\ \end{cases}$ (16)

In this case $level(i\pm 1)[2]$ are occupied by neighbours of $a$ and $c$, so
the third neighbour of $b$ cannot have any neighbours except for $b$ since
there is no place for them.

Now, we consider the possible cases for the amount of nodes with degree three.

  * •

There are no nodes of degree three. In this case our tree is just a line-graph
$l$ and we embed it the following way:

$\displaystyle\varphi:V(l)\rightarrow Ladder_{n}$ (17)
$\displaystyle\varphi(l[i])=level(i)[1]$ (18)

Remember that right now we allow to choose any $n$, arbitrary large.

  * •

There is one node of degree three. We can think of it as two line graphs
$l_{1}$ and $l_{2}$ with additional edge $(l_{1}[i],l_{2}[1])$ for some $i$.
We embed the tree in the following way:

$\displaystyle\varphi:V(l_{1})\cup V(l_{2})\rightarrow Ladder_{n}$ (19)
$\displaystyle\varphi(l_{1}[j])=level(j)[1]$ (20)
$\displaystyle\varphi(l_{2}[j])=level(i+j-1)[2]$ (21)

  * •

There are two nodes of degree three. Since $|V(trunkCore(T)|\leq 1$, we
conclude that those two nodes are paired, since otherwise they would be single
nodes and therefore be in the trunk core by Lemma 5. So, in this case we can
present $T$ as two line-graphs $l_{1}$ and $l_{2}$ with additional edge
$(l_{1}[i],l_{2}[j])$ for some $i$ and $j$. We embed $T$ in the following way:

$\displaystyle\varphi:V(l_{1})\cup V(l_{2})\rightarrow Ladder_{n}$ (22)
$\displaystyle\varphi(l_{1}[k])=level(k)[1]$ (23)
$\displaystyle\varphi(l_{2}[k])=level(i+k-j)[2]$ (24)

  * •

There are three nodes of degree three. Since $|V(trunkCore(T)|\leq 1$, we
conclude that there is no single node, otherwise, it is in the trunk core and
one of the other two is also in the trunk core, contradicting the assumption.

So, with our three nodes of degree three, say $a$, $b$ and $c$ we must have
edges $(a,b)$ and $(b,c)$. By the Lemma 10 none of $a,b,c$ can be embedded
into the same level, and the third neighbour of $b$ is of degree one. Denote
the line-graphs connected to $a$ with $l^{1}_{a}$ and $l^{2}_{a}$ (they are
line-graphs since we have only three nodes of degree three) and the line-
graphs connected to $c$ with $l^{1}_{c}$ and $l^{2}_{c}$. Denote the third
neighbour of $b$ with $d$. We embed as follows:

$\displaystyle\varphi(b)=level(2)[1]$ (25)
$\displaystyle\varphi(d)=level(2)[2]$ (26)
$\displaystyle\varphi(a)=level(1)[1]$ (27)
$\displaystyle\varphi(c)=level(3)[1]$ (28)
$\displaystyle\varphi(l^{1}_{a}[i])=level(1-i)[1]$ (29)
$\displaystyle\varphi(l^{2}_{a}[i])=level(2-i)[2]$ (30)
$\displaystyle\varphi(l^{1}_{c}[i])=level(3+i)[1]$ (31)
$\displaystyle\varphi(l^{2}_{c}[i])=level(2+i)[2]$ (32)

  * •

There are no other cases, since we showed that if there are four nodes with
degree three then the size of the trunk core should be bigger than one.

Now, we discuss how to embed a more generic tree with $|V(trunkCore(T))|\geq
2$ into the grid. We call our embedding as $\tilde{\varphi}$.

  1. 1.

$\tilde{\varphi}(trunkCore(T)[i])=level(i)[1]$

  2. 2.

Suppose $l$ is a simple-graph connected to the inner node with number $i$ of
the trunk core by its $j$-th node, so the leg of $l$ is $(trunkCore[i],l[j])$.
We embed $l[j]$ to the opposite of $trunkCore[i]$, i.e.
$\tilde{\varphi}(l[j])=level(i)[2]$.

We also want to reserve nodes $level(|V(trunkCore(T))|)[2]$ and $level(1)[2]$
for exit-graphs, so we say we embed phantom nodes there for algorithm not to
use them on Step 3.

  3. 3.

We now want to embed hands of simple-graphs connected to the inner trunk core
nodes. Suppose we have such simple graph $l$ and we’ve embedded its head to
$level(i)[2]$ on Step 2.

If $l$ is zero-handed, it is already embedded on Step 2.

If $l$ is two-handed, denote its hands with $h_{1}$ and $h_{2}$ and choose the
one of embeddings from

$\displaystyle\left[\begin{array}[]{c}\begin{cases}\tilde{\varphi}(h_{1}[j])=level(i+j)[2]\\\
\tilde{\varphi}(h_{2}[j])=level(i-j)[2]\\\ \end{cases}\\\
\begin{cases}\tilde{\varphi}(h_{1}[j])=level(i-j)[2]\\\
\tilde{\varphi}(h_{2}[j])=level(i+j)[2]\\\ \end{cases}\end{array}\right.$ (35)

which does not map nodes from $V(h_{1})\cup V(h_{2})$ to the place nodes were
mapped to on step 2.

If $l$ is one-handed, denote its hand with $h$ and consider two cases:

     * •

$\displaystyle\begin{cases}trunkCore(T)[i+1]\ \parbox[t]{260.17464pt}{is an
inner node and it is a foot of another\newline one-handed or zero-handed
simple-graph $l_{2}$\newline with hand (possibly empty) $h_{2}$}\\\
m(h[j])=level(i-j)[2]\ \parbox[t]{260.17464pt}{ maps some nodes of $h$ to the
place\newline where nodes were placed on step 2}\end{cases}$ (36)

In this case we define $\tilde{\varphi}$ for $l$ and $l_{2}$ at a time the
following way:

$\displaystyle\begin{cases}\tilde{\varphi}(h[j])=level(i+j)[2]\\\
\tilde{\varphi}(h_{2}[j])=level(i+1-j)[2]\end{cases}$ (38)

     * •

The symmetric case is when

$\displaystyle\begin{cases}trunkCore(T)[i-1]\ \parbox[t]{260.17464pt}{is an
inner node and it is a foot of another\newline one-handed or zero-handed
simple-graph $l_{2}$\newline with hand (possibly empty) $h_{2}$}\\\
m(h[j])=level(i+j)[2]\ \parbox[t]{260.17464pt}{ maps some nodes of $h$ to the
place\newline where nodes were placed on step 2}\end{cases}$ (39)

In this case we define $\tilde{\varphi}$ for $l$ and $l_{2}$ at a time the
following way:

$\displaystyle\begin{cases}\tilde{\varphi}(h[j])=level(i-j)[2]\\\
\tilde{\varphi}(h_{2}[j])=level(i-1+j)[2]\end{cases}$ (41)

     * •

If the previous two cases don’t come true we act pretty much the similar as we
did for two-handed simple-graph, namely denote hand of $l$ with $h$ and choose
one of the following definitions of $\tilde{\varphi}$ which doesn’t map nodes
of $h$ to the places already used on step 2:

$\displaystyle\left[\begin{array}[]{c}\tilde{\varphi}(h[j])=level(i+j)[2]\\\
\tilde{\varphi}(h[j])=level(i-j)[2]\end{array}\right.$ (44)

  4. 4.

The last case is to consider an exit-graph.

Denote the end-node of the trunk core, to which the exit-graph is connected by
$i$. $i$ is either $|V(trunkCore(T))|$ or $1$.

     * •

If $i=|V(trunkCore(T))|$. There are two line-graphs connected to $i$, say
$l_{1}$ and $l_{2}$. Note that they can’t both be two-handed, since that means
we have three nodes of degree three in a row, the middle one is the end node
of the trunk core, but then the middle one by Lemma 10 must have the third
neighbour of degree one which is not the case since it is a trunk core node
and trunk core nodes are all of degree $\geq 2$.

So let’s assume that $l_{1}$ is one-handed. We embed it with

$\displaystyle\tilde{\varphi}(l_{1}[j])=level(i+j)[1]$ (45)

If $l_{2}$ is one-handed we embed it with

$\displaystyle\tilde{\varphi}(l_{2}[j])=level(i+j-1)[2]$ (46)

If $l_{2}$ instead has two hands $h_{1}$ and $h_{2}$ and it connects to $i$
with the node $l_{2}[j]$. Then we define

$\displaystyle\tilde{\varphi}(l_{2}[j])=level(i)[2]$ (47)
$\displaystyle\tilde{\varphi}(h_{1}[k])=level(i+k)[2]$ (48)
$\displaystyle\tilde{\varphi}(h_{2}[k])=level(i+k)[2]$ (49)

     * •

If $i=1$ we do everything symmetrically. Remember we don’t care if we go out
$Ladder_{n}$ top or bottom borders, if it happens, we can just enlarge our
grid to $Ladder_{m}$ for some large enough $m$ to accommodate the image.

###### Definition 21

The definition of $\varphi$ on the hand(s) of the simple-graph connected to
the inner trunk core node is called the orientation of that simple-graph.

###### Definition 22

We say that two inner simple-graphs are neighbours if there are no other
simple-graphs connected to the trunk core in between their foots.

###### Lemma 11

The resulting embedding of this strategy exists and it is quasi-correct.

Before diving into prove let us discuss what does the Lemma give to us. There
are three key points about the described quasi-correct embedding.

First of all, we should emphasise that such embedding can be efficiently
computed.

Not only that, but it also can be recomputed easily while remaining quasi-
correctness when the new vertices come, which is relevant to the online
scenario.

And last but not least, recall that each two adjacent nodes are embedded at
the distance at most five (see Lemma 7) so we are not worried about serving
the same request many times.

###### Proof

The lemma is obvious for the trees with $|V(trunkCore(T))|\leq 1$, since we
can do a correct embedding.

Denote the resulting embedding with $\tilde{\varphi}$. We know that a correct
embedding exists, denote it $\varphi$.

  * •

The described embedding of the trunk core meets no constraints, so it always
exists.

  * •

Let $top:=|V(trunkCore(T))|$.

The described embedding of the exit-graphs does not have any constraints, so
it exists. Let us now focus on the exit-graphs connected to
$trunkCore(T)[top]$. For each node $u$ of those exit-graphs it is true that
$\tilde{\varphi}(u)$ is on the $level(top)$ or higher. There are no more than
three nodes of exit-graphs per level. Simple-graphs connected to the inner
trunk core nodes are not allowed to pass through $level(top)$, so since they
are connected, no nodes from simple graphs are embedded into levels $\geq
top$. There are no nodes of the trunk core higher than $top$ and on
$level(top)$ there are only one node from our exit-graphs. The exit graphs
connected to the $trunkCore(T)[1]$ are all embedded to the levels $\leq 1$, so
they can’t interfere with the exit-graphs connected to the
$trunkCore(T)[top]$. Thus we conclude that nodes of exit-graphs connected to
the $trunkCore(T)[top]$ do not violate quasi-correctness since there are no
more than three nodes on their levels. The same for the exit-graphs connected
to the $trunkCore(T)[1]$.

  * •

Now to the two-handed inner simple-graphs. The leg of each such simple-graph
for any correct embedding must be embedded horizontally, i.e. $\varphi(foot)$
and $\varphi(head)$ must be on the same level. This is since we know that the
trunk core image is monotone by Lemma 10 and it can’t be if $\varphi(foot)$
and $\varphi(head)$ are on the different levels:

Say $\varphi(foot)=level(i)[1]$ and $\varphi(head)=level(i+1)[1]$. Then
$level(i+1)[2]$ and $level(i+2)[1]$ are occupied by $head$ neighbours since it
is of degree three. The $foot$ is also of degree three because it is an inner
trunk core node with a simple-graph connected to it. Thus $level(i-1)[1]$ and
$level(i)[2]$ are occupied with its neighbours, trunk core nodes. But the node
mapped to $level(i)[2]$ can’t be the end node of the trunk core since then it
is of degree three and the node mapped to $level(i+1)[2]$ is its neighbour
thus we obtain a cycle
$\varphi^{-1}(\\{level(i)[1],level(i+1)[1],level(i+1)[2],level(i)[2]\\})$. So
there is another trunk core node after it and it is inevitably mapped to
$level(i-1)[2]$ violating monotone property of the trunk core embedding.

Now denote the hands of our two-handed graph with $h_{1}$ and $h_{2}$ and
let’s say that $\varphi(foot)=level(i)[1],\ \varphi(head)=level(i)[2]$ and
$\varphi(h_{1}[1])=level(i+1)[2]$. Then $\varphi(h_{1}[2])$ must be
$level(i+2)[2]$ since $level(i+1)[1]$ is occupied by the $foot$ trunk core
neighbour $next$ (remember $foot$ is inner). If now $next$ is of degree three
we obtain a conflict or a cycle, since $next^{\prime}s$ neighbour occupies
$level(i+2)[2]$. If not, $next$ is an inner trunk core node and we continue
with the $level(i+3)[2]$ for the $h_{1}[3]$ and $level(i+3)[1]$ for the next
trunk core node of $next$. So we do until we ran out of $h_{1}$ nodes. We now
say that there are no nodes of degree three in

$\displaystyle\\{trunkCore(T)[i+j]\mid j\in[|V(h_{1})|]\\}$ (50)

since if there is $j$ such that $trunkCore(T)[i+j]$ is of degree three, we
obtain a conflict between the third neighbour of $trunkCore(T)[i+j]$ and
$h_{1}[j]$. That means that $\tilde{\varphi}(h_{1}[j])=level(i+j)$ will not
place a node to the slot already occupied on step 2 of the strategy. The same
for $h_{2}$. We call this line of reasoning the inductive argument.

So we proved that for each two-handed simple-graph connected to the inner node
of a trunk core one of its orientations will not face conflicts with a
neighbours of a trunk core nodes of degree three. Or in other words two-handed
inner graphs can’t violate the existence of the described embedding.

  * •

We’ve shown that the quasi-correctness can’t be violated on the levels $\geq
top$ and $\leq 1$. So now we need to proof that it is not violated in between.

To violate the quasi-correctness we need to obtain at least four nodes per
level. Since on each level between $top$ and $1$ there is a node from the
trunk core and there are no nodes from exit-graphs we conclude that there must
be at least three nodes of an inner-simple graphs. And note also that they
must be from the different simple-graphs since we don’t embed more than one
node from one inner simple-graph per level. Denote those simple-graphs with
$a,b,c$. Their foots are somehow ordered in the trunk core, say $foot(b)$ is
between $foot(a)$ and $foot(c)$. Since simple-graphs hands conflict at some
node, we conclude that either hand of $a$ crosses the $head(b)$ or a hand of
$c$ crosses the $head(b)$, otherwise $a$ and $c$ just don’t share nodes.
W.l.o.g. hand of $a$ crosses $head(b)$. But this is only possible when $b$ and
$a$ are one-handed graphs with adjacent foots and in this case their hands are
oriented contrary and they only have two conflicts: $hand(a)[1]$ is embedded
to the same node as $head(b)$ and $hand(b)[1]$ is embedded to the same node as
$head(a)$. So $c$ can possibly participate in that conflict only if $c$ is a
one-handed graph with a foot adjacent to $foot(b)$. That is because by our
strategy two-handed simple-graphs do not cross other simple-graphs heads at
all and the one-handed do only if their foots are adjacent. Our goal now is to
show that in such setting $c$ can be oriented the other direction to avoid
conflict with $b$.

Note that we have three nodes of degree three and edges
$(foot(a),foot(b))$, $(foot(b),foot(c))$. This is exactly the statement of
Lemma 10, so we conclude that we have the following structure up to symmetry:

$\displaystyle\varphi(foot(b))=level(i)[1]$ (51)
$\displaystyle\varphi(foot(a))=level(i-1)[1]$ (52)
$\displaystyle\varphi(foot(c))=level(i+1)[1]$ (53)
$\displaystyle\varphi(head(b))=level(i)[2]$ (54)

and we know that $b$ in fact consists of one node.

We still have two possibilities for $head(c)$, namely $level(i+1)[2]$ or
$level(i+2)[1]$.

If $\varphi(head(c))=level(i+1)[2]$, then $\varphi(c[2])=level(i+2)[2]$ and by
the inductive argument applied to the $hand(c)$ there are no nodes of degree
three in

$\displaystyle\\{trunkCore(T)[i+1+j]\mid j\in[|V(hand(c))|]\\}$ (56)

so

$\displaystyle\tilde{\varphi}(hand(c)[j])=level(i+1+j)[2]$ (57)

won’t place nodes of $c$ to the slots already occupied on step 2 of the
strategy.

If on the other hand $\varphi(head(c))=level(i+2)[1]$ then
$\varphi(trunkCore(i+2))$ must be $level(i+1)[2]$. Thus $trunkCore(i+2)$ can’t
be the end of the trunk core since then it is of degree three but
$level(i)[2]$ is occupied by $head(b)$. So we say that $trunkCore(i+3)$ exists
and $\varphi(trunkCore(i+3))=level(i+2)[2]$ and it is also not the end node
since it can’t be of degree three since $level(i+2)[1]$ is occupied by the
assumption by the $head(c)$. We now apply the inductive argument obtaining
that there are no nodes of degree three in

$\displaystyle\\{trunkCore(T)[i+2+j]\mid j\in[|V(c)|]\\}$ (58)

We also showed that $trunkCore(T)[i+2]$ is not of degree three, so we state
that $\tilde{\varphi}(hand(c)[j])=level(i+1+j)$ won’t place nodes of $c$ to
the slots already occupied on step 2 of the strategy.

This completes the proof of quasi-correctness of the embedding.

  * •

So the last thing to show is that the described embedding exists for one-
handed inner graphs.

Suppose we have a one-handed inner graph $l$ with hand $h$ connected to the
$i$-th node of the trunk core. Suppose also that w.l.o.g.
$\varphi(foot(l))=level(i)[1]$. The only constrainted case in our strategy is
when the following doesn’t hold:

$\displaystyle\left[\begin{array}[]{c c}\begin{cases}trunkCore(T)[i+1]\
\parbox[t]{173.44534pt}{is an inner node and it is a foot of another one-
handed or zero-handed simple-graph $l_{2}$ with hand (possibly empty)
$h_{2}$}\\\ m(h[j])=level(i-j)[2]\ \parbox[t]{173.44534pt}{ maps some nodes of
$h$ to the place where nodes were placed on step 2}\end{cases}&(1)\\\
\begin{cases}trunkCore(T)[i-1]\ \parbox[t]{173.44534pt}{is an inner node and
it is a foot of another one-handed or zero-handed simple-graph $l_{2}$ with
hand (possibly empty) $h_{2}$}\\\ m(h[j])=level(i+j)[2]\
\parbox[t]{173.44534pt}{ maps some nodes of $h$ to the place where nodes were
placed on step 2}\end{cases}&(2)\\\ \end{array}\right.$ (61)

For the proof by contradiction assume now that both
$\tilde{\varphi}(h[j])=level(i+j)[2]$ and
$\tilde{\varphi}(h[j])=level(i-j)[2]$ map the nodes of $h$ to the places
already used on step 2. By the inductive argument that means that there exist
such $j_{1},j_{2}\leq|V(h)|$ that $trunkCore(i+j_{1})$ and
$trunkCore(i-j_{2})$ are of degree three. But that means that
$\varphi(head(l))\neq level(i)[2]$ since in that case by the inductive
argument $\varphi(h[j])$ must be either $level(i-j)[2]$ or $level(i+j)[2]$ but
in the first case we obtain a conflict with a neighbour of
$trunkCore(i+j_{1})$ and in the second case we obtain a conflict with
$trunkCore(i-j_{2})$.

So, $\varphi(head(l))$ is either $level(i+1)[1]$ or $level(i-1)[1]$. Let’s
consider the case $level(i+1)[1]$, the second is totally symmetric.

The trunk core nodes adjacent to $foot(l)$ are $trunkCore(T)[i-1]$ and
$trunkCore(T)[i+1]$ they are mapped by $\varphi$ to $level(i-1)[1]$ and
$level(i)[2]$. We consider the case where
$\varphi(trunkCore(T)[i-1])=level(i-1)[1]$ and
$\varphi(trunkCore(T)[i+1])=level(i)[2]$ and we show that in this case (1)
holds. Symmetrically $\varphi(trunkCore(T)[i-1])=level(i)[2]$ and
$\varphi(trunkCore(T)[i+1])=level(i-1)[1]$ will lead to (2).

We now prove that $trunkCore(T)[i+1]$ can’t be the end node of the trunk core.

In Lemma 5 we make a path through the support nodes. If
$trunkCore(T)[i+1]$ is not a support node, it can’t be the end node of the
trunk core since the trunk core connects to support nodes. It is neither a
single node, since it a has a neighbour $trunkCore(T)[i]$ of degree three. So,
since it is in the trunk core, we deduce that it is of degree three and there
are nodes $a$ and $c$ of degree three s.t. there is a path $a\rightarrow
trunkCore(T)[i+1]\rightsquigarrow c$. If $a$ is different from
$trunkCore(T)[i]$ then we have three consecutive nodes $trunkCore(T)[i]$,
$trunkCore(T)[i+1]$ and $a$ of degree three, so by the Lemma 10
$\varphi(trunkCore(T)[i])$ is on the same side as
$\varphi(trunkCore(T)[i+1])$, which contradicts the assumption of
$\varphi(trunkCore(T)[i])=level(i)[1]$ and
$\varphi(trunkCore(T)[i+1])=level(i)[2]$. So there is a node $c$ of degree
three which is not adjacent to $trunkCore(T)[i+1]$ and there is a path
$trunkCore(T)[i]\rightarrow trunkCore(T)[i+1]\rightsquigarrow c$. But then
either $c$ or its pair (if it is paired) is in the trunk core meaning that the
trunk core passes through $trunkCore(T)[i+1]$ so it is inner.

Thus the $trunkCore(T)[i+2]$ exists and it has no other options but to be
embedded to $level(i+1)[2]$ since if it is embedded to $level(i-1)[2]$ it is
embedded to the same level as $trunkCore(T)[i-1]$ and it violates the trunk
core monotone property stated by Lemma 10. So we are now able to apply the
inductive argument deducing that there are no nodes of degree three in
$\\{trunkCore(T)[i+1+j]\mid j\in[|V(l)|]\\}$. Recall that by our proof by
contradiction assumption we have that mapping $m:$ $m(h[j])=level(i+j)[2]$
maps some nodes of $h$ to the place where nodes were placed on step 2 meaning
that there is a node of degree three in $\\{trunkCore(T)[i+j]\mid
j\in[|V(h)|]\\}$. But this implies that the node $trunkCore(T)[i+1]$ is of
degree three, it is inner, so we have an inner simple-graph connected to it,
moreover this simple graph is a one-handed graph since otherwise we have three
nodes of degree three: $trunkCore(T)[i]$, $trunkCore(T)[i+1]$ and $head$ of
that simple-graph, implying by Lemma 10 that $trunkCore(T)[i]$ and
$trunkCore(T)[i+1]$ are mapped to the same side of the grid which as we know
is not the case.

So we have that $m:$ $m(h[j])=level(i+j)[2]$ maps some nodes of $h$ to the
place where nodes were placed on step 2 and that there is a one-handed inner
simple-graph connected tot he $trunkCore(T)[i+1]$ which is exactly the case
(1).

####  0.C.3.2 Embedding with Cycles

###### Definition 12

A _maximal_ cycle $C$ of a graph $G$ is a cycle in $G$ that cannot be
enlarged, i.e., there is no other cycle $C^{\prime}$ in $G$ such that
$V(C)\subsetneq V(C^{\prime})$.

###### Definition 13

Consider a graph $G$ and a maximal cycle $C$ of $G$. The whisker $W$ of $C$ is
a line graph inside $G$ such that:

  * •

$V(W)\neq\emptyset$, and $V(W)\cap V(C)=\emptyset$.

  * •

There exists only one edge between the cycle and the whisker $(w,c)$ for $w\in
V(W)$ and $c\in V(C)$. Such $c$ is called a _foot_ of $W$. The nodes of $W$
are enumerated starting from $w$.

  * •

$W$ is maximal, i.e., there is no $W^{\prime}$ in $G$ such that $W^{\prime}$
satisfies previous properties and $V(W)\subsetneq V(W^{\prime})$.

###### Definition 14

Suppose we have a graph $G$ that can be correctly embedded into $Ladder_{n}$
by $\varphi$ and a cycle $C$ in $G$. Whiskers $W_{1}$ and $W_{2}$ of $C$ are
called adjacent for the embedding $\varphi$ if

$\displaystyle\forall i\in[\min(|V(W_{1})|,|V(W_{2})|]\
(\varphi(W_{1}[i]),\varphi(W_{2}[i]))\in E(Ladder_{n})$

###### Statement 3

For any correct embedding of a cycle $C$ into $Ladder_{n}$ each level of
$Ladder_{n}$ is either occupied with two nodes of $C$ or not occupied at all.

###### Proof

Suppose the contradictory, and there exists a correct embedding $\varphi$ of
$C$ such that there is only one node of $C$, say $a$, on some level $i$, i.e.,
$level(i)[1]$. $a$ has two neighbours in $C$, which we call $b$ and $c$.
W.l.o.g. we say that $\varphi(b)=level(i-1)[1]$ and $\varphi(c)=level(i+1)$.
We define $next_{ab}(x)$ for the node $x\in V(C)\setminus\\{a\\}$ as the next
node in $C$ for $x$ in the direction $ab$. It is easy to see that if
$level\langle\varphi(x)\rangle>i$ then
$level\langle\varphi(next_{ab}(x))\rangle>i$ since it cannot be less than $i$
and due to the connectivity of the cycle image and it cannot be equal to $i$
since then $next_{ab}(x)=a$ and then $x=c$ but
$level\langle\varphi(c)\rangle=i-1$.
$level\langle\varphi(b)\rangle=i+1\rightarrow
level\langle\varphi(next_{ab}(b))\rangle>i\rightarrow
level\langle\varphi(next_{ab}(next_{ab}(b)))\rangle>i\rightarrow\ldots\rightarrow
level\langle\varphi(c)\rangle>i$ which is a contradiction.

###### Lemma 8

Suppose we have a graph $G$ that can be correctly embedded into $Ladder_{n}$
and there exists a maximal cycle $C$ in $G$ with at least $6$ vertices with
two neighbouring whiskers $W_{1}$ and $W_{2}$ of $C$, i.e.,
$(\text{foot}(W_{1}),\text{foot}(W_{2}))\in E(G)$. Then, $W_{1}$ and $W_{2}$
are adjacent in any correct embedding of $G$ into $Ladder_{N}$.

###### Proof

At first, we show that for every correct embedding $foot(W_{1})$ and
$foot(W_{2})$ are embedded to the same level of the grid. Suppose not. So
there exists a correct embedding $\varphi$ of $G$ s.t.
$\varphi(foot(W_{1}))=level(i)[1]$ and $\varphi(foot(W_{2}))=level(i-1)[1]$.
By the Statement 3 $level(i)[2]$ and $level(i-1)[2]$ are also occupied with
nodes from cycle. So we deduce that $\varphi(W_{1}[1])=level(i+1)[1]$ and
$\varphi(W_{2}[1])=level(i-2)[1]$. But by Statement 3 it means that there are
no nodes of $C$ mapped to the levels $i+1$ and $i-2$ and so due to
connectivity of the cycle image there are no more nodes of the cycle, but then
there are only four nodes in $C$.

Now we want to show that $W_{1}[1]$ and $W_{2}[1]$ are embedded to the same
level of the grid for any correct embedding of $G$. Suppose not. So there
exists a correct embedding $\varphi$ of $G$ s.t.

$\displaystyle\varphi(foot(W_{1}))=level(i)[1]$ (62)
$\displaystyle\varphi(foot(W_{2}))=level(i)[2]$ (63)
$\displaystyle\varphi(W_{1}[1])=level(i+1)[1]$ (64)
$\displaystyle\varphi(W_{2}[1])=level(i-1)[2]$ (65)

But this by Statement 3 implies that there are no nodes of $C$ mapped to
levels $i+1$ and $i-1$ and thus there are no more nodes of $C$ at all due to
the connectivity of the cycle image. Contradiction, since there are at least
$6$ nodes in $C$, not $2$.

So for every correct mapping $\varphi$ of $G$ we know that up to symmetry it
does the following:

$\displaystyle\varphi(foot(W_{1}))=level(i)[1]$ (66)
$\displaystyle\varphi(foot(W_{2}))=level(i)[2]$ (67)
$\displaystyle\varphi(W_{1}[1])=level(i+1)[1]$ (68)
$\displaystyle\varphi(W_{2}[1])=level(i+1)[2]$ (69)

So there is no other option for $W_{1}[2]$ and $W_{2}[2]$ but to be embedded
to $level(i+2)[1]$ and $level(i+2)[2]$ respectively and so until we reach the
end of either $W_{1}$ or $W_{2}$. In other words for any correct embedding
$\varphi$

$\displaystyle\forall i\in[\min(|V(W_{1})|,|V(W_{2})|]\
(\varphi(W_{1}[i]),\varphi(W_{2}[i]))\in E(Ladder_{n})$ (70)

###### Remark 2

Due to Lemma 8 if the cycle is of length $\geq 6$ we can forget about an
embedding while talking about adjacent whiskers.

###### Definition 15

Assume we have a graph $G$ and a maximal cycle $C$ of length at least $6$. The
frame for $C$ is a subgraph of $G$ induced by vertices of $C$ and
$\\{W_{1}[i],W_{2}[i]\mid i\in[\min(|V(W_{1})|,|V(W_{2})|)]\\}$ for each pair
of adjacent whiskers $W_{1}$ and $W_{2}$. Adding all the edges
$\\{(W_{1}[i],W_{2}[i])\mid i\in[\min(|V(W_{1})|,|V(W_{2})|)]\\}$ for each
pair of adjacent whiskers $W_{1}$ and $W_{2}$ makes frame _completed_.

Figure 9: Cycle, its frame, and edges (dashed) to make the frame completed

###### Lemma 12

If we have a cycle of length at least $6$ in a graph which is a subgraph of
the request graph then its end nodes of the frame are adjacent in the request
graph.

###### Proof

This is because by Lemma 8 they are adjacent for every embedding and in
particular for the original embedding of the cycle into the request graph.

###### Remark 3

Due to Lemma 12 we can “extend” each maximal cycle to the ends of its frame,
so, we we do not have any adjacent whiskers, i.e., one whisker is embedded
fully.

###### Lemma 13

Assume we have a graph $G$ which can be embedded into $Ladder_{n}$ and a
maximal cycle $C$ of length at least $6$ of $G$ has no adjacent whiskers.
Then, there are at most two nodes connected to $C$ (i.e. $(v,c)\in E(G)\
,such\ that\ v\in V(G)\setminus V(C)\wedge c\in V(C)$).

Moreover, these two connecting nodes are not adjacent.

###### Proof

Consider a correct embedding $\varphi$ of $G$ into $Ladder_{n}$. The cycle
occupies level from $i$ to $j$, $i<j$ (it can’t make a gap due to the
connectivity of the image and by the Lemma 3 it occupies the whole level). So
the possible places for $v$ are $level(i-1)\cup level(j+1)$.

For the proof by contradiction assume that there are at least three nodes
connected to $C$. Then by the pigeon hole principle there are two of them on
the same level, say $v_{1}$ and $v_{2}$. There can’t be an edge between
$v_{1}$ and $v_{2}$ since then the cycle can be extended by adding $v_{1}$ and
$v_{2}$ and thus is not maximal. But if there is no edge between $v_{1}$ and
$v_{2}$ they form whiskers and those whiskers are adjacent. Contradiction.

Trees and cycles

###### Definition 23

By the cycle-tree decomposition of a graph $G$ we mean a set of maximal cycles
$\\{C_{1},\ldots C_{n}\\}$ of $G$ and a set of trees
$\\{T_{1},\ldots,T_{m}\\}$ of $G$ such that

  * •

$\bigcup\limits_{i\in[n]}V(C_{i})\cup\bigcup\limits_{i\in[m]}V(T_{i})=V(G)$

  * •

$V(C_{i})\cap V(C_{j})=\emptyset\ \forall i\neq j$

  * •

$V(T_{i})\cap V(T_{j})=\emptyset\ \forall i\neq j$

  * •

$V(T_{i})\cap V(C_{j})=\emptyset\ \forall i\in[m],j\in[n]$

  * •

$\forall i\neq j\ \forall u\in V(T_{i})\ \forall v\in V(T_{j})\ (u,v)\notin
E(G)$

###### Lemma 14

Assume we have a graph $G$ which can be embedded into $Ladder_{n}$. Suppose
that there is a cycle $C$ and a tree $T$ from cycle-tree decomposition of $G$,
such that $C$ and $T$ are connected by an edge $(c,t)\in E(G)$, where $t\in
V(T)$ and $c\in V(C)$. Then, for any correct embedding $\varphi$ $t\in
trunk_{\varphi}(T)$.

###### Proof

By Lemma 3 there is another node of $C$ on the
$level\langle\varphi(c)\rangle$. Let’s say this level has number $i$. If
$\varphi(t)\in level(i+1)$ then we know that no nodes of $T$ can be embedded
to the $level(i)$ (and thus, due to the connectivity of $T$-s image, below it)
so $t$ is the bottom most node and thus it is in the trunk. Symmetrically, it
is the top most node of $T$ if $\varphi(t)\in level(i-1)$.

###### Definition 24

We call a node $t$ from Lemma 14 an _end-node_ of a tree $T$, and a node $c$ a
_foot_ of a $T$.

###### Remark 4

If the tree $T$ is connected to a cycle, then $trunkCore(T)$ can be extended
to an end-node of $T$.

We call the path connecting the end-node of the trunk core and an end-node of
a tree an extension of the trunk core.

We call a trunk core with two of its possible extensions an extended trunk
core.

The exit-graphs are now simple-graphs connected to the end-nodes of an
extended trunk core.

Note that the end-nodes of the tree might not exist while the end-nodes of the
trunk core are just the end-nodes of the path.

We now define how to embed a tree $T$ from a cycle-tree decomposition.

We include possible foots of a tree with their neighbours in that tree, making
them the end-nodes of the trunk core. We then apply strategy 0.C.3.1 to the
obtained tree.

###### Definition 25

We say that such an embedding of a tree respects the strategy 0.C.3.1.

###  0.C.4 Dynamic algorithm

Now, we talk about how we update the embedding with respect to new requests.

In our strategy of edge processing, if an already known edge is requested we
do nothing since the requested nodes are already at the distance at most $12$,
because by the assumption the enumeration preserves the proximity property
(see the strategy plan 0.C.1).

But if we obtain a new edge, our enumeration may no longer maintain the
proximity property , so we perform a re-enumeration.

There are two possible cases for the new edge. It may be within the
connectivity component or it may connect two different connectivity
components. We analyse these cases separately.

We want to maintain the following five invariants:

  1. 1.

The embedding of any connectivity component is quasi-correct.

  2. 2.

For each tree in the cycle-tree decomposition the embedding of that tree
matches the strategy 0.C.3.1

  3. 3.

We do not have maximal cycles of length $4$

  4. 4.

Each maximal cycle does not have adjacent whiskers

  5. 5.

There are no conflicts with cycle nodes

####  0.C.4.1 New edge within one connectivity component

Assume we have a connectivity component $S$ with at least one cycle (call it
$C_{S}$) and a quasi-correct embedding $\varphi^{\prime}$ of $S$ preserving
all the invariants from 0.C.4.

Assume the new edge connects nodes $u$ and $v$. Since $u$ and $v$ are already
in a one connectivity component we conclude that there is now a cycle
$C^{\prime}$ containing $u$ and $v$. We consider a maximal cycle $C$
containing $C^{\prime}$.

We call a graph $S$ with an edge $(u,v)$ as $S_{+}$.

If $C$ is of length $4$, for every two nodes $a$ and $b$ of $C$
$|level\langle\varphi^{\prime}(a)\rangle-
level\langle\varphi^{\prime}(b)\rangle|\leq 3$ since the distance in $S$
between $a$ and $b$ is at most $3$ and $\varphi^{\prime}$ preserves
connectivity. Thus, since there are no more than $3$ nodes per level, we
conclude that the difference between numbers of $a$ and $b$ is at most $12$,
so, the proximity property is maintained and we do nothing.

If $C$ is now of length at least $6$ (note that if a cycle can be embedded
into $Ladder_{n}$ its length must be even) we consider its frame $F$ stating
that it is in fact a cycle by Lemma 12 and that it has at most two nodes
connected to it by Lemma 13.

###### Lemma 15

Consider a graph $G$ embedded into $Ladder_{n}$ with some embedding $\varphi$
that respects invariants 0.C.4. Consider a frame of a maximal cycle $C$ in $G$
embedded by $\varphi$ into levels from $i$ to $j$ ($i<j$). Then $\\{v\mid v\in
V(G),\ level\langle\varphi(v)\rangle>j\\}$ form a connectivity component.

###### Proof

By the invariant 4 0.C.4 and Lemma 13 there is only one node $u$ connected to
$C$ with $level\langle\varphi(u)\rangle>j$. So, if some path from $a$ to $b$
($level\langle\varphi(a)\rangle>j$, $level\langle\varphi(b)\rangle>j$) goes
through a node $v$ with $level\langle\varphi(v)\rangle\leq j$ it must pass
through $u$ twice, meaning we can replace $a\rightsquigarrow u\rightsquigarrow
v\rightsquigarrow u\rightsquigarrow b$ with $a\rightsquigarrow
u\rightsquigarrow b$.

We say that a group of nodes is on the same side from a cycle if they are in a
one connectivity component when the cycle is removed.

###### Lemma 16

If after the removal of $F$ , a connectivity component $S_{i}$ $i\in\\{1,2\\}$
is a line-graph and it connects to $F$ via its end-node then all of its nodes
belong to an exit-graph in $S$.

###### Proof

Since by our assumption $S$ has a cycle, we state that each tree has a non-
empty extended trunk core and, thus, each node of the component has only four
options where to belong. It is either in a cycle, an extended trunk core, an
inner-graph, or an exit-graph. So, we now prove that the first three do not
happen here:

  * •

The node remains on a cycle when adding a new edge and the nodes from $S_{i}$
are not on the cycle in $S_{+}$, thus, they were not in $S$.

  * •

Each node in the extended trunk core is either of degree three or has two
edge-disjoint paths to nodes of degree three. Those properties can’t disappear
when adding a new edge and none of them hold in $S_{+}$ for nodes in $l$ thus
did not them in $S$. So the nodes from $l$ were not in the extended trunk
core.

  * •

As shown in 0.C.3.1 for every correct embedding nodes of a simple-graphs
always have a node embedded to the same level, namely a node from the trunk
core. But $S_{+}$ has an embedding with all the nodes from $S_{i}$ being
single on their level, and since every embedding for $S_{+}$ induces an
embedding for $S$ the same holds for them in $S$ thus none of them is a node
of an inner-graph in $S$.

###### Lemma 17

If a connectivity component $l$ left when removing $F$ is a line-graph and it
connects to $F$ via its inner node $u$ then all of its nodes belong to an
exit-graph in $S$ except possibly $u$.

###### Proof

The proof is almost the same as in 16 but with to adjustments:

  * •

The second bullet does not hold for $u$

  * •

$l$ has an embedding where a node from $l$ is single on its level or with
another node of $l$ and since nodes of $l$ are not the inner trunk core nodes
that means that they are not nodes of inner simple-graphs.

By Lemma 15 there are at most two connectivity components left when removing
$F$. Let’s call them $S_{1}$ and $S_{2}$. We now describe how we embed $F$,
$S_{1}$ and $S_{2}$.

So, imagine that we formed $F$ and it has node $f$ of degree three. We first
discuss the case of $S_{1}$ being a line-graph connected with $f$ with its
end-node. By Lemma 16 we deduce that $S_{1}$ was a part of an exit-graph in
$S$ and thus it was embedded strictly monotonically. In other words, (let’s
set an enumeration of $S_{1}$ such that $(S_{1}[1],f)\in E(S_{+})$)
$level\langle\varphi(S_{1}[1])\rangle<level\langle\varphi(l[2])\rangle<\ldots$.
We then embed $F$ in the way that $f$ is embedded higher then any other node
of $F$, say to $level(i)[1]$. And we embed $S_{1}[j]$ to $level(i+j)[1]$. If
the levels of nodes of $S_{1}$ were decreasing we act the same way but
embedding $f$ lower then other nodes of $F$ and embedding $S_{1}$ in
decreasing order.

What if now $S_{1}$ is a line-graph connected to $F$ via its inner node. By
the Lemma 17 we know that its hands (call them $h_{1}$ and $h_{2}$) were exit-
graphs and thus were embedded monotonically, assume increasingly numerating
from head. Assume head of $S_{1}$ was connected to $f\in V(F)$. We then embed
$F$ in a way that $f$ is embedded higher then any other node of $F$ say to
$level(i)[1]$. We then embed

$\displaystyle head(S_{1})\rightarrow level(i+1)[1]$ (71) $\displaystyle
h_{1}[j]\rightarrow level(i+1+j)[1]$ (72) $\displaystyle h_{2}[j]\rightarrow
level(i+j)[2]$ (73)

We act symmetrically if the order on $h_{i}$ was decreasing.

We now want to show that we cannot face incompatibility namely that we have
two line-graphs connected (no matter via their inner or end nodes) to $F$ both
having increasing (decreasing) order on their hands in $S$. By Lemma 16 those
line-graphs were both whiskers in $S$, so we denote them $W_{1}$ and $W_{2}$.
If they both had the same order that means they were in the same tree. To see
this we first prove that there are at most two trees from the cycle-tree
decomposition of the component can have exit-graphs. Consider the embedding
satisfying invariants 0.C.4. It induces an order on the maximal cycle of the
component, since maximal cycles do not intersect and there for can be
enumerated from bottom to top for example. If the tree is embedded between two
consecutive cycles (say, $C_{1}$ and $C_{2}$) it must be connected to both of
them. This is because they are connected with some path connecting nodes
$c_{1}$ and $c_{2}$ of cycles. We consider such path that contains just two
nodes from cycles, it is straightforward to see that such path can be obtained
if we have an arbitrary one. This path (except $c_{1}$ and $c_{2}$) belongs to
some tree $T$ in a cycle-tree decomposition. If now some tree different from
$T$ (say, $T_{2}$) from a cycle-tree decomposition is embedded between cycles,
since the component is connected it has two options: either to be connected to
$T$ or to one of the cycles. It can’t be connected to $T$ by the definition of
the cycle-tree decomposition. Neither it can be connected to $C_{1}$ or
$C_{2}$ since by the Lemma 15 if that cycle is removed since $T$ and $T_{2}$
are on the one side of that cycle they are in the one connectivity component.
But this implies that $T_{2}$ is connected to other cycle which is impossible
due to the Lemma 15.

The only way for a tree to have exit-graphs is to be embedded below the lowest
cycle or above the highest. But exit-graphs in the highest tree are embedded
increasingly and the whiskers in the lowest tree are embedded decreasingly.