Consider now some index $1\leq i\leq d_u$. Let $\gamma'_i(u)$ be the curve obtained by concatenating the images of all edges that lie on the $i$th column of grid $H_u$. We truncate the curve $\gamma_i'(u)$, so that it terminates at a point on the boundary of disc $\hat D(u)$, and is internally disjoint from disc $\hat D(u)$. We denote by $p'_i(u)$ the point on the boundary of $\hat D(u)$ that lies on $\gamma_i'(u)$. Note that curve $\gamma_i'(u)$ connects points $p_i(u)$ and $p'_i(u)$; it is contained in disc $D'(u)$, and it is internally disjoint from disc $\hat D(u)$. It is easy to verify that, since drawing $\phi'$ of $G'$ is planar, curves $\gamma'_i(u),\ldots,\gamma'_{d_u}(u)$ are disjoint from each other. For all $1\leq i\leq d_u$, we then let $\gamma''_i(u)$ be any simple curve connecting $p_i'(u)$ to $p^*(u)$, that is contained in disc $\hat D(u)$; we construct the curves $\gamma''_1(u),\ldots,\gamma''_{d_u}(u)$ so that they are internally disjoint from each other. For all $1\leq i\leq d_u$, we then let $\gamma_i(u)$ be the curve obtained by concatenating $\gamma'_i(u)$ and $\gamma''_i(u)$. It is immediate to verify that curve $\gamma_i(u)$ is contained in $D'(u)$, and it connects $p_i(u)$ to $p^*(u)$. From our construction, it is easy to verify that,  for any pair $\gamma,\gamma'$ of distinct curves in set $\Gamma\cup \set{\gamma_i(u)\mid u\in V(G); 1\leq i\leq d_u}$, every point $p\in \gamma\cap \gamma'$ must be an endpoint of both curves.

We are now ready to complete the proof of Theorem <ref>. We  construct the graph $G'$ as described above, and use the algorithm from <Ref> to test whether graph $G'$ is planar, and if so, to compute a planar drawing $\phi'$ of $G'$.
If $G'$ is not planar, then we correctly establish that $\optcrors(G,\Sigma)\ne 0$, from <Ref>.
If $G'$ is planar, then we apply the algorithm from  <Ref> to graph $G'$ and its planar drawing $\phi'$, to compute a valid solution $\phi$ to instance $I$ of with $\cro(\phi)=0$.

First, we process all vertices of $G$ with degree at least $4$, as follows.
Consider a vertex $v\in V(G)$ with $d=\deg_G(v)\ge 4$, and $\delta_G(v)=\set{e_1,\ldots,e_d}$, where the edges are indexed according to the ordering $\oset_v\in \Sigma$.
Since $d\ge 4$, $H_v$ is $3$-vertex-connected. Therefore, from [43], the the image of the grid $H_v$ in $\phi'$ is identical to the unique planar drawing of $H_v$ shown in <ref>. We denote by $F^{out}_v$ the face of this drawing whose boundary contains vertices $v_{1,1},\ldots,v_{1,d}$, and denote by $F^{i}_v$ the face of whose boundary contains vertices $v_{1,i},v_{1,i+1},v_{2,i},v_{2,i+1}$.
Since $\phi'$ is planar, the image of $e_i$ either lies entirely in $F^{out}$, or lies entirely in $F^{i}_v$, or lies entirely in $F^{i-1}_v$.
Now consider the drawing of $\phi'$ inside the face $F^i_v$. If the images of $e_i,e_{i+1}$ do not lie in $F^i_v$, then since $\phi'$ is planar, the interior of $F^i_v$ does not contain any image (or segments of image) of vertices and edges of $G'$.
If the image of $e_i$ lie in $F^i_v$, but the image of $e_{i+1}$ does not lie in $F^i_v$, then $G\setminus e_i$ is not connected, and the interior of $F^i_v$ contains the image of the connected component of $G\setminus e_i$ that does not contain $v$. We “flip” the image inside the face $F^i_v$ into the face $F^{out}_v$ as in Figure <ref>, such that the new image lies in an arbitrarily small disc $\eta(v_{1,i})$ of the image of $v_{1,i}$.

[Before flipping.]0.36

[After flipping.]

An illustration of flipping the image inside the face $F^i_v$ into the disc $\eta(v_{1,i})$.

The case where the image of $e_{i+1}$ lie in $F^i_v$ but the image of $e_{i}$ does not lie in $F^i_v$ is treated similarly.
Assume now that the images of both $e_i$ and $e_{i+1}$ lie in $F^i_v$, then $G\setminus v$ is not connected, and the interior of $F^i_v$ contains the image of the connected component of $G\setminus v$ that contains the edges $e_i,e_{i+1}$. We “flip” the image inside the face $F^i$ into the face $F^{out}_v$ as in Figure <ref>, such that the new image lies in an arbitrarily thin strip around the image of the edge $(v_{1,i},v_{1,i+1})$.

[Before flipping.]0.37

[After flipping.]
An illustration of flipping the image inside $F^i$ into the thin strip around edge $(v_{1,i},v_{1,i+1})$.

After processing all vertices in this way, we obtain a planar drawing $\phi''$ of $G'$, such that, for each vertex $v$ with $\deg_G(v)\ge 4$, in the image of the grid $H_v$ in $\phi''$, only the interior of the face $F^{out} _v$ contains image of vertices and edges of $G'$. Therefore, we can contract, for each such vertex, the image of $H_v$ into a single point $y_v$. Let $\phi$ be the resulting drawing. Note that, if we view the point $y_v$ as the image of $v$, then $\phi$ is a planar drawing of $G$ and moreover, from our way of contracting the image of $H_v$, $\phi$ is a feasible solution to the instance $(G,\Sigma)$.

Assume without loss of generality that $G$ is connected; otherwise, we process each connected component of $G$ separately.
We start by constructing a graph $G'$, that is obtained from $G$, as follows.
Initially, we set $G'=G$, and then process every vertex $v$ of $G'$ whose current degree is greater is at least $4$ one by one.
We now describe an iteration for processing a vertex $v$ of $G'$.
Denote $d=\deg_G(v)$, and let $e_1,\ldots,e_d$ be the edges in $\delta_G(v)$,  indexed according to the ordering $\oset_v\in \Sigma$. For each $1\le t\le d$, denote by $u_t$ the endpoint of edge $e_t$ that is different from $v$.
We delete vertex $v$ from $G'$, and instead add a $d\times d$-grid $H_v$ graph, denoting, for all $1\leq i,j\leq d$, the vertex at the intersection of row $i$ and column $j$ by $v_{i,j}$. For all $1\leq t\leq d$, we add a new edge $(u_t,v_{1,t})$ to graph $G'$, that represents the original edge $e_t$.
Note that this transformation does not increase the degree of any vertex that lied in $G'$ before the current iteration.
See Figure <ref> for an illustration of an iteration execution.

Once every vertex of $G'$ has degree at most $4$, we obtain the final graph $G'$.

[Vertex $v$ and its incident edges $e_1,\ldots, e_d$ ordered according to the ordering $\oset_v$.]0.4

[The grid $H_v$ and the reorganization of edges $e_1,\ldots, e_d$.]
An illustration of an iteration of processing vertex $v$ in constructing the graph $G'$. is it possible to modify the two  figures so that vertices that are different from $v$ are called $u_1,\ldots,u_d$, and the circles representing the vertices have the same outline color as the inner color? Thanks!

We use the following observations.

If $\optcrors(I)=0$, then graph $G'$ is planar.

Let $\phi$ be a feasible solution to instance $I$ of , with $\cro(\phi)=0$. We modify $\phi$ to construct a drawing of graph $G'$ with no crossings. The modification follows the process that we used in order to modify graph $G$ to obtain graph $G'$.

Specifically, we let $H=G$, and then process every vertex of $H$ whose degree is greater than $4$ one by one. Consider an iteration where some vertex $v$ is processed, and denote by $e_1,\ldots,e_d$ the set of edges that are incident to vertex $v$  in graph $G$,
Consider a vertex $v\in V(G)$ with $d=\deg_G(v)\ge 4$, and $\delta_G(v)=\set{e_1,\ldots,e_d}$, where the edges are indexed according to the ordering $\oset_v\in \Sigma$.
Since $\deg_G(v)\ge 4$, $H_v$ is $3$-vertex-connected. Since the grid $H_v$ is a planar graph, and it was proved by Whitney in [43] that every $3$-vertex-connected graph has a unique planar drawing, we know that $H_v$ has a unique planar drawing, which is shown in Figure <ref>.
Let $\eta(v)$ be an arbitrarily small disc around the image $\phi(v)$ of $v$ in $\phi$, such that the boundary of $\eta(v)$ only intersects with the image of edges $e_1,e_2\ldots,e_d$, and the intersections are denoted by $x_1,\ldots,x_d$, respectively.
Note that, since $\phi$ is a feasible solution to the instance $(G,\Sigma)$, the intersections $x_1,\ldots,x_d$ appear on the boundary of $\eta(v)$ in this order.
We erase the drawing of $\phi$ inside the disc $\eta(v)$, and put the unique planar drawing of the grid $H_v$ inside $\eta(v)$, with vertices $v_{1,1},\ldots,v_{1,d}$ appearing on the outer face.
We then connect, for each $1\le i\le d$, the image of vertex $v_{1,i}$ to the intersection $x_i$ via a simple curve in $\eta(v)$, such that all these curves are mutually disjoint and internally disjoint from the image of $H_v$. It is clear that the drawing obtained this way is a planar drawing of $G'$.

§.§ Proof of Theorem <ref>

We start with any feasible solution $\phi$ to instance $I$, and then gradually modify it to ensure that every pair of edges in $G$ cross at most once.
As long as there  is a pair $e,e'\in E(G)$ of distinct edges, whose images cross at least twice in ${\phi}$, we perform the following modification step. Let $p,q$ be two crossing points between curves $\phi(e),\phi(e')$, that appear consecutively on $\phi(e)$; in other words, the segment of $\phi(e)$ between $a$ and $b$ contains no other point that lies on $\phi(e')$. We “uncross” the images of edges $e$ and $e'$, as shown in Figure <ref>.
(In Sections <ref> and <ref> we provide a more formal description of this uncrossing process, that we refer to as type-1 uncrossing).
It is easy to see that, after this uncrossing step, the new drawing remains a feasible solution to instance $I$, and the number of crossings in the drawing decreases by at least $2$.
We continue this process until every pair of edges of $G$ cross at most once in $\phi$. It is clear that the resulting drawing contains at most $|E(G)|^2$ crossings.

[Before: Curves $\phi(e)$ (red) and $\phi(e')$ (blue) cross at $p$ and $q$.]0.12

[After: The modified curves no longer cross at $p$ or at $q$.]
Uncrossing two curves.

We start with any feasible solution $\phi$ of the instance $(G,\Sigma)$. Let $\Gamma_1$ be the set of curves in the drawing $\hat\phi$. We apply the algorithm of Theorem <ref> to the set $\Gamma_1$ of curves, with $\Gamma_2=\emptyset$. Let $\Gamma'_1$ be the set of curves that we obtain. From Theorem <ref>, it is clear that the curves in $\Gamma'_1$ form a drawing $\phi'$ of $G$ that respects the rotation system $\Sigma$. Moreover, in the drawing $\phi'$, any pair of curves cross at most once. Therefore, $\cro(\phi')\le |E(G)|^2$.

§.§ Proof of <Ref>

Denote $I=(G,\Sigma)$ and $m=|E(G)|$. Recall that from Property <ref>, $\sum_{I'=(G',\Sigma')\in \iset'}|E(G')|\leq m\cdot (\log m)^{O(1)}$, so in particular, for every instance $I'=(G',\Sigma')\in \iset'$, $|E(G')|\leq m\cdot (\log m)^{O(1)}$.
From the same property, for every instance $I'=(G',\Sigma')\in \iset'$, $\sum_{I''=(G'',\Sigma'')\in \iset''(I')}|E(G'')|\leq |E(G')|\cdot (\log(|E(G')|))^{O(1)}\leq |E(G')|\cdot (\log m)^{O(1)}$. Therefore, altogether, we get that:

\[
\begin{split}
\sum_{I''=(G'',\Sigma'')\in \iset}|E(G'')|& = \sum_{I'\in \iset'}\sum_{I''=(G'',\Sigma'')\in \iset''(I')}|E(G'')|\\
& \leq \sum_{I'=(G',\Sigma')\in \iset'}|E(G')|\cdot (\log m)^{O(1)}\\
%& \leq \log(|E(G)|)^{O(1)}\cdot \sum_{I'=(G',\Sigma')\in \iset'}|E(G')|\\
& \leq m\cdot (\log m)^{O(1)},\\
\end{split}
\]

establishing Property <ref>.

Next, we establish Property <ref>, using the same property of Algorithms $\alg_1$ and $\alg_2$:

split form

\[\begin{split}
\sum_{I''=(G'',\Sigma'')\in \iset''}|E(G'')|&=  \\
&=\sum_{I'=(G',\Sigma')\in \iset'}\sum_{I''=(G'',\Sigma'')\in \iset''(I')}|E(G'')|\\
&\leq \sum_{I'=(G',\Sigma')\in \iset'}O(|E(G')|)\\
&\leq O(|E(G)|).
\end{split}\]

\[\begin{split}
\expect{\sum_{I''\in \iset''}\optcrors(I'')}&=\sum_{I'\in \iset'}\expect{\sum_{I''\in \iset''(I')}\optcrors(I'')}\\
&\leq \sum_{I'=(G',\Sigma')\in \iset'}\expect{\bigg(\optcrors(I')+|E(G')|\bigg)\cdot \nu''}\\
&= \nu''\cdot\left(\sum_{I'=(G',\Sigma')\in \iset'}|E(G')|\right)+ \nu''\cdot\expect{\sum_{I'\in \iset'}\optcrors(I')}\\
&\leq O(\nu''\cdot m\cdot (\log m)^{O(1)})+\left (\optcrors(I)+m\right )\cdot (\nu'\nu'')\\
&\leq \left (\optcrors(I)+m\right )\cdot \nu''\cdot\max\set{2\nu',(\log m)^{O(1)}}\\
&\leq \left (\optcrors(I)+m\right )\cdot \nu.
\end{split}\]

Lastly, we establish Property <ref> of Algorithm $\alg$, using the same property of algorithms $\alg_1$ and $\alg_2$.
Assume that we are  given, for every instance $I''\in \iset''$, a feasible solution $\phi(I'')$ to $I''$.
We process instances $I'\in \iset'$ one by one. For each such instance, we apply Algorithm $\alg(\iset''(I'))$ that is given by Property <ref> of the decomposition $\iset''(I')$ to solutions $\phi(I'')$ of instances $I''\in \iset''(I')$, to obtain  a solution $\phi(I')$ to instance $I'$ of cost at most  $O\left (\sum_{I''\in \iset''(I')}\cro(\phi(I''))\right )$.

We then apply the algorithm $\alg(\iset')$, given by Property <ref> of the decomposition $\iset'$ of $I$, to the resulting solutions $\phi(I')$ for instances $I'\in \iset'$, to obtain a solution $\phi(I)$ to instance $I$, whose cost is at most:

$$O\left (\sum_{ I'\in \iset'}\cro(\phi(I'))\right )\le O\left (\sum_{ I''\in \iset}\cro(\phi(I''))\right ).$$

§ PROOFS OMITTED FROM <REF>

§.§ Proof of <Ref>

The proof is by induction on $h(I)$. The base case is when $h(I)=0$, so $v(I)$ is a leaf vertex of $T^*$, and hence of $T$. Denote $I=(G,\Sigma)$.  From <Ref>, either $|E(G)|\leq \mu^{c''}$; or $\optcrors(I)=0$; or $\optcrors(I)> |E(G)|^2/\mu^{c''}$.
If $\optcrors(I)=0$, then the algorithm returns a solution of cost $0$. Otherwise, $\optcrors(I)\geq 1$, and, if $|E(G)|\leq \mu^{c''}$, then the algorithm returns  the trivial solution, of cost at most $|E(G)|^2\leq |E(G)|\cdot \mu^{c''}$. Lastly, if $\optcrors(I)>|E(G)|^2/\mu^{c''}$, then, since the trivial solution $\phi'$ is considered by the algorithm, it returns a solution of cost at most $|E(G)|^2\leq \optcrors(I)\cdot \mu^{c''}$.

Assume now that  the claim holds for all vertices $v(I)$ of $T^*$ with $h(I)<q$,  for some $0<q\leq \dep(T)$. Consider any vertex $v(I)$ of the tree $T^*$ with $h(I)=q$. Let $v(I_1),\ldots,v(I_k)$ be the child vertices of $v(I)$ in the tree $T^*$. Denote $I=(G,\Sigma)$ and $|E(G)|=m$. Additionally, for all $1\leq r\leq k$, denote $I_r=(G_r,\Sigma_r)$ and $m_r=|E(G_r)|$.

Since instance $I$ is not a leaf instance of $T$, $|E(G)|\geq \mu^{c''}$ must hold.
Since we have assumed that event $\event$ does not happen, either $\optcrors(I)> |E(G)|^2/\mu^{c''}$, or $\sum_{r=1}^k\optcrors(I_r)\leq (\optcrors(I)+m)\cdot 2^{c_g(\log m)^{3/4}\log\log m}$ must hold.
In the former case, the algorithm is guaranteed to return a solution to $I$ whose cost is at most $|E(G)|^2\leq \optcrors(I)\cdot \mu^{c''}$, since the trivial solution $\phi'$ is considered as one of the possible solutions. From now on we focus on latter case. For all $1\leq r\leq k$, let $\phi_r$ be the solution to instance $I_r$ that the algorithm computes recursively. From the induction hypothesis, for all $1\leq r\leq k$:

\[\cro(\phi_r)\leq  2^{\tilde c\cdot h(I_r)\cdot (\log m^*)^{3/4}\log\log m^*}\cdot \mu^{c''\cdot c_g}\cdot \optcrors(I_r)+(\log m^*)^{4c_g h(I_r)}\mu^{2c''\cdot \tilde c}\cdot m_r.\]

Notice that, for all $1\leq r\leq k$, $h(I_r)\leq q-1$. Moreover, from  <Ref>, $\sum_{r=1}^km_r\leq m\cdot(\log m)^{c_g}\leq m\cdot(\log m^*)^{c_g}$. Lastly, as noted already, $\sum_{r=1}^k\optcrors(I_r)\leq (\optcrors(I)+m)\cdot 2^{c_g(\log m)^{3/4}\log\log m}$ must hold.
Altogether, we get that:

\[
\begin{split}
\sum_{r=1}^k\cro(\phi_r)&\leq 2^{\tilde c\cdot (q-1)\cdot (\log m^*)^{3/4}\log\log m^*}\cdot \mu^{c''\cdot c_g}\cdot \sum_{r=1}^k\optcrors(I_r)+(\log m^*)^{4c_g (q-1)}\mu^{2c''\cdot \tilde c}\cdot \sum_{r=1}^km_r
\\
&\leq 2^{\tilde c\cdot (q-1)\cdot (\log m^*)^{3/4}\log\log m^*}\cdot \mu^{c''\cdot c_g}\cdot  (\optcrors(I)+m)\cdot 2^{c_g(\log m)^{3/4}\log\log m} \\
&\hspace{6cm}+(\log m^*)^{4c_g (q-1)}\mu^{2c''\cdot \tilde c}\cdot m\cdot(\log m^*)^{c_g}\\
&\leq 2^{\tilde c\cdot (q-0.5)\cdot (\log m^*)^{3/4}\log\log m^*}\cdot \mu^{c''\cdot c_g}\cdot \optcrors(I)+ (\log m^*)^{4c_gq-3c_g}\mu^{2c''\cdot \tilde c}\cdot m\\
&\hspace{6cm}+2^{\tilde c\cdot (q-0.5)\cdot (\log m^*)^{3/4}\log\log m^*} \cdot\mu^{c''\cdot c_g}\cdot m.
\end{split}\]

Since $q\leq \dep(T)\leq \frac{(\log m^*)^{1/8}}{c^*\log\log m^*}$  from <Ref>,
the last term is bounded by:

\[ 2^{\tilde c\cdot (\log m^*)^{7/8}/c^*} \cdot\mu^{c''\cdot c_g}\cdot m  \leq \mu^{2c''\cdot c_g}\cdot m\]

(since $\mu =2^{c^*(\log m^*)^{7/8}\log\log m^*}$). Therefore, we get that:

\[\sum_{r=1}^k\cro(\phi_r)\leq  2^{\tilde c\cdot (q-0.5)\cdot (\log m^*)^{3/4}\log\log m^*}\cdot \mu^{c''\cdot c_g}\cdot \optcrors(I)+ (\log m^*)^{4c_gq-2c_g}\mu^{2c''\cdot \tilde c}\cdot m. \]

The solution that our algorithm returns for instance $I$ is obtained by applying Algorithm from <Ref> to solutions $\phi_1,\ldots,\phi_k$ to instances $I_1,\ldots,I_k$ (or some other solution the algorithm considers, if its cost is smaller). Since event $\event$ does not happen, the cost of the resulting solution is bounded by:

\[
\begin{split}
&c_g\cdot\bigg(\sum_{r=1}^k\cro(\phi_r)\bigg) +(\optcrors(I)+m)\cdot\mu^{c_g}\\
&\hspace{1cm}\leq c_g\cdot 2^{\tilde c\cdot (q-0.5)\cdot (\log m^*)^{3/4}\log\log m^*}\cdot \mu^{c''\cdot c_g}\cdot \optcrors(I)+\mu^{c_g}\cdot \optcrors(I)\\
&\hspace{3cm}+ c_g\cdot(\log m^*)^{4c_gq-2c_g}\mu^{2c''\cdot \tilde c}\cdot m+\mu^{c_g}\cdot m\\
&\hspace{1cm}\leq 2^{\tilde c\cdot q\cdot (\log m^*)^{3/4}\log\log m^*}\cdot \mu^{c''\cdot c_g}\cdot \optcrors(I)+(\log m^*)^{4c_gq}\mu^{2c''\cdot \tilde c}\cdot m,
\end{split}
\]

as required.

§.§ Proof of <Ref>

We construct the solution $\phi(I)$ to instance $I$ in three steps.
In the first step, we compute a solution $\phi(I')$ to every instance $I'\in \hat{\iset}^{(n)}_{\textsf {large}}\cup \tilde{\iset}^{(n)}_{\textsf {large}}$, as follows. Consider any instance $I'=(G',\Sigma')\in \hat{\iset}^{(n)}_{\textsf {large}}\cup \tilde{\iset}^{(n)}_{\textsf {large}}$. Recall that we are given a solution $\phi(I'')$  to every instance $I''\in \overline\iset(I')$. Recall also that $\overline\iset(I')$ is a $\nu$-decomposition  of instance $I'$. We apply the efficient algorithm $\alg(\overline\iset(I'))$ from the definition of $\nu$-decomposition to the drawings in set  $\set{\phi(I'')}_{I''\in \overline\iset(I')}$, to compute a feasible solution $\phi(I')$ to instance $I'$, of cost $\cro(\phi(I'))\leq O\left (\sum_{I''\in \overline\iset(I')}\cro(\phi(I''))\right )$.
Overall, we get that:

\begin{equation}\label{eq: solutoins to narrow instances}
\sum_{I'\in \hat{\iset}^{(n)}_{\textsf {large}}\cup \tilde{\iset}^{(n)}_{\textsf {large}}}\cro(\phi(I'))\leq \sum_{I''\in \iset^*}O(\cro(\phi(I''))).
\end{equation}

We have now obtained a solution $\phi(I')$ to every instance $I'\in \big(\hat{\iset}_{\textsf {small}}\cup \hat{\iset}^{(n)}_{\textsf {large}}\cup \tilde{\iset}_{\textsf {small}}\cup \tilde{\iset}^{(n)}_{\textsf {large}}\big)$.

In the second step, we compute a solution $\phi(I')$ to every instance $I'\in \hat{\iset}^{(w)}_{\textsf {large}}$.
Consider any such instance $I'\in \hat{\iset}^{(w)}_{\textsf {large}}$.
Recall that we applied the algorithm from  <Ref> to instance $I'$, to obtain a collection $\tilde \iset(I')$ of instances of . Every instance in the resulting collection belongs to $\tilde \iset_{\textsf{small}}$ or to $ \tilde{\iset}^{(n)}_{\textsf {large}}$.
We use Algorithm $\algcombine'$, that is guaranteed from <Ref>, to compute a solution $\phi(I')$ to instance $I'$.
Since we have assumed that event $\event_2$ did not happen, the cost of the solution is bounded by:

$\cro(\phi(I')) \leq \sum_{\tilde I=(\tilde G, \tilde \Sigma)\in \tilde \iset(I')}\cro(\phi(\tilde I)) + \optcrors(I')\cdot\mu^{c'_g}$.
Overall, we get that:

\begin{equation}\label{eq: solutions to wide not connected}
\sum_{I'\in \hat{\iset}^{(w)}_{\textsf {large}}}\cro(\phi(I'))\leq \sum_{I''\in \iset^*}O(\cro(\phi(I''))+\sum_{I'\in \hat{\iset}^{(w)}_{\textsf {large}}}\optcrors(I')\cdot\mu^{c'_g}.
\end{equation}

We now describe the third step. We have so far obtained a solution $\phi(I')$ to every instance $I'\in \big(\hat{\iset}_{\textsf {small}}\cup \hat{\iset}^{(n)}_{\textsf {large}}\cup
\hat{\iset}^{(w)}_{\textsf {large}}\big)$, that is, a solution to every instance in $\hat \iset$.
Recall that $\hat \iset$ is a $\nu_1$-decomposition of the input instance $I$. Since we have assumed that Event $\event_1$ did not happen, $\sum_{I'\in \hat\iset}\optcrors(I')\leq  100\cdot\left (\optcrors(I)+m\right )\cdot \nu_1$. By combining Inequalities <ref> and <ref>, we get that:

\begin{equation}\label{eq: solution for step 1}
\begin{split}
\sum_{I'\in \hat \iset}\cro(\phi(I'))&\leq \sum_{I''\in \iset^*}O(\cro(\phi(I''))+\sum_{I'\in \hat{\iset}^{(w)}_{\textsf {large}}}\optcrors(I')\cdot\mu^{c'_g}\\
&\leq \sum_{I''\in \iset^*}O(\cro(\phi(I''))+100\cdot\left (\optcrors(I)+m\right )\cdot \nu_1\cdot \mu^{c'_g}\\
&\leq \sum_{I''\in \iset^*}O(\cro(\phi(I''))+\left (\optcrors(I)+m\right )\cdot \mu^{O(1)},
\end{split}
\end{equation}

since $\nu_1= 2^{O((\log m)^{3/4}\log\log m)}$ and $\mu\gg \nu_1$.

Lastly, we apply the efficient algorithm $\alg(\hat \iset)$ that is guaranteed by the definition of $\nu_1$-decomposition to the solutions $\set{\phi(I')}_{I'\in \hat \iset}$, to obtain a feasible solution $\phi(I)$ to instance $I$.
The cost of the solution is bounded by $\sum_{I'\in \hat \iset}O(\cro(\phi(I')))\leq
\sum_{I''\in \iset^*}O(\cro(\phi(I''))+\left (\optcrors(I)+m\right )\cdot \mu^{O(1)}$, as required.

If events $\event_1,\event_2,\event_3$ did not happen, then the cost of the solution is bounded by

\[\begin{split}
&\cro(\phi(I)) \leq O\bigg(\sum_{I'\in \hat \iset}\cro(\phi(I'))\bigg) \\
&\leq  O\bigg(\sum_{I'\in \hat \iset_{\textsf {small}}}\cro(\phi(I'))+\sum_{I'\in \hat \iset^{(n)}_{\textsf {large}}}\cro(\phi(I'))+\sum_{I'\in \hat \iset^{(w)}_{\textsf {large}}}\cro(\phi(I'))\bigg)\\
&\leq  O\bigg(\sum_{I'\in \hat \iset_{\textsf {small}}}\cro(\phi(I'))+\sum_{I'\in \hat \iset^{(n)}_{\textsf {large}}}\cro(\phi(I'))+\sum_{I'\in \hat \iset^{(w)}_{\textsf {large}}}\bigg(\sum_{\tilde I\in \tilde
\iset(I')}\cro(\phi(\tilde I))+\optcrors(I')\cdot\mu^{c'_g}\bigg)\bigg)\\
&\leq  O\bigg(\sum_{I'\in \hat \iset_{\textsf {small}}}\cro(\phi(I'))+\sum_{I'\in \hat \iset^{(n)}_{\textsf {large}}}\cro(\phi(I'))+\sum_{I'\in \hat \iset^{(w)}_{\textsf {large}}}\sum_{\tilde I\in \tilde
\iset(I')}\cro(\phi(\tilde I))\bigg)+100(\optcrors(I)+m)\cdot\mu^{c'_g}\cdot\nu_1\\
&\leq  O\bigg(\sum_{I'\in \hat \iset_{\textsf {small}}}\cro(\phi(I'))+\sum_{\tilde I\in \tilde
\iset_{\textsf {small}}}\cro(\phi(\tilde I))+\sum_{I'\in \hat \iset^{(n)}_{\textsf {large}}\cup \tilde \iset^{(n)}_{\textsf {large}}}\cro(\phi(I'))\bigg)+100(\optcrors(I)+m)\cdot\mu^{c'_g}\cdot\nu_1\\
&\leq  O\bigg(\sum_{I'\in \hat \iset_{\textsf {small}}}\cro(\phi(I'))+\sum_{\tilde I\in \tilde
\iset_{\textsf {small}}}\cro(\phi(\tilde I))+\sum_{I'\in \hat \iset^{(n)}_{\textsf {large}}\cup \tilde \iset^{(n)}_{\textsf {large}}}O\bigg(\sum_{I''\in \overline\iset(I')}\cro(\phi(I''))\bigg)\bigg)+100(\optcrors(I)+m)\cdot\mu^{c'_g}\cdot\nu_1\\
&\leq O\left (\sum_{I''\in \iset^*}\cro(\phi(I'))\right ) +(\optcrors(I)+m)\cdot\mu^{O(1)}.
\end{split}
\]

§.§ Proof of <Ref>

Throughout the proof, we assume that $\optcrors(I)\leq |E(G)|^2/\mu^{c'}$ and bad event $\event$ did not happen.

Since event $\event_1$ does not happen:

\begin{equation}\label{eq: bound on opts step 1}
\sum_{I'\in \hat\iset}\optcrors(I')\leq  100\nu_1\cdot (\optcrors(I)+m).
\end{equation}

Recall that $\hat \iset=\hat{\iset}_{\textsf {small}}\cup \hat{\iset}^{(n)}_{\textsf {large}}\cup
\hat{\iset}^{(w)}_{\textsf {large}}$. In Step 2 of the algorithm, applied the algorithm from <Ref> to every instance $I'=(G',\Sigma')\in \hat{\iset}^{(w)}_{\textsf {large}}$, to compute a collection $\tilde \iset(I')$ of instances of . Consider now any such instance $I'\in \hat{\iset}^{(w)}_{\textsf {large}}$. Since we have assumed that Event $\event_2$ did not happen:

\[
\sum_{\tilde I\in \tilde \iset(I')}\optcrors(\tilde I)\le \optcrors(I')\cdot (\log |E(G')|)^{c'_g}\leq \optcrors(I')\cdot (\log m)^{c'_g}.
\]

Recall that we have defined $\tilde \iset=\bigcup_{I'\in \hat{\iset}^{(w)}_{\textsf {large}}}\tilde \iset(I')$. Combining the above inequality with Equation <ref>, and recalling that $\nu_1=2^{O((\log m)^{3/4}\log\log m)}$, we get that:

\begin{equation}\label{eq: bound opts second}
\sum_{\tilde I\in \tilde \iset}\optcrors(\tilde I)\le \sum_{I'\in \hat{\iset}^{(w)}_{\textsf {large}}}\optcrors(I')\cdot (\log m)^{c'_g}\leq (\optcrors(I)+m)\cdot 2^{O((\log m)^{3/4}\log\log m)}.
\end{equation}

Consider now an instance $I'=(G',\Sigma')\in \hat{\iset}^{(n)}_{\textsf {large}}\cup \tilde{\iset}^{(n)}_{\textsf {large}}$. Since we have assumed that event $\event_3$ does not happen, from the definition of a $\nu$-decomposition:

\[\expect{\sum_{I''\in \overline\iset(I')}\optcrors(I'')}\le \left (\optcrors(I')+|E(G')|\right )\cdot \nu. \]

Recall that $\overline\iset_{\textsf{small}}=\bigcup_{I'\in \hat{\iset}^{(n)}_{\textsf {large}}\cup \tilde{\iset}^{(n)}_{\textsf {large}}}\overline\iset(I')$. Recall also that, from  Inequality <ref>,
$\sum_{I'=(G',\Sigma')\in \hat \iset^{(n)}_{\textsf {large}}}|E(G')|\le m\cdot (\log m)^{c'_g}$,
and from Inequality <ref>,
$\sum_{I'=(G',\Sigma')\in \tilde{\iset}^{(n)}_{\textsf {large}}}|E(G')|\leq 2m\cdot (\log m)^{c'_g}$.  Altogether, we get that:

\begin{equation}\label{eq: bound ops last step}
\begin{split}
\expect{\sum_{I''\in \overline\iset_{\textsf{small}}}\optcrors(I'')}&\leq \sum_{I'=(G',\Sigma')\in \hat \iset^{(n)}_{\textsf {large}}\cup \tilde \iset^{(n)}_{\textsf {large}}} \left (\optcrors(I')+|E(G')|\right )\cdot \nu\\
&\leq \sum_{I'\in \hat \iset^{(n)}_{\textsf {large}}\cup \tilde \iset^{(n)}_{\textsf {large}}} \optcrors(I')\cdot \nu +4m\cdot (\log m)^{c'_g}\cdot \nu\\
&\leq (\optcrors(I)+m)\cdot 2^{O((\log m)^{3/4}\log\log m)}
\end{split}
\end{equation}

(we have used Equations <ref> and <ref> in order to bound $\sum_{I'\in \hat \iset^{(n)}_{\textsf {large}}}\optcrors(I')$ and $\sum_{I'\in \hat \iset^{(n)}_{\textsf {large}}}\optcrors(I')$, respectively, and the fact that $\nu_1,\nu\leq  2^{O((\log m)^{3/4}\log\log m)}$).

Finally, by combining Equations <ref>, <ref> and <ref>, we get that:

\[
\begin{split}
\expect{\sum_{I''\in \iset^*}\optcrors(I'')}&\leq \expect{\sum_{I''\in \hat \iset_{\textsf {small}}}\optcrors(I'')+ \sum_{I''\in \tilde \iset_{\textsf {small}}}\optcrors(I'')+\sum_{I''\in \overline \iset_{\textsf {small}}}\optcrors(I'')}\\
&\leq (\optcrors(I)+m)\cdot 2^{O((\log m)^{3/4}\log\log m)}.
\end{split}
\]

We denote this expectation by $\eta'$.
Let $\hat \event$ be the bad event that
$\sum_{I''\in \iset^*}\optcrors(I'')>100\eta'$. From Markov inequality, $\prob{\hat \event\mid \neg\event}<1/100$.

§ PROOFS OMITTED FROM SECTION <REF>

§.§ Proof of <Ref>

Denote $E=\delta_G(v)$. We first define a multiset $E'$ and an ordering $\oset'$ on $E'$ as follows. Set $E'$ contains, for each edge $e\in E$, $(n^-_e+n^+_e)$ copies of $e$, in which $n^-_e$ copies are labelled $-$, and other $n^+_e$ copies are labelled $+$. The ordering $\oset'$ on $E'$ is obtained from the ordering $\oset_v$ on $E$ by replacing, for each $e\in E'$, the edge $e$ in the ordering $\oset_v$ with its $(n^-_e+n^+_e)$ copies in $E'$, that appear consecutively at the location of $e$ in $\oset_v$, and the ordering among these copies is arbitrary.
Since $\sum_{e\in E}n^-_e=\sum_{e\in E}n^+_e$, the number of edges in $E'$ that are labelled $-$ is the same as the number of edges in $E'$ that are labelled $+$.
We now iteratively construct a set $M'$ of ordered pairs as follows.
We start with $M'=\emptyset$ and perform iterations.
In each iteration, we find a pair of edges in $E'$ that appears consecutively in $\oset'$, such that one of them (denoted by $e'_1$) is labelled $-$ and the other (denoted by $e'_2$) is labelled $+$. It is clear that such a pair always exists. Note that it is possible that $e'_1$ and $e'_2$ are distinct copies of the same edge of $E$.
We then add the ordered pair $(e'_1,e'_2)$ to $M'$, and delete $e'_1,e'_2$ from $E'$ and $\oset'$.
It is clear that after this iteration, the number of remaining edges in $E'$ (and in $\oset'$) that are labelled $-$ is still the same as the number of remaining edges in $E'$ (and in $\oset'$) that are labelled $+$. Therefore, at the end of the process, $E'$ and $\oset'$ become empty and $M'$ contains $\sum_{e\in E}n^+_e$ ordered pairs of edges in $E'$. Moreover, for each pair of ordered pairs in $M'$, the intersection between the paths consisting of corresponding pairs of edges is non-transversal with respect to $\oset'$.
We then let set $M$ contains, for each pair $(e'_1,e'_2)\in M$, a pair $(e_1,e_2)$, where $e_1$ is the original edge of $e'_1$ in $E$ and $e_2$ is the original edge of $e'_2$ in $E$. It is clear that for each pair of ordered pairs in $M$, the intersection between the paths consisting of corresponding pairs of edges is non-transversal with respect to $\oset'$.

§.§ Proof of <Ref>

Consider a pair $R,R'$ of edge-disjoint cycles with $R\in \rset$ and $R'\in \rset'$. We denote by $\gamma$ the closed curve obtained by taking the union of the images of all edges of $R$ in $\phi$, and we define the closed curve $\gamma'$ similarly. Since $R$ and $R'$ are edge-disjoint, and since $\phi$ is a feasible solution to instance $I=(G,\Sigma)$, curves $\gamma$ and $\gamma'$ are in general position. Let $X(\gamma,\gamma')$ be the set of crossings between curves $\gamma,\gamma'$ that are not vertex-images in $\phi$, so $|X(\gamma,\gamma')|=\chi(\gamma,\gamma')$. We will show that, if the intersection between $R$ and $R'$ are transversal at exactly one of their shared vertices, then $X(\gamma,\gamma')\ne \emptyset$.

Assume for contradiction that $X(\gamma,\gamma')=\emptyset$. Let $v_1,\ldots,v_k$ be the shared vertices between $R$ and $R'$, and let $x_1,\ldots,x_k$ be the images of $v_1,\ldots,v_k$ in $\phi'$, respectively. Assume without loss of generality that vertices $v_1,\ldots,v_k$ appear sequentially on cycle $R$, and the intersection between $R$ and $R'$ is transversal at $v_1$.
We give a direction for the closed curve $\gamma$ as follows: $x_1\to x_2\to\ldots\to x_k\to x_1$.
Clearly, the curve $\gamma$ partitions the sphere into internally-disjoint discs, and since $R$ is a simple cycle, vertex $x_1$ lies on the boundary of exactly two of these discs, that we denote by $D_{+}$ and $D_{-}$.

Since cycles $R,R'$ are disjoint and the intersection of them is transversal at $v_1$, if we denote by $\gamma'_+$ the tiny segment of curve $\gamma'$ that has $x_1$ as an endpoint and goes a little in one direction of $\gamma'$, and denote by $\gamma'_-$ the tiny segment of curve $\gamma'$ that has $x_1$ as an endpoint and goes a little in the other direction of $\gamma'$, then one of segments $\gamma'_+, \gamma'_+$ belong to $D_{+}$ and the other belongs to $D_{-}$. Therefore, since $\gamma'$ is a closed curve, $\gamma'$ has to intersect the boundary of disc $D_{+}$ at some other point $x'$. However, since $R$ and $R'$ are edge-disjoint and the intersections of $R$ and $R'$ are non-transversal at $v_2,\ldots,v_k$, $x$ cannot be any of $\set{x_2,\ldots,x_k}$. Therefore, $x'$ has to be some non-vertex-image crossings between $\gamma$ and $\gamma'$.

We now complete the proof of <Ref>.
For every cycle $R\in \rset$, we denote by $\gamma_R$ the closed curve obtained by taking the union of the images of all edges of $R$ in $\phi$, and for each cycle $R\in \rset'$, we define the closed curve $\gamma_R'$ similarly.
Then it is easy to verify that every crossing $(e,e')$ in drawing $\phi$ belongs to at most $\bigg(\cong_G(\rset,e)\cdot \cong_G(\rset',e')+\cong_G(\rset,e')\cdot \cong_G(\rset',e)\bigg)$ sets among all sets of $\set{X(\gamma_R,\gamma_{R'})\mid R\in \rset, R'\in \rset'}$.
Since for every pair $R, R'$ of edge-disjoint cycles with $R\in \rset, R'\in \rset'$, the intersection of $R$ and $R'$ is transversal at at most one of their common vertices, we get that

\[
\begin{split}
\ntcost(\rset,\rset';\Sigma)\le & \sum_{R\in \rset, R'\in \rset'} |X(\gamma_{R}, \gamma_{R'})|\\
\le & \sum_{e,e'\in E(G)}\chi_{\phi}(e,e')\cdot \bigg(\cong_G(\rset,e)\cdot \cong_G(\rset',e')+\cong_G(\rset,e')\cdot \cong_G(\rset',e)\bigg).
\end{split}
\]

§.§ Proof of <Ref>

We first prove the following lemma.

There exists an efficient algorithm, that, given a point $p$ in the plane, a disc $D$ containing $p$, and a set $\Gamma$ of curves, such that every curve $\gamma$ of $\Gamma$ contains the point $p$ and intersects the boundary of $D$ at two distinct points $s_{\gamma},t_{\gamma}$, and $p$ is the only point in $D$ that belongs to at least two curves of $\Gamma$, computes, for each curve $\gamma\in \Gamma$, a curve $\gamma'$, such that

* for each curve $\gamma\in \Gamma$, the curve $\gamma'$ does not contain $p$, and is identical to the curve $\gamma$ outside the disc $D$;

* the segments of curves of $\set{\gamma'\mid \gamma\in \Gamma}$ inside disc $D$ are in general position;

* for each pair $\gamma_1,\gamma_2$ of curves in $\Gamma$, the new curves $\gamma_1,\gamma_2$ cross inside $D$ iff the order in which the points $s_{\gamma_1},t_{\gamma_1},s_{\gamma_2},t_{\gamma_2}$ appear on the boundary of $D$ is either $(s_{\gamma_1},s_{\gamma_2},t_{\gamma_1},t_{\gamma_2})$ or $(s_{\gamma_1},t_{\gamma_2},t_{\gamma_1},s_{\gamma_2})$.

We first compute, for each $\gamma\in \Gamma$, a curve $\tilde\gamma$ inside disc $D$ connecting $s_{\gamma}$ to $t_{\gamma}$, such that (i) the curves in $\set{\tilde\gamma\mid \gamma\in \Gamma}$ are in general position; and (ii) for each pair $\gamma_1,\gamma_2$ of curves in $\Gamma$, the curves $\tilde\gamma_1$ and $\tilde\gamma_2$ intersects iff the order in which the points $s_{\gamma_1},t_{\gamma_1},s_{\gamma_2},t_{\gamma_2}$ appear on the boundary of $D$ is either $(s_{\gamma_1},s_{\gamma_2},t_{\gamma_1},t_{\gamma_2})$ or $(s_{\gamma_1},t_{\gamma_2},t_{\gamma_1},s_{\gamma_2})$.
It is clear that this can be achieved by first setting, for each curve $\gamma$, the curve $\tilde \gamma$ to be the line segment connecting $s_{\gamma}$ to $t_{\gamma}$, and then slightly perturb these curves so that no point belong to at least three curves in $\set{\tilde \gamma\mid \gamma\in \Gamma}$.
We now define, for each $\gamma\in \Gamma$, the curve $\tilde\gamma$ to be the union of the part of $\gamma$ outside $D$ and the curve $\tilde\gamma$.
See Figure <ref> for an illustration.
Clearly, all conditions of <Ref> are satisfied.

[Before: Curves of $\Gamma$ are shown in distinct colors. ]0.32

[After: Curves of $\set{\tilde\gamma\mid \gamma\in \Gamma}$ are shown in dash lines.]
An illustration of the proof of <Ref>.

We now use <Ref> to prove <Ref>.

Denote $G'=G\setminus C$ and denote $\hat \qset=\qset\cup \qset'$.
For each $e\in E(G')$, we let set $\Pi_{e}$ contain $\cong_{G'}(\hat \qset,e)$ curves connecting the endpoints of $e$ that are internally disjoint and lying inside an arbitrarily thin strip around the curve $\phi(e)$. We then assign, for each path $Q\in \hat \qset$ and each edge $e\in E(Q)$, a distinct curve of $\Pi_{e}$ to $Q$, so each curve in $\bigcup_{e\in E(G')}\Pi_{e}$ is assigned to exactly one path of $Q$.
For each $e\in \delta_G(C)$, let $\zeta_Q$ be the curve obtained by concatenating all curves in $\bigcup_{e\in E(G')}\Pi_{e}$ that are assigned to $Q$, so $\zeta_Q$ connects $\phi(s_Q)$ to $\phi(t^*)$.
We denote $Z=\set{\zeta_Q\mid Q\in \hat \qset}$.
In fact, when we assign curves of $\bigcup_{e\in \delta_{G'}(t^*)}\Pi_{e}$ to path of $\hat\qset$, we additionally ensure that the order in which the curves of $\set{\zeta_Q\mid Q\in \hat \qset}$ enter $\phi(t^*)$ is identical to $\oset^{\guided}(\hat\qset,\oset_{t^*})$, the ordering guided by the set $\hat\qset$ of paths and the ordering $\oset_{t^*}$. Note that this can be easily achieved according the the definition of $\oset^{\guided}(\hat\qset,\oset_{t^*})$.

We then modify the curves of $Z$ as follows.
For each vertex $v\in V(G')$, we denote by $x_v$ the point that represents the image of $v$ in $\phi$, and we let $X$ contain all points of $\set{x_v\mid v\in V(G')}$ that are crossings between curves in $Z$, so $x_{t^*}\notin X$.
We then iteratively process all points of $X$ as follows.
Consider a point $x_v$ of $X$ and let $D_{\phi}(v)$ be a tiny $v$-disc.
Let $Z(v)$ be the subset of all curves in $Z$ that contains $x_v$.
Let $Z'(v)$ be the set of curves we obtain by applying the algorithm from <Ref> to modify the curves of $Z(v)$ within disc $D_{\phi}(v)$. We then replace curves of $Z(v)$ in $Z$ by curves of $Z'(v)$, and continue to the next iteration. Let $\Gamma'$ be the set of curves that we obtain after processing all points of $X$ in this way.
Note that the curves of $\Gamma'$ might be non-simple,  and a pair of curves in $\Gamma'$ may cross more than once. We then remove self-loops from all curves of $\Gamma'$, and perform type-1 uncrossing (the algorithm from <Ref>) to curves of $\Gamma'$, and finally denote by $\Gamma=\set{\gamma(Q)\mid Q\in \hat\qset}$ the set of curves we obtained. This finishes the construction of the set $\Gamma$ of curves.

From <Ref> and the construction of $\Gamma$, it is easy to verify that the first and the second properties are satisfied.
We now show that $\Gamma$ satisfies the fourth property.
Since our operations at vertex-images only modify the image of curves within tiny discs around inner-vertex-images but does not change the course of any curves, and since type-1 uncrossing does not change the last segment of curves in $\Gamma'$ (and therefore does not change the ordering in which curves of $\Gamma'$ enter $\phi(t^*)$), the curves of $\Gamma$ enter $\phi(t^*)$ in the order $\oset^{\guided}(\hat\qset,\oset_{t^*})$.
We next show that $\Gamma$ satisfies the fifth property.
Note that the curves of $\Gamma$ all lie within thin strips of the image of edges of $E(\hat\qset)$ in $\phi$, and for each edge $e'\in E(G')$, the number of segments in $\Gamma$ that lie entirely within the thin strip of $\phi(e')$ is bounded by $\cong_{G'}(\hat\qset,e')$. Therefore, the number of crossings between the image of any edge $e\in E(C)$ and the curves of $\Gamma$ is bounded by the sum, over all edges $e'\in E(G')$, the number of crossings between $e$ and $e'$ in $\phi$, times $\cong_G(\hat\qset, e')$, which is in turn bounded by $\chi_{\phi}(e, G\setminus C)\cdot \cong_G(\hat\qset)$.

It remains to show that $\Gamma$ satisfies the third property, and this is the only place where we treat path sets $\qset$ and $\qset'$ differently. First, since we performed type-1 uncrossing to the set $\Gamma'$ of curves in the last step, the number of crossings between curves of $\Gamma(\qset')=\set{\gamma(Q)\mid Q\in \qset'}$ is at most $|\qset'|^2$.

Second, we bound the number of crossings between curves of $\Gamma(\qset)=\set{\gamma(Q)\mid Q\in \qset}$, as follows.
On the one hand, it is easy to verify that, if we denote $Z(\qset)=\set{\zeta_Q\mid Q\in \qset}$, then the number of non-vertex-image crossings between curves of $Z(\qset))$ is at most $\chi^2_{\phi}(\qset)$.
Note that

\[
\begin{split}
\chi^2_{\phi}(\qset)
\le & \sum_{e,e'\in E(G)}\chi_{\phi}(e,e')\cdot \cong_G(\qset,e)\cdot \cong_G(\qset,e')\\
\le & \sum_{e,e'\in E(G)}\chi_{\phi}(e,e')\cdot \frac{(\cong_G(\qset,e))^2+ (\cong_G(\qset,e'))^2}{2}\\
\le & \sum_{e\in E(G)}\chi_{\phi}(e)\cdot(\cong_G(\qset,e))^2.
\end{split}
\]

On the other hand, in the step where we repeatedly apply the algorithm from <Ref> to the set $Z$ of curves, it is not hard to verify that, if a crossing between two curves $\gamma(Q)$ and $\gamma(Q')$ (where $Q,Q'\in \qset$) is introduced in this step, then either they share an edge, or their intersection is transversal at a common inner vertex. The number of pairs of paths in $\qset$ that share an edge is bounded by $\sum_{e\in E(G)}(\cong_G(\qset,e))^2$. The number of pairs of paths in $\qset$ whose intersection is transversal at some of their common inner vertex is bounded by $\ntcost(\qset;\Sigma)$.
Third, using similar arguments, we can show that the number of crossings between a curve of $\Gamma(\qset)$ and a curve of $\Gamma(\qset')$ is at most
$$\ntcost(\qset,\qset';\Sigma)+\sum_{e\in E(G)} \cong_G(\qset,e)\cdot\cong_G(\qset',e)+
\sum_{e,e'\in E(G)}
\chi_{\phi}(e,e')\cdot \cong_G(\qset,e)\cdot\cong_G(\qset',e').$$

Altogether, they imply that $\Gamma$ satisfies the third property.

This completes the proof of <Ref>.

§.§ Proof of <Ref>

We construct a feasible solution $\phi'$ of $(G',\Sigma')$ as follows.
Recall that we are given a solution $\phi$ of instance $(G,\Sigma)$. We start with drawing $\phi(G\setminus E(\pset))$, the drawing of subgraph $G\setminus E(\pset)$ induced by $\phi$. It remains to add the images of $\set{e_P\mid P\in \pset}$ to $\phi(G\setminus E(\pset))$, which we do as follows.

For each path $P\in \pset$, we denote $\gamma_P=\phi(P)$ the image of $P$ in $\phi$, so $\gamma_P$ is a curve (possibly non-simple) connecting $\phi(s)$ to $\phi(t)$.
Denote $\Gamma=\set{\gamma_P\mid P\in \pset}$.
We iteratively modify the curves in $\Gamma$, by processing all vertices of $V(\pset)$ one-by-one as follows.
Consider a vertex $v\in V(P)$. Denote $\Gamma_v=\set{\gamma_P\mid v\in V(P)}$. We apply <Ref> to curves in $\Gamma_v$ within an arbitrarily small disc $D_v$ around $\phi(v)$, and get a new set $\Gamma'_v=\set{\gamma'_P\mid \gamma_P\in \Gamma_v}$ of curves. We then replace the curves of $\Gamma_v$ in $\Gamma$ with curves of $\Gamma_v$. This completes the iteration of processing vertex $v$.
Note that, since the paths of $\pset$ are edge-disjoint and non-transversal with respect to $\Sigma$, the curves of $\Gamma_v$ do not cross in $D_v$.
Let $\Gamma^*=\set{\gamma_P\mid P\in \pset}$ be the set of curves we get after processing all vertices of $V(P)$ in this way.

Note that curves of $\Gamma^*$ may be non-simple. We then delete self-loops of for each curve of $\Gamma^*$. We then add curves of $\Gamma^*$ to the drawing $\phi(G\setminus E(\pset))$, where for each $P\in \pset$, the curve $\gamma^*_{P}$ is designated as the image of $e_P$.
Let $\phi'$ be the resulting drawing. It is easy to verify that the $\phi'$ is a feasible solution of the instance $(G',E')$.
Since we have not created additional crossings in the process of obtaining the curves of $\Gamma^*$, any crossing in $\phi'$ is also a crossing in $\phi$. We then conclude that $\cro(\phi')\le \cro(\phi)$.

§.§ Proof of <Ref>

To Complete.

previous type-2 unucrossing

§.§ Proof of Theorem <ref>

We use similar arguments as in the proof of Theorem <ref>.

Let $Z$ be the set of points that lie on at least two curves of $\Gamma$. For each point $z\in Z$, let $D_z$ be an arbitrarily small disc around point $z$, such that, if $z$ lies on curves $\gamma_{1},\ldots,\gamma_{k}$, then

* the disc $D_z$ is disjoint from all curves of $\Gamma\setminus\set{\gamma_{1},\ldots,\gamma_{k}}$;

* for each $1\le i\le k$, the intersection between disc $D_z$ and curve $\gamma_i$ is a simple subcurve of $\gamma_i$; and

* for each $1\le i\le k$, the curve $\gamma_i$ intersects the boundary of $D_z$ at two distinct points.

Moreover, all discs in $\set{D_z}_{z\in Z}$ are mutually disjoint.

We now process the sets $\Gamma_1,\ldots,\Gamma_r$ of curves one-by-one.
We will describe the algorithm for processing the set $\Gamma_1$, and the algorithms for processing sets $\Gamma_2,\ldots,\Gamma_r$ are the same.
The algorithm for processing the set $\Gamma_1$ is iterative.
Throughout, we maintain (i) a set $\hat{\Gamma}_1$ of curves, that is initialized to be $\Gamma_1$; and (ii) a set $\hat Z$ of points that lie in at least two curves of $\hat\Gamma_1\cup (\Gamma\setminus \Gamma_1)$, that is initialized to be $Z$.
The algorithm continues to be executed as long as there is still a point that lies on at least two curves of $\hat \Gamma_1$ and is an inner point of each of these curves.
We now describe an iteration.
We first arbitrarily pick such a point $z$, and let $\gamma_{1},\ldots,\gamma_{k}$ be the curves that contains $z$.
For each $1\le i\le k$, we denote by $s_i$ the first endpoint of $\gamma_i$ and by $t_i$ the last endpoint of $\gamma_i$, and denote by $s'_i, t'_i$ the intersections between curve $\gamma_i$ and the boundary of disc $D_z$, such that the points $s_i,s'_i,z,t'_i,t_i$ appear on the directed curve $\gamma_i$ in this order.

[Before: Curves $\gamma_1,\gamma_2,\gamma_3,\gamma_4,\gamma_5$ are shown in red, yellow, pink, black and green respectively. The points of $S'\cup T'$  appear on the boundary of disc $D_z$.]0.33

[The set $\set{\eta^i_z\mid 1\le i\le k}$ of curves connecting distinct vertices of $S'$ to distinct vertices of $T'$ are shown in dash purple lines.]

[After: New curves $\hat\gamma_1,\hat\gamma_2,\hat\gamma_3,\hat\gamma_4,\hat\gamma_5$ are shown in red, yellow, pink, black and green respectively. Point $z$ no longer lies in any of these curves.]
An illustration of an iteration in type-1 uncrossing.

We now modify the curves $\gamma_1,\ldots,\gamma_k$ as follows. Denote $S'=\set{s'_i\mid 1\le i\le k}$ and $T'=\set{t'_i\mid 1\le i\le k}$. We first use the algorithm in <Ref> to compute a set $\set{\eta^{i}_z\mid 1\le i\le k}$ of curves, such that

* for each $1\le i\le k$, the curve $\eta_z^i$ connects $s'_i$ to a distinct point $t'_{x_i}$ of $T'$;

* for each $1\le i\le k$, the curve $\eta_z^i$  lies entirely in the disc $D_z$; and

* the curves in $\set{\eta^{i}_z\mid 1\le i\le k}$ are mutually disjoint.

Note that the algorithm in <Ref> only gives us a matching between points in $S'$ and points $T'$, but it can be easily tranformed into a set of curves satisfying the above properties.
See Figure <ref> for an illustration.
For each $1\le i\le k$, we denote by $\gamma^s_i$ the subcurve of $\gamma_i$ between $s_i$ and $s'_i$, and by $\gamma^t_i$ the subcurve of $\gamma_i$ between $t'_i$ and $t_i$.
We then define, for each $1\le i\le k$, a new curve $\hat \gamma_i$ to be the sequential concatenation of curves $\gamma^s_i, \eta^i_z, \gamma^t_{x_i}$.
See Figure <ref> for an illustration.
We then replace the curves $\gamma_1,\ldots,\gamma_k$ in $\hat\Gamma_1$ with the new curves $\hat\gamma_1,\ldots,\hat\gamma_k$. This completes the description of an iteration.
Let $\Gamma'_1$ be the set of curves that we obtain at the end of the algorithm, and let $Z'$ be set of points that lie on at least two curves of $\Gamma'_1\cup (\Gamma\setminus \Gamma_1)$.

It is easy to verify that, in the iteration described above, the multiset of the first endpoints of new curves $\hat\gamma_1,\ldots,\hat\gamma_k$ is identical to that of the original curves $\gamma_1,\ldots,\gamma_k$ and similarly the multiset of the last endpoints of new curves $\hat\gamma_1,\ldots,\hat\gamma_k$ is identical to that of the original curves $\gamma_1,\ldots,\gamma_k$.
Therefore, $S(\Gamma'_1)=S(\Gamma_1)$ and $T(\Gamma'_1)=T(\Gamma_1)$.
It is also easy to verify that the point $z$ no longer lies in any of the new curves $\hat\gamma_1,\ldots,\hat\gamma_k$, while other points in $\hat Z$ remains in $\hat Z$, and there are no new points added to $\hat Z$.
So in each iteration, one point is removed from $\hat Z$, and therefore the algorithm of processing $\Gamma_1$ will terminate in $O(\chi(\Gamma_1))$ rounds.
Moreover, from the terminating criterion of the algorithm, the curves in the resulting set $\Gamma_1'$ no longer cross with each other.

For each $1\le i\le r$, let $\Gamma'_i$ be the set of curves that we obtain from processing the set $\Gamma_i$ of curves using the same algorithm.
We now show that the sets $\Gamma_1,\ldots,\Gamma_r$ satisfy the conditions in <Ref>.

First, from the above discussion, for each $1\le i\le r$, $S(\Gamma'_i)=S(\Gamma_i)$ and $T(\Gamma'_i)=T(\Gamma_i)$.
Second, if we denote by $Z'$ the set of points that lie in at least two curves of $\Gamma'=\Gamma_0\cup(\bigcup_{1\le i\le r}\Gamma'_i)$, then clearly $Z'\subseteq Z$, and for each $1\le i\le r$, $Z'$ does not contain a point lying in at least two curves of $\Gamma'_i$.
It follows that for each $1\le i\le r$, curves in $\Gamma_i$ do not cross each other; for every curve $\gamma\in \Gamma_0$, $\chi(\gamma,\Gamma'\setminus \Gamma_0)\le \chi(\gamma,\Gamma\setminus \Gamma_0)$; and
$\chi(\Gamma')\le \chi(\Gamma)$.
Last, it is easy to verify from the algorithm that,
if a point is an endpoint of a curve in $\Gamma'$, then it may not be an inner point of any other curve in $\Gamma'$.
Moreover, if a point of $Z$ lie in more than 2 curves in $\Gamma'$, then it has to be an endpoint of every curve that contains it.
Therefore, curves in $\Gamma'$ are in general position.
This completes the proof of <Ref>.

previous type-2 uncrossing

Let $\cset=\set{C_1,\ldots,C_r}$.
We partition the set $E(G')$ of edges into subsets $E_0,E_1,\ldots,E_r$ as follows: for all $1\leq i\leq r$, $E_i=E(C'_i)$, and $E_0$ contains all edges that do not lie in any cluster $C'_1,\ldots,C'_r$. We let $\chi_1$ be the set of all crossings $(e,e')$ in $\phi'$, with $e,e'$ lying in the same set $E_i$, for $0\leq i\leq r$, and we let $\chi_2$ be the set of all crossings $(e,e')$ in $\phi'$ where $e\in E_i$, $e'\in E_j$, and $i\neq j$.

Consider now some index $1\leq i\leq r$, and some edge $e\in E(C'_i)$. If $e$ does not participate in any path in $\qset(C_i)$, then we set $n_e=1$; otherwise, we let $n_e=\cong(\qset(C_i),e)$ be the number of paths in $\qset(C_i)$, in which the edge $e$ participates. For each edge $e\in E_0$, we set $n_e=1$.

Let $G''$ be the graph obtained from $G'$, where we replace every edge $e\in E(G')$ with $n_e$ parallel copies. For all $0\leq i\leq r$, we denote by $E'_i$ the set of edges of $G''$ corresponding to the edges of $E_i$. Drawing $\phi'$ of $G'$ naturally defines a drawing $\phi''$ of $G''$: for every edge $e\in E(G')$, we draw the $n_e$ parellel copies of the edge $e$ next to each other, in parallel to the original drawing of the edge $e$ and very close to it.

We denote by $\chi_1'$ the set of all crossings $(e,e')$ in the resulting drawing $\phi''$, where both $e$ and $e'$ lie in the same set $E'_i$ of edges, for any $0\leq i\leq r$, and we let $\chi_2'$ be the set of all crossings $(e,e')$ in $\phi''$, where $e\in E_i'$, $e'\in E_j'$, and $0\leq i<j\leq r$. We use the following simple observation to bound the number of crossigns in $\chi_2'$.

\[\expect{|\chi_2'|}\leq |\chi_2|\cdot O(\log^8n/\alpha^2).\]

Consider some crossing $(e_1,e_2)\in \chi_2'$. Then there must be a crossing $(e_1',e_2')\in \chi_2$, where $e_1$ is a copy of $e_1'$ and $e_2$ is a copy of $e_2'$. We say that crossing $(e_1',e_2')$ is responsible for the crossing $(e_1,e_2)$. We have now assigned, to each crossing in $\chi_2'$, a crossing in $\chi_2$ that is responsible for it.

Consider now some crossing $(e,e')\in \chi_2$. The number of crossings in $\chi_2'$ that it is responsible for is precisely $n_e\cdot n_{e'}$. Assume that $e\in E_i,e'\in E_j$, for some $0\leq i,j\leq r$, with $i\neq j$. Since $i\neq j$, $n_e$ and $n_{e'}$ are independent random variables. Therefore, $\expect{n_e\cdot n_{e'}}=\expect{n_e}\cdot \expect{n_{e'}}\leq O(\log^8n/\alpha^2)$.

Altogether, we get that:

\[\expect{|\chi_2'|}\leq \expect{\sum_{(e,e')\in \chi_2}n_e\cdot n_{e'}}\leq \sum_{(e,e')\in \chi_2}\expect{n_e\cdot n_{e'}}\leq |\chi_2|\cdot O(\log^8n/\alpha^2).\]

Let $\chi_0$ be the set of all crossings $(e,e')$ in the drawing $\phi'$ in which $e,e'\in E_0$.

For all $1\leq i\leq r$, let $C''_i$ be the subgraph of $G''$ induced by the vertices of $C'_i$. We can now define a set $\qset'(C_i)$ of paths in graph $C''_i$, routing the vertices of $T_{C_i}$ to $u_C$, such that the paths in $\qset'(C_i)$ are edge-disjoint. In order to do so, we simply assign, for each edge $e\in E_i$, a distinct copy of $e$ to every path $Q_t\in \qset(C_i)$ that contains $e$.

Next, we define a collection $\Gamma_0,\Gamma_1,\ldots,\Gamma_r$ of curves, as follows. For each edge $e\in E_0$, we add a curve $\gamma(e)$ to $\Gamma_0$, where $\gamma(e)$ is the image of the edge $e$ in the drawing $\phi''$.

Consider now some index $1\leq i\leq r$. We start by letting $\Gamma_i$ contain the set of images of all paths in $\qset'(C_i)$ in the drwaing $\phi'$; in other words, we can denote $\Gamma_i=\set{\gamma_i(t)\mid t\in T_C}$, where $\gamma_i(t)$ is the image of the unique path $Q'_t\in \qset'(C_i)$, connecting $t$ to $u(C_i)$. We direct all curves in $\Gamma_i$ towards the image of $u(C_i)$, and we delete loops from each resulting curve, so that all curves in set $\Gamma_i$ become simple.

Consider the resulting collection $\Gamma=\Gamma_0\cup\Gamma_1\cup\cdots \Gamma_r$ of curves. Let $p$ be any point that lies on more than two such curves.
Assume first that $p$ is an image of some vertex $v\in V(G'')$. If there is some index $1\leq i\leq r$, such that $v\in V(C_i)$, then every curve $\gamma\in \Gamma$ that contains $v$ must belong to $\Gamma_i$. Otherwise, for every curve $\gamma\in \Gamma$ with $p\in \gamma$, point $p$ is an endpoint of $\gamma$.
Assume now that $p$ is not an image of a vertex in $V(G'')$, so it is an inner point on the image of some edge of $G''$. I this case, from the definition of a graph drawing, $p$ may lie on images of at most two edges of $G''$, and so it may not belong to more than three curves of $\Gamma$.

To conclude, if a point $p$ lies on more than $2$ curves of $\Gamma$, then either it is an endpoint of every curve $\gamma$ containing $p$, or there is some index $1\leq i\leq r$, such that every curve $\gamma$ containing $p$ belongs to $\Gamma_i$.

we then use the algorithm from <Ref> in order to uncross each set $\Gamma_i$ of curves, for $1\leq i\leq r$. Recall that we obtain new sets $\Gamma'_1,\ldots,\Gamma'_r$ of curves. For each $1\leq i\leq r$ and $t\in T_C$, we denote by $\gamma'_i(t)$ the unique curve in $\Gamma'_i$ that originates at the image of $t$ and terminates at the image of $u(C_i)$.

from here on needs to be fixed once the statement of  <Ref> is fixed
Recall that <Ref>, we are guaranteed that, if $p$ is a point lying on more than two curves in $\Gamma_0\cup \Gamma'_1\cup\cdots\cup\Gamma'_r$, then $p$ is an endpoint of all these curves, and that the total number of crossings between all curves in $\Gamma_0\cup \Gamma'_1\cup\cdots\cup\Gamma'_r$ is bounded by $|\chi_2'|+|\chi_0|$.

We are now ready to define the drawing $\phi$ of graph $G_{|\cset}$. We start from the drawing $\phi'$ of $G'$.
For every cluster $C_i\in \cset$, we delete the images of all vertices of $C$, except for $u_C$, and of all edges of $E(C')$. The image of $u_C$ becomes the image of the vertex $v(C)$ representing the cluster $C$ in the contracted graph. We then add the curves in $\Gamma'_i$ to this drawing; recall that each such curve connects $u(C)$ to a distinct vertex $t\in T_C$. Once all clusters $C_i\in \cset$ are processed, we obtain  a drawing of a graph $\hat G$, that is obtained from $G_{|\cset}$ by subdividing every edge $e\in \bigcup_{C\in \cset}\delta(v(C))$ with a vertex $t_e$. The set of images of the edges of $\hat G$ in this drawing is precisely $\Gamma_0\cup \Gamma'_1\cup\cdots\cup\Gamma'_r$, and so the number of crossings in this drawing is bounded by $|\chi_2'|+|\chi_0|$. This drawing of $\hat G$ immediately defines a drawing of $G_{|\cset}$, by surpressing the images of all vertices $\set{t_e\mid e\in \bigcup_{C\in \cset}\delta(v(C))}$. The number of crossings in this final drawing is bounded by $|\chi_2'|+|\chi_0|$. Clearly, $|\chi_0|\leq \optcrors(I)$, since we did not modify the drawings of the edges in $E_0$, and each edge $e\in E_0$ has $n_e=1$.
$\expect{|\chi_2'|}\leq |\chi_2|\cdot O(\log^8n/\alpha^2)$. Moreover, since we did not modify the drawings of the edges in $E_0$, it is easy to verify that for every vertex $x\in V(G_{|\cset})\cap V(G)$, the ordering of the edges of $\delta_G(x)$ as they enter $x$ in the final drawing $\phi$ is consistent with the ordering $\oset_x\in \Sigma$.

to modify using new type-2 uncrossing

§.§ Proof of <Ref>

To add.

§.§ Proof of <Ref>

For each $1\le i\le n-1$, we denote $S_{i}=\set{v_1,\ldots,v_i}$ and  $\notS_{i}=\set{v_{i+1},\ldots,v_n}$.

Let $v_C,v_{C'}$ be two vertices that appear consecutively on the contracted path $\tau_{\cset}$, where $v_C$ corresponds to cluster $C$ and $v_{C'}$ corresponds to cluster $C'$ ($C,C'\in \cset$). We denote $C=\set{v_p,\ldots,v_r}$ and $C'=\set{v_{r+1},\ldots,v_q}$.
Since path $\tau$ is a Gomory-Hu tree of $G$, then the cut $(S_r,\notS_r)$ is a min-cut in $G$ separating $v_r$ from $v_{r+1}$.
On the other hand, note that any cut separating $v_C$ from $v_{C'}$ in the contracted graph $G_{\cset}$ corresponds to a cut in the original graph $G$ separating $v_r$ from $v_{r+1}$, with the same set of edges. Moreover, if we denote by $S,\notS$ the components of $\tau$ obtained by removing the edge $(v_C,v_{C'})$ from $\tau$, then the cut $(S,\notS)$ in $G_{\cset}$ corresponds to the cut $S_r,\notS_r$ in $G$. Therefore, the cut $(S,\notS)$ is a min-cut in $G_{\cset}$ separating $v_C$ from $v_{C'}$. It follows that $\tau_{|\cset}$ is a Gomory-Hu tree of the contracted graph $G_{|\cset}$.

§ PROOFS OMITTED FROM <REF>

§.§ Proof of <Ref>

In this proof, we assume that all drawings are on the sphere.
For every cluster $C\in \lset$, denote by $\wset(C)\subseteq \lset$ the set of all child clusters of $C$, and by $\wset^*(C)\subseteq \lset$ the set of all descendant clusters of $C$. We define a new instance $I'_C=(G'_C,\Sigma'_C)$ of associated with cluster $C$, as follows. If $C=G$, then $G'_C=G$ and $\Sigma'_C=\Sigma$. Otherwise, graph $G'_C$ is obtained from graph $G$, by contracting all vertices of $V(G)\setminus V(C)$ into a supernode $v^*$. Rotation system $\Sigma'_C$ is defined as follows. Note that $\delta_{G'_C}(v^*)=\delta_G(C)$. We define the rotation $\oset_{v^*}\in \Sigma'_C$ to be $\oset(C)$. For every other vertex $v\in V(G'_C)$, $\delta_{G'_C}(v)=\delta_G(v)$ holds, and its rotation $\oset_v\in \Sigma'_C$ remains the same as in $\Sigma$. This completes the definition of instance $I'_C$.
Notice that instance $I_C$ can be obtained from instance $I'_C$ by contracting, for each cluster $C'\in \wset(C)$, the vertices of $C'$ into a supernode $v_{C'}$, and then setting the rotation of the edges incident to this supernode to $\oset(C')$.

We prove by induction that there is an efficient algorithm, that, given a cluster $C\in \lset$, and solutions $\set{\phi(I_{C'})}_{C'\in \wset^*(C)}$ to instances associated with the descendant clusters of $C$, computes a solution $\phi'(I'_C)$ to instance $I'_C$, of cost at most $\sum_{C'\in \wset^*(C)}\phi(I_{C'})$. Since $I'_G=I$, this will complete the proof of the lemma.

The proof is by induction of the length of the longest path in the partitioning tree $\tau(\lset)$ between $v(C)$ and its descendant. The base of the induction is when cluster $C$ is the leaf of the tree $\tau(\lset)$. In this case, $I'_C=I_C$ holds, and we let $\phi'(I'_C)=\phi(I_C)$.

For the induction step, we consider some cluster $C\in \lset$, whose corresponding vertex $v(C)$ is not a leaf vertex of the tree $\tau(\lset)$.
Assume that $\wset(C)=\set{C_1,\ldots,C_r}$. For convenience, for each $1\leq i\leq r$, we denote the supernode $v_{C_i}$ representing cluster $C_i$ in graph $G_C$ by $v_i$. By applying the induction hypothesis to every cluster $C_i\in \wset(C)$, we obtain a solution $\phi'_i=\phi'(I'_{C_i})$ to instance $I'_{C_i}$ of , whose cost is $\cro(\phi'_i)\leq \sum_{C'\in \wset^*(C_i)}\cro(\phi(I_{C'}))$. It is now enough to show an efficient algorithm that constructs a solution $\phi'(I'_C)$ to instance $I'_C$, whose cost is at most $\cro(\phi(I_C))+\sum_{i=1}^r\cro(\phi'_i)\leq \sum_{C'\in \wset^*(C)}\cro(\phi(I_{C'}))$.

We start with the solution $\tilde \phi=\phi(I_C)$ to instance $I_C$, and we process the clusters $C_1,\ldots,C_r$ one by one, gradually modifying the drawing $\tilde \phi$. We now describe the iteration when cluster $C_i$ is processed. We denote $\delta_{G'_C}(v_i)=\delta_G(C_i)=\set{e^i_1,\ldots,e^i_{q_i}}$, where the edges are indexed according to their ordering in $\oset(C_i)$.
For all $1\leq j\leq q_i$, we denote $e^i_j=(x_j,y_j)$, where $x_j\in C_i$.
Let $D_i=D_{\tilde \phi}(v_i)$ be a tiny $v_i$-disc in the drawing $\tilde \phi$. For all $1\leq j\leq q_i$, we denote by $p^i_j$ the unique point on the image of edge $e^i_j$ that lies on the boundary of the disc $D_i$, and we let $\gamma(e^i_j)$ denote the segment of the image of $e^i_j$ that is disjoint from the interior of $D_i$. Therefore, $\gamma(e^i_j)$ connects the image of vertex $y_j$ to point $p^i_j$. Notice that points $p^i_1,\ldots,p^i_{q_i}$ appear on the boundary of $D_i$ in this circular order. If the orientation of this ordering is positive, then we say that vertex $v_i$ is positive, and otherwise we say that it is negative. We erase the parts of the images of all edges in the interior of disc $D_i$, and we erase the image of the vertex $v_i$ from the current drawing. We place another disc $D'_i$ inside $D_i$, so that $D'_i\subseteq D_i$, and the boundaries of both discs are disjoint.

Next, we consider the drawing $\phi'_i$ of the graph $G'_{C_i}$. We let $\hat D_i=D_{\phi'_i}(v^*)$ be a tiny $v^*$-disc in this drawing. Recall that $\delta_{G'_{C_i}}(v^*)=\delta_G(C_i)$. For all $1\leq j\leq q_i$, we denote by $\hat p^i_j$ the unique point on the image of the edge $e^i_j$ in $\phi'_i$ that lies on the boundary of the disc $\hat D_i$. Note that points $\hat p^i_1,\ldots,\hat p^i_{q_i}$ must appear on the boundary of the disc $\hat D_i$ in this circular order, from the definition of the rotation $\oset_{v^*}\in \Sigma'_{C_i}$. We assume w.l.o.g. that, if vertex $v_i$ is positive, then the orientation of this ordering is negative, and otherwise it is positive (if this is not the case then we simply flip the drawing $\phi'_i$). Let $\hat D'_i$ be the disc that has the same boundary as $\hat D_i$ but whose interior is disjoint from that of $\hat D_i$ (so $\hat D'_i$ is the complement of disc $\hat D_i$; recall that the drawing $\phi'_i$ is on the sphere). For all $1\leq j\leq q_i$, we denote by $\gamma'(e^i_j)$ the segment of the image of edge $e^i_j$ that lies inside $\hat D'_i$. Therefore,  $\gamma'(e^i_j)$ connects the image of vertex $x_j$ to point $\hat p^i_j$.

We copy the disc $\hat D'_i$, together with its contents (in $\phi'_i$), to the current drawing $\tilde \phi$, so that the boundaries and the interiors of the discs $\hat D'_i$ and $D'_i$ coincide.
Assume w.l.o.g. that vertex $v_i$ is positive. Then points $p^i_1,\ldots,p^i_{q_i}$ appear on the boundary of disc $D'_i$ in this counter-clock-wise order, while points $\hat p^i_1,\ldots,\hat p^i_{q_i}$ appear on the boundary of disc $\hat D'_i$ in this counter-clock-wise order. Therefore, we can compute a collection $\set{\sigma_1,\ldots,\sigma_{q_i}}$ of mutually disjoint curves, where for all $1\leq j\leq q_i$, curve $\sigma_j$ has endpoints $p_j^i$ and $\hat p_j^i$, and all inner points of $\sigma_j$ lie in $D_i\setminus D'_i$, and are disjoint from the boundary of $D_i$. For all $1\leq j\leq q_i$, we now define the image of the edge $e_j=(x_j,y_j)$ to be the concatenation of the curves $\gamma^i_j,\sigma_j$, and $\hat \gamma^i_j$.

Once every cluster $C_i\in \wset(C)$ is processed in this manner, we obtain a solution $\phi'(I'_C)$ to instance $I'_C$ of . It is immediate to verify that the total number of crossings in this solution is at most $\cro(\phi(I_C))+\sum_{i=1}^r\cro(\phi'_i)\leq \sum_{C'\in \wset^*(C)}\cro(\phi(I_{C'}))$. The lemma follows by letting $\phi$ be the solution $\phi'(I_{C'})$ that we construct for instance $I_{C'}$, where $C'=G$.

§.§ Proof of <Ref>

Throughout the proof, we denote $|E(G)|=m$.

Consider first a cluster $C\in \lset^{\gd}$. Recall that, in order to define instance $I_C$, we used the distribution $\dset(C)$ over the internal $C$-routers, where $C$ is $\beta$-light with respect to $\dset(C)$.
We selected a router $\qset(C)$ from the distribution $\dset(C)$ at random, whose center vertex is denoted by $u(C)$. We then used the algorithm from <Ref> to compute a non-transversal set $\tilde \qset(C)$ of paths, routing all edges of $\delta_G(C)$ to vertex $u(C)$, so $\tilde \qset(C)$ is also an internal $C$-router. The set $\tilde \qset(C)$ of paths was used in order to define the ordering $\oset(C)$ of the edges of $\delta_G(C)$, which was in turned used in order to define instance $I_C$.

Consider now a cluster $C\in \lset^{\bad}$. We apply the algorithm from <Ref> to $C$, obtaining a distribution $\dset(C)$ over the set $\Lambda(C)$ of internal $C$-routers, such that, for every edge $e\in E(C)$, $\expect[\qset\sim \dset]{\cong(\qset(C),e)}\leq  O(\log^4m/\alpha_0)\leq O(\log^{16}m)$. We then select a router $\qset(C)$ from the distribution $\dset(C)$ at random, and denote by $u(C)$ its center vertex. We view the paths of $\qset(C)$ as being directed towards  $u(C)$.
Next, we use the algoritm from <Ref> to compute a non-transversal set $\tilde \qset(C)$ of paths, routing all edges of $\delta_G(C)$ to vertex $u(C)$, so $\tilde \qset(C)$ is also an internal $C$-router. The algorithm ensures that, for every edge $e\in E(G)$,  $\cong_G(\tilde \qset(C),e)\leq \cong_G(\qset(C),e)$.

Consider an optimal solution $\phi^*$ to instance $I$ of . For every cluster $C\in \lset$, denote by $\chi(C)$ the set of all crossings $(e,e')_p$ in the drawing $\phi^*$, where at least one of the edges $e,e'$ lies in $E(C)\cup \delta_G(C)$.
Recall that $\iset=\set{I_C\mid C\in \lset}$. The proof of the lemma follows from the following claim.

For every cluster $C\in \lset$, $\expect{\optcrors(I_C)}\leq O(\beta^2\cdot(|\chi(C)|+|E(C)|))$.

Indeed, for all $1\leq i\leq \dep(\lset)$, let $\lset_i\subseteq \lset$ be the set of all clusters that lie at level $i$ of the laminar family. Note that all clusters in $\lset_i$ are mutually disjoint. Therefore, every crossing $(e,e')_p$ of the drawing $\phi^*$ may contribute to the sets $\chi(C)$ of at most four clusters of $\lset_i$: at most two clusters $C$ with $e\in E(C)\cup \delta_G(C)$, and at most  two clusters $C'$ with $e\in E(C')\cup \delta_G(C')$. Therefore:

\[
\sum_{C\in \lset_i}\expect{\optcrors(I_C)}\leq \sum_{C\in \lset_i} O(\beta^2\cdot(|\chi(C)|+|E(C)|)) \leq  O(\beta^2\cdot (\optcrors(I)+|E(G)|)).
\]

Summing this up over all  $1\leq i\leq \dep(\lset)$, we get that $\expect{\sum_{I'\in \iset}\optcrors(I')}\leq O(\dep(\lset)\cdot\beta^2\cdot (\optcrors(I)+|E(G)|))$. In order to complete the proof of <Ref>, it is now enough to prove <Ref>, which we do next.

In the remainder of this proof, we fix a cluster $C\in \lset$. Recall that there is a distribution $\dset'(C)$ over the set $\Lambda'(C)$ of external $C$-routers, such that for every edge $e$ of $E(G\setminus C)$,
$$\expect[\qset'(C)\sim\dset'(C)]{\cong_G(\qset'(C),e)}\leq \beta.$$

We sample an external $C$-router $\qset'(C)$ from the distribution $\dset'(C)$. We view the paths of $\qset'(C)$ as being directed towards vertex $u'(C)$, that is the center of the router. We apply the algorithm from <Ref> to obtain a collection $\tilde \qset'(C)$ of non-transversal paths, routing the edges of $\delta_G(C)$ to $u'(C)$, such that,  for every edge $e\in E(G)$, $\cong_G(\tilde \qset'(C),e)\leq \cong_G(\qset'(C),e)$. In particular, $\tilde \qset'(C)$ is also an external $C$-router with center vertex $u'(C)$.

In order to simplify the notation, we denote $\tilde \qset'(C)$ by $\qset'$, and $\tilde \qset(C)$ by $\qset$. To summarize, $\qset'$ is an external $C$-router, and we are guaranteed that, for every edge $e\in E(G\setminus C)$, $\expect{\cong_G(\qset',e)}\leq \beta$. Set $\qset$ of paths is an internal $C$-router. If $C\in \lset^{\bad}$, then for every edge $e\in E(C)$,
$\expect{\cong(\qset,e)}\leq  \beta$, while, if $C\in \lset^{\gd}$ then, for every edge $e\in E(C)$, $\expect{(\cong_G(\qset,e))^2}\leq \beta$.
We denote the center vertex of router $\qset$ by $u$, and the center vertex of router $\qset'$ by $u'$.

We denote by $\wset=\set{C_1,\ldots,C_r}$ the set of child-clusters of $C$. We partition $\wset$ into two subsets: $\wset^{\bad}=\wset\cap \lset^{\bad}$, and $\wset^{\gd}=\wset\cap \lset^{\gd}$. For convenience, for all $1\leq i\leq r$, we denote the internal $C_i$-router $\tilde \qset(C_i)$ that we have constructed by $\qset_i$, and its center vertex by $u_i$. Recall that, if $C_i\in \lset^{\bad}$, then  for every edge $e\in E(C_i)$,
$\expect{\cong(\qset_i,e)}\leq  \beta$, while, if $C_i\in \lset^{\gd}$ then, for every edge $e\in E(C_i)$, $\expect{(\cong_G(\qset_i,e))^2}\leq \beta$.

It will be convenient for us to also define another cluster $C_0$ to be the connected component of $G\setminus C$ containing the vertex $u'$ – the center vertex of the external $C$-router $\qset'$. It is immediate to verify that the set $\qset'$ of paths is an internal $C_0$-router, and for consistency we denote it by $\qset_0$. We also denote the center vertex of this router by $u_0=u'$. Recall that each one of the sets $\qset_0,\qset_1,\ldots,\qset_r$ of paths is non-transversal with respect to $\Sigma$.
For convenience, we denote $R=C\setminus\left(\bigcup_{i=1}^rC_i\right )$, and $\qset^*=\bigcup_{i=0}^r\qset_i$.

Lastly, it will be convenient for us to assume that no edge of $G$ has its endpoints in two distinct clusters of $C_0,C_1,\ldots,C_r$. For each such edge $e$, we subdivide the edge with a new vertex $v_e$, that is added to graph $R$ as an isolated vertex.
Note that, for all $0\leq i<j\leq r$, the only vertices that may be shared by paths in $\qset_i$ and paths in $\qset_j$ are vertices of $V(R)$, which must serve as endpoints of those paths.

The remainder of the proof of <Ref> consists of three steps. In the first step, we will define a new graph $H$ by slightly modifying graph $G$, and compute its drawing $\psi$. In the second step, we use graph $H$ and its drawing $\psi$ in order to construct an initial drawing $\phi'$ of graph $G_C$ (associated with instance $I_C=(G_C,\Sigma_C)\in \iset$ of ). This drawing, however, may not obey all rotations in $\Sigma_C$. In the third and the last step, we modify drawing $\phi'$ to obtain the final drawing $\phi''$ of $G_C$, that is a valid solution to instance $I_C$ of . We now describe each of the three steps in turn.

§.§.§ Step 1: Graph $H$

We assign, to every edge $e\in E(G)$, an integer $n_e\geq 0$, as follows. For every edge $e\in E(R)\cup \delta_G(R)$, we let $n_e=1$. For every other edge $e\in E(G)\setminus E(R)$, we let $n_e=\cong_G(\qset^*,e)$.

In order to construct graph $H$, we start with $V(H)=V(G)$. For every edge $e=(u,v)\in E(G)$ with $n_e>0$, we add a set $J(e)$ of $n_e$ parallel edges $(u,v)$ to graph $H$, and we call the edges of $J(e)$ copies of edge $e$. This completes the definition of the graph $H$. Note that graph $H$ is a random graph, as values $\set{n_e}_{e\in E(G)}$ are random variables.

Consider the optimal solution $\phi^*$ to instance $I$ of . We use $\phi^*$ in order to define a drawing $\psi$ of the graph $H$, in a natural way: for every vertex $v\in V(H)$, its image in $\psi$ remains the same as in $\phi^*$. For every edge $e\in E(G)$ with $n(e)\geq 1$, we draw the edges of $J(e)$ in parallel to the image of $e$ in $\phi^*$, immediately next to it, so that their images do not cross.
Consider the resulting drawing $\psi$ of graph $H$, and let $(e'_1,e'_2)_p$ be a crossing of $\psi$. Assume that $e'_1\in J(e_1)$ and $e'_2\in J(e_2)$. Then the images of the edges $e_1,e_2$ cross in $\phi^*$, at some point $p'$ that is very close to point $p$. We say that crossing $(e_1,e_2)_{p'}$ of $\phi^*$ is responsible for the crossing $(e_1',e_2')_p$ of $\psi$.

Next, we classify the crossings of the drawing $\psi$ into three types, and we bound the expected number of crossings of some of the types. Consider some crossing $(e'_1,e'_2)_p$ of $\psi$, and let $(e_1,e_2)_{p'}$ be the crossing of $\phi^*$ that is responsible for $(e_1',e_2')_p$. We say that crossing $(e'_1,e'_2)_p$ is a type-1 crossing if there is some cluster $C_i\in \wset^{\light}$, with $e_1,e_2\in E(C_i)$. We say that it is a type-2 crossing if there is an index $0\leq i\leq r$ with $e_1,e_2\in E(C_i)$, and either $i=0$ or $C_i\in\wset^{\bad}$ holds. We say that $(e_1',e_2')_p$ is a type-3 crossing otherwise.

We now bound the expected number of type-1 and type-3 crossings. We do not bound the number of type-2 crossings, as all such crossings will eventually be eliminated.

Type-1 crossings. Consider some cluster $C_i\in \wset^{\light}$, and some crossing $(e_1,e_2)_{p'}$ of $\phi^*$, such that $e_1,e_2\in E(C_i)$. Notice that crossing $(e_1,e_2)_{p'}$ lies in $\chi(C_i)$. The number of type-1 crossings in $\phi$ that this crossing is responsible for is $n_{e_1}\cdot n_{e_2}\leq n_{e_1}^2+n_{e_2}^2$. Observe that, for an edge $e\in E(C_i)$, $n_e=\cong_G(\qset_i,e)$, and so  $\expect{n_e^2}=\expect{(\cong_G(\qset_i,e))^2}\leq \beta$. We conclude that the total expected number of type-1 crossings in $\psi$ is bounded by:

\[ \sum_{C_i\in \wset^{\light}} \sum_{(e_1,e_2)_{p'}\in \chi(C_i)}\expect{n_{e_1}^2+n_{e_2}^2 }\leq   \sum_{C_i\in \wset^{\light}} O(\beta \cdot |\chi(C_i)|)\leq O(\beta\cdot |\chi(C)|).
\]

Type-3 crossings. Consider some crossing $(e_1,e_2)_{p'}$ of $\phi^*$. If edges $e_1,e_2$ lie in the same cluster $C_i$, for $0\leq i\leq r$, then this crossing may not be responsible for any type-3 crossings in $\psi$. Assume now that this is not the case. Then the total number of type-3 crossings that $(e_1,e_2)_{p'}$ is responsible for is at most $n_{e_1}\cdot n_{e_2}$. Furthermore $n_{e_1},n_{e_2}$ are independent random variables, each of which has expectation at most $\beta$. Therefore, the expected number of type-3 crossings for which crossing $(e_1,e_2)_{p'}$ is responsible is at most $\beta^2$. Note that, at least one of the edges $e_1,e_2$ must lie in $E(C)\cup \delta_G(C)$, so crossing $(e_1,e_2)_{p'}$  must lie in $\chi(C)$. We conclude that the total expected number of type-3 crossings in $\phi$ is at most $|\chi(C)|\cdot \beta^2$.

Consider now an index $0\leq i\leq r$, and let $E_i=\delta_G(C_i)$. From our definition, for every edge $e\in E_i$, $n_e=1$. Recall that we have defined a set $\qset_i=\set{Q(e)\mid e\in E_i}$ of paths in graph $G$, routing all edges of $E_i$ to the vertex $u_i\in V(C_i)$. The paths in $\qset_i$ are non-transversal with respect to $\Sigma$, and all their inner vertices are contained in $C_i$. We will now define a corresponding set $\hat \qset_i=\set{\hat Q(e)\mid e\in E_i}$ of paths in graph $H$, routing the edges of $E_i$ to the same vertex $u_i$, such that the paths in $\hat \qset_i$ are edge-disjoint. In order to do so, we assign, to every path $Q(e)\in \qset_i$, for every edge $e'\in E(Q(e))\setminus\set{e}$, a copy of the edge $e'$ from $J(e')$, such that every copy of edge $e'$ is assigned to a distinct path. We will then obtain path $\hat Q(e)$ from path $Q(e)$ by replacing every edge $e'\in E(Q(e))\setminus\set{e}$ with its copy that was assigned to $Q(e)$.

Consider any edge $e'\in E(C_i)$. If $e'$ is not incident to the vertex $u_i$, then we assign each copy of $e'$ to a distinct path in $\qset_i$ that contains $e'$ arbitrarily. Assume now that edge $e'$ is incident to vertex $u_i$, and that $C_i\not\in \wset^{\gd}$. In this case, as before, we assign  each copy of $e'$ to a distinct path in $\qset_i$ that contains $e'$ arbitrarily. It now remains to consider the case where $C_i\in \wset^{\gd}$, and edges that are incident to vertex $u_i$. We need to assign  copies of such edges to paths in $\qset_i$ more carefully. The goal of this more careful assignment is to achieve the following property: if we denote $E_i=\set{e_1,\ldots,e_{h_i}}$, where the edges are indexed according to the ordering $\oset(C_i)$, and, for each such edge $e_j$, we denote by $e'_j$ be the last edge on path $\hat Q(e_j)$ (that we are trying to construct), then the images of the edges $\set{e'_1,\ldots,e'_{h_i}}$ enter the image of $u_i$ in the drawing $\psi$ of graph $H$ in this circular order. We now describe the procedure for assigning copies of edges of $\delta_G(u_i)$ to paths in $\qset_i$.

We start by revisiting the definition of the  ordering $\oset(C_i)$ of the edges of $E_i=\delta_G(C_i)$, which is an ordering that is guided by the set $\qset_i$ of paths and the rotation system $\Sigma$.
Denote $\delta_G(u_i)=\set{a^i_1,\ldots,a^i_{z_i}}$, where the edges are indexed according to their circular ordering $\oset_{u_i}\in \Sigma$. We assume w.l.o.g. that the orientation of this ordering in the drawing $\phi^*$ of $G$ is negative (or clock-wise). For all $1\leq j\leq z_i$, let $\qset^j_i\subseteq \qset_i$ the set of paths in $\qset_i$ whose last edge is $a^i_j$. We defined an ordering $\hat \oset_i$ of the paths in $\qset_i$, where the paths in sets $\qset_i^1,\ldots,\qset_i^{z_i}$ appear in the natural order of their indices, and for all $1\leq j\leq z_i$, the ordering of the paths in set $\qset_i^j$ is arbitrary. We denote $\qset_i^j=\set{Q(e_1^{i,j}),Q(e_2^{i,j}),\ldots,Q(e_{m_{i,j}}^{i,j})}$, and assume that these paths are indexed according to the ordering that we have chosen when defining $\hat \oset_i$.

Ordering $\hat\oset_i$ of the paths in $\qset_i$ was then used to define the ordering $\oset(C_i)$ of the edges in $E_i$: we obtain the ordering $\oset(C_i)$ from $\hat \oset_i$ by replacing, for every path $Q(e_{\ell}^{i,j})\in \qset_i$, the path $Q(e_{\ell}^{i,j})$ in $\hat \oset$ with the edge $e_{\ell}^{i,j}$ (the first edge of $Q(e_{\ell}^{i,j})$).

Consider now some edge $a^i_j\in \delta_G(u_i)$. Recall that we have defined a set $J(a^i_j)$ of  $n_{a^i_j}= m_{i,j}$ copies of the edge $a^i_j$. We denote these copies by $\hat a^{i,j}_1,\ldots,\hat a^{i,j}_{m_{i,j}}$, where the copies are indexed according to the order in which their images enter the image of vertex $u_i$ in the drawing $\psi$ of $H$, in the clock-wise direction. For all $1\leq \ell\leq m_{i,j}$, we assign the copy $\hat a^{i,j}_{\ell}$ of edge $a^i_j$ to the path $Q(e_{\ell}^{i,j})$.
This completes the assignment of the copies of the edges incident to vertex $u_i$ to the paths of $\qset_i$.

We now define  a set $\hat \qset_i=\set{\hat Q(e)\mid e\in E_i}$ of paths in graph $H$, routing the edges of $E_i$ to vertex $u_i$, as follows. For every edge $e\in E_i$, path $\hat Q(e)$ is obtained from the path $Q(e)\in \qset_i$ by replacing every edge $e'\in E(Q(e))\setminus \set{e}$ with the copy of $e'$ that was assigned to path $Q(e)$. The following observation summarizes the properties of the path set $\hat \qset_i$, that follow immediately from our construction.

Paths in set $\hat \qset_i=\set{\hat Q(e)\mid e\in E_i}$  route the edges of $E_i$ to vertex $u_i$ in graph $H$, and all inner vertices on all paths in $\hat \qset_i$ lie in $V(C_i)$. Moreover, the paths of $\hat \qset_i$ are edge-disjoint. Additionally, if $C_i\in \wset^{\light}$, then the following holds. Denote $E_i=\set{e_1,\ldots,e_{h_i}}$, where the edges are indexed according to the ordering $\oset(C_i)$. For each such edge $e_j$, let $e'_j$ be the last edge on path $\hat Q(e_j)$. Then the images of the edges $e'_1,\ldots,e'_{h_i}$ enter the image of $u_i$ in the drawing $\psi$ of graph $H$ in the circular order of their indices.

§.§.§ Step 2: Initial Drawing of Graph $G_C$

In this step we exploit the drawing $\psi$ of graph $H$ that we have constructed in the first step, in order to construct an initial drawing $\phi'$ of graph $G_C$.

In order to construct the drawing $\phi'$ of graph $G_C$, we start with the drawing $\psi$ of graph $H$, and then gradually modify it. We  place the image of the vertex $v^*$ in $\phi'$ at point $\psi(u_0)$, and, for all $1\leq i\leq r$, we place the image of the vertex $v_{C_i}$ at point $\psi(u_i)$. Intuitively, the images of the vertices and the edges of $R$ will remain unchanged. For all $0\leq i\leq r$, we will utilize the images of the paths of $\hat\qset_i$ in $\psi$ in order to draw the edges of $E_i$. There are two issues with this approach. First, we did not bound the expected number of type-2 crossings in $\psi$, so there may be many crossings between pairs of edges lying on paths of $\qset_i$, where $i=0$, or $C_i\in \wset^{\bad}$. We take care of this issue by performing a type-2 uncrossing for each such path set $\hat \qset_i$, to obtain the drawings of the edges in $E_i$. The second problem then remains for indices $i$ with $C_i\in \wset^{\gd}$. Since several paths from $\hat \qset_i$ may share the same vertex, there could be points that lie on images of multiple paths of $\hat \qset_i$. We take care of this latter issue by employing a nudging procedure. We now describe each of these two operations in turn.

We consider indices $i$ for which either $i=0$ or $C_i\in \wset^{\bad}$ holds one by one. Consider any such index $i$. We view every path of $\hat \qset_i$ as being directed towards the vertex $u_i$. We use the algorithm from <Ref> in order to compute a type-2 uncrossing, that produces, for every edge $e\in E_i$, a directed curve $\gamma(e)$, that connects the image of the endpoint of $e$ that lies in $R$ to the image of $u_i$ in $\psi$. Recall that we are guaranteed that the curves in the resulting set $\Gamma_i=\set{\gamma(e)\mid e\in E_i}$ do not cross each other, and each such curve is aligned with the drawing of graph $\bigcup_{\hat Q(e)\in \hat \qset_i}\hat Q(e)$ induced by $\psi$.

Let $\psi'$ be a drawing obtained from $\psi$ as follows. For every index $i$ with $i=0$ or  $C_i\in \wset^{\bad}$, we delete the images of all vertices of $V(C_i)$ and all edges with at least one endpoint in $V(C_i)$ from the drawing. If $i=0$, then we place the image of vertex $v^*$ at point $\psi(u_0)$, and otherwise we place the image of vertex $v_{C_i}$ at point $\psi(u_i)$. For every edge $e\in E_i$, we then let $\gamma(e)\in \Gamma_i$ be the image of the edge $e$.

Note that this uncrossing step has eliminated all type-2 crossings, and every crossing in the resulting drawing $\psi'$ corresponds to a distinct type-1 or type-3 crossing of $\psi$. Therefore, the expected number of crossings of $\psi'$ is bounded by $O(\beta^2\cdot |\chi(C)|)$.
We call all crossings that are currently present in drawing $\psi'$ primary crossings.

We now consider the indices $i$ with $C_i\in \wset^{\gd}$ one by one. When  such an index $i$ is considered, we delete the images of all vertices of $V(C_i)$ and all edges with at least one endpoint in $V(C_i)$ from the current drawing $\psi'$. We then place the image of vertex $v_{C_i}$ at point $\psi(u_i)$. For every edge $e\in E_i$, we initially let $\gamma(e)$ be the image of the path $\hat Q(e)\in \hat \qset_i$ in $\psi$, and we add $\gamma(e)$ to the current drawing as the image of the edge $e$. Note that the curves in $\set{\gamma(e)\mid e\in E_i}$ enter the image of $v_{C_i}$ in the order $\oset(C_i)$ of their corresponding edges in $E_i$,  from <Ref>. However, it is possible that, for some vertex $x\in V(C_i)$, point $\psi(x)$ lies on more than two curves from
$\set{\gamma(e)\mid e\in E_i}$.

We process each vertex $x\in V(C_i)\setminus \set{u_i}$ one by one. Consider any such vertex $x$, and let $\qset^x\subseteq \hat\qset_i$ be the set of all paths containing vertex $x$. Note that $x$ must be an inner vertex on each such path. For convenience, we denote $\qset^x=\set{Q(e_1),\ldots,Q(e_z)}$. Consider the tiny $x$-disc $D=D_{\psi}(x)$. For all $1\leq j\leq z$, denote by $s_j$ and $t_j$ the two points on the curve $\gamma(e_j)$ that lie on the boundary of disc $D$. We use the algorithm from <Ref> to compute a collection $\set{\sigma_1,\ldots,\sigma_z}$ of curves, such that, for all $1\leq j\leq z$, curve $\sigma_j$ connects $s_j$ to $t_j$, and the interior of the curve is contained in the interior of $D$. Recall that every pair of resulting curves crosses at most once, and every point in the interior of $D$ may be contained in at most two curves.
Consider now a pair $\sigma_{\ell},\sigma_{\ell'}$ of curves, and assume that these two curves cross. Recall that, from <Ref>, this may only happen if the two pairs $(s_{\ell},t_{\ell})$, $(s_{\ell'},t_{\ell'})$ of points cross. Denote by $e_1,e_2$ the two edges that lie on path $\hat Q(e_{\ell})$ immediately before and immediately after vertex $x$, and denote by $e_1',e_2'$ the two edges that lie on path $\hat Q(e_{\ell'})$ immediately before and immediately after vertex $x$. We assume that edges $e_1,e_2$ are copies of edges $\hat e_1,\hat e_2$ of $G$, and similarly, $e_1',e_2'$ are copies of edges $\hat e_1',\hat e_2'$ of $G$, respectively. Assume first that there are four distinct edges in set $\set{\hat e_1,\hat e_1',\hat e_2,\hat e_2'}$. From the fact that the two pairs  $(s_{\ell},t_{\ell})$, $(s_{\ell'},t_{\ell'})$ of points cross, we get that these four edges must appear in the rotation $\oset_x\in \Sigma$ in the order $(\hat e_1,\hat e_1',\hat e_2,\hat e_2')$. Since the paths of $\qset_i$ are non-transversal with respect to $\Sigma$, this is impossible. Therefore, we conclude that paths $Q(e_{\ell}),Q(e_{\ell'})$ must share an edge that is incident to $x$. If $e^*$ is an edge incident to $x$ that the two paths share, then we say that $e^*$ is responsible for the crossing between $\sigma_{\ell}$ and $\sigma_{\ell'}$.

For all $1\leq j\leq z$, we modify the curve $\gamma(e_j)$, by replacing the segment of the curve that is contained in disc $D$ with $\sigma_j$.
Once every vertex $x\in V(C_i)\setminus \set{u_i}$ is processed, we obtain the final set $\Gamma'_i=\set{\gamma'(e)\mid e\in E_i}$ of curves, which are now guaranteed to be in general position. For every edge $e\in E_i$, we modify the image of edge $e$ in the current drawing, by replacing it with the new curve $\gamma'(e)$. As before, curves of $\Gamma'_i$ enter the image of $v_{C_i}$ according to the ordering $\oset(C_i)$.

Once every index $i$ with $C_i\in \wset^{\gd}$ is processed, we obtain a valid drawing $\phi'$ of the graph $G_C$. In this drawing, for every index $i$ with $C_i\in \wset^{\gd}$, the images of the edges in set $E_i=\delta_{G_C}(v_{C_i})$ enter the image of vertex $v_{C_i}$ according to the ordering $\oset_{v_{C_i}}\in \Sigma_C$, which is precisely $\oset(C_i)$. However, for indices $i$ with $C_i\in \wset^{\bad}$, this property may not hold, and the edges incident to $v^*$ may enter the image of $v^*$ in an arbitrary order. For every other vertex $v$ of $G_C$, the rotation $\oset_v\in \Sigma_{C}$ is identical to the rotation $\oset_v\in \Sigma$, and is obeyed by the current drawing $\phi'$. We modify the drawing $\phi'$ to obtain a drawing that is consistent with the rotation system $\Sigma_{C}$ in the third step. Notice however that the nudging operation may have introduced some new crossings. Each such new crossing must be contained in a disc $D_{\psi}(x)$, for some vertex $x$ that must lie in some cluster $C_i\in \wset^{\gd}$. We call all such new crossings secondary crossings. We now bound the total number of secondary crossings.

Fix an index $i$ with $C_i\in \wset^{\gd}$, and consider some vertex $x\in V(C_i)$. Every secondary crossing that is contained in $\dset_{\psi}(x)$ is a crossing between a pair $\sigma_{\ell},\sigma_{\ell'}$ of curves that we have defined when processing vertex $x$, and each such crossing was charged to an edge of $G$ that is incident to $x$, whose copies lie on the corresponding two paths $\hat Q(e_{\ell}),\hat Q(e_{\ell'})\in \hat \qset_i$. If $e$ is an edge that is incident to $x$ in $G$, then there are at most $(\cong_G(\qset_i,e))^2$ pairs of paths in $\qset_i$ that contain $e$, and each such pair of paths may give rise to a single secondary crossing in $D_{\psi}(x)$ that is charged to edge $e$. Therefore, the total expected number of secondary crossings that are contained in discs $D_{\psi}(x)$ for vertices $x\in V(C_i)$ is bounded by:

\[ \sum_{e\in E(C_i)}O(\expect{(\cong_G(\qset_i,e))^2})\leq O(\beta \cdot |E(C_i)|),  \]

since $C_i\in \wset^{\gd}$.

We conclude that the total expected number of secondary crossings in $\phi'$ is at most $\sum_{C_i\in\wset^{\gd}}O(\beta \cdot |E(C_i)|)\leq O(\beta\cdot |E(C)|)$, and the total number of all crossings in $\phi'$ is at most  $O(\beta^2\cdot (|\chi(C)|+|E(C)|))$.

§.§.§ Step 3: the Final Drawing

So far we have obtained a drawing $\phi'$ of graph $G_C$, that obeys the rotations $\oset_v\in \Sigma_C$ for all vertices $v\in V(G_C)$, except possibly for vertex $v^*$, and vertices $v_{C_i}$, for $C_i\in \wset^{\bad}$. We now fix this drawing to obtain a final drawing $\phi''$ of $G_C$ that obeys the rotation system $\Sigma_C$.

Let $U=\set{v^*}\cup \set{v_{C_i}\mid C_i\in \wset^{\bad}}$. For each vertex $x\in U$, we denote by $\hat \oset(x)=\oset_x\in \Sigma_C$ the rotation associated with vertex $x$ in the rotation system $\Sigma_C$, and by $\hat \oset'(x)$ the circular order in which the edges of $\delta_{G_C}(x)$ enter the image of $x$ in the current drawing $\phi'$. Note that, for a vertex $x=v_{C_i}$, where $C_i\in \wset^{\bad}$, if we denote by $\Sigma(C_i)$ the rotation system induced by $\Sigma$ for cluster $C$, then the following must hold:

\[\dist(\hat \oset(x),\hat \oset'(x))\leq |\delta_{G_C}(x)|^2=|\delta_G(C_i)|^2\leq \beta\cdot (\optcrors(C_i,\Sigma(C_i))+|E(C_i)|)\leq \beta(|\chi(C_i)|+|E(C_i)|).\]

(we have used the fact that cluster $C_i$ is a $\beta$-bad cluster).
We use the following claim, whose proof appears in Section <ref>, in order to bound $\dist(\hat \oset(v^*),\hat \oset'(v^*))$.

$\expect{\dist(\hat \oset(v^*),\hat \oset'(v^*))}\leq \beta^2\cdot (|\chi(C)|+|E(C)|)$.

In order to compute the final drawing $\phi''$ of graph $G_C$, we process the vertices $x\in U$ one by one. When vertex $x$ is processed, we apply the algorithm from <Ref> to it. The algorithm modifies the current drawing of graph $G_C$ within the tiny $x$-disc $D(x)$ to ensure that the images of the edges of $\delta_{G_C}(x)$ enter the image of $x$ in the circular order $\hat \oset(x)$. This modification increases the number of crossings in the current drawing by at most $2\cdot\dist(\hat \oset(x),\hat \oset'(x))$. Once every vertex of $U$ is processed, we obtain the final drawing $\phi''$ of graph $G_C$, which obeys the rotation system $\Sigma_C$. Moreover, $\cro(\phi'')\leq \cro(\phi')+\sum_{x\in U}2\cdot\dist(\hat \oset(x),\hat \oset'(x))$. Recall that $\expect{\cro(\phi')}\leq O(\beta^2)\cdot (|\chi(C)|+|E(C)|)$, and that, for every vertex $x=v_{C_i}$ with $C_i\in \wset^{\bad}$, $\dist(\hat \oset(x),\hat \oset'(x))\leq \beta(|\chi(C_i)|+|E(C_i)|)$. Combining this with <Ref>, we get that:

\[\expect{\cro(\phi'')}\leq O(\beta^2)\cdot (|\chi(C)|+|E(C)|)+\sum_{C_i\in \wset^{\bad}}  O(\beta)\cdot (|\chi(C_i)|+|E(C_i)|)\leq O(\beta^2\cdot (|\chi(C)|+|E(C)|)). \]

This completes the proof of <Ref>.

§.§ Proof of <Ref>

Clearly, $\dist(\hat \oset(v^*),\hat \oset'(v^*))\leq |\delta_{G_C}(v^*)|^2=|\delta_G(C)|^2$. If $C\in \lset^{\bad}$, then cluster $C$ is $\beta$-bad, and so $\dist(\hat \oset(v^*),\hat \oset'(v^*))\leq |\delta_G(C)|^2\leq \beta\cdot (|\chi(C)|+|E(C)|)$ from the definition of $\beta$-bad clusters. Therefore, we assume from now on that $C\in \lset^{\gd}$.

For convenience of notation, we denote $v^*$ by $u'$, and we denote $\hat \oset(v^*)$ and $\hat \oset'(v^*)$ by $\oset$ and $\oset'$, respectively. We also denote $E'=\delta_G(C)=\delta_{G_C}(u')$.
In order to prove the claim, we will construct a collection $\Gamma=\set{\gamma(e)\mid e\in E'}$ of curves in the plane, all of which connect two points $p$ and $q$. We will ensure that the order in which the curves enter the point $p$ is precisely $\oset'$, and the order in which they enter the point $q$ is $\oset$. We will also ensure that the curves of $\Gamma$ are in general position. By showing that the expected number of crossings between the curves in $\Gamma$ is relatively small, we will obtain the desired bound on $\expect{\dist(\oset,\oset')}$.

In order to construct the curves in $\Gamma$, we consider again the intance $I$ of and its optimal solution $\phi^*$. Recall that we have computed an internal $C$-router $\qset=\set{Q(e)\mid e\in E'}$, where for each edge $e\in E'$, path $Q(e)$ originates with edge $e$, terminates at vertex $u$, and all its inner vertices lie in $C$. The paths in $\qset$ are non-transversal with respect to $\Sigma$, and, for every edge $e'\in E(C)$, $\expect{(\cong_G(\qset,e'))^2}\leq \beta$. We have also constructed an  external $C$-router $\qset'=\set{Q'(e)\mid e\in E'}$, where for each edge $e\in E'$, path $Q(e)$ originates with edge $e$, terminates at vertex $u'$, and all its inner vertices are disjoint from $C$. The paths in $\qset'$ are non-transversal with respect to $\Sigma$, and, for every edge $e'\in E(G\setminus C)$, $\expect{\cong_G(\qset',e')}\leq \beta$. We note that path set $\qset'$ is exactly the same as path set $\qset_0$ – the internal router for $C_0$, that we used in the first step of the algorithm. Intuitively, we would like to let $p$ be the image of vertex $u'$ and $q$ the image of vertex $u$ in $\phi^*$. For every edge $e\in E'$, we would like to use the concatenation of the images of paths $Q(e)$ and $Q'(e)$ in $\phi^*$ in order to construct the curve $\gamma(e)$. This approach has several problems. First, the paths in sets $\qset$ and $\qset'$ may share edges and vertices, and so the resulting curves may not be in a general position. Second, there could be many crossings between edges lying on the paths of $\qset'$, which may lead to many crossings between curves of $\Gamma$. We take care of all these issues in the following three steps. In the first step, we take care of the congestion issue by constructing a graph $H'$ and its drawing $\psi'$. The construction is somewhat similar to the construction of graph $H$, in that we make several copies of some of the edges of $G$, in a way that allows us to define edge-disjoint paths in graph $H'$ replacing the path sets $\qset$ and $\qset'$. In the second step, we perform uncrossing of curves corresponding to the paths in $\qset'$, in order to eliminate some of the crossings. In the third step we perform nudging of curves corresponding to the paths in $\qset$. We now describe each of these steps in turn.

Graph $H'$.
For each edge $e\in E'$, we set $n'_e=1$. For an edge $e\in E(C)$, we set $n'_e=\cong_G(\qset,e)$, and for an edge $e\in E(G\setminus C)$, we set $n'_e=\cong_G(\qset',e)$. For every other edge $e$, we set $n'_e=0$. Note that for each edge $e\in E(G\setminus C)$, $n'_e=n_e$ holds, where $n_e$ is the parameter that we have used in the construction of graph $H$ in Step 1 of the algorithm.

In order to construct graph $H'$, we start with $V(H')=V(G)$. For every edge $e=(x,y)\in E(G)$ with $n'_e\neq 0$, we add a new set $J'(e)$ of $n'_e$ parallel edges connecting $x$ to $y$ to graph $H'$, that we view as copies of edge $e$.  As before, we use the drawing $\phi^*$ of $G$ in order to compute a drawing $\psi'$ of graph $H'$. For every vertex $x\in V(H')$, we let its image in $\psi'$ be $\phi^*(x)$. For every edge $e\in E(G)$ with $n'_e\neq 0$, we draw the edges of $J'(e)$ in parallel to the image of $e$ in $\phi^*$. Recall that for each edge $e\in E(G\setminus C)$, $n'_e=n_e$ holds, and so set $J'(e)$ of copies of $e$ can be thought of as being identical to the set $J(e)$ of copies of $e$ that we have constructed for graph $H$. We ensure that the specific drawing of the edges of $J'(e)$ in $\psi'$ is identical to the drawing of these edges in $\psi$.

We now bound the expected number of crossings in the resulting drawing $\psi'$ of graph $H'$. Consider any such crossing $(e_1',e_2')_{p'}$, and assume that $e_1'\in J'(e_1)$, $e_2'\in J'(e_2)$ holds for some edges $e_1,e_2\in E(G)$. Then there must be some crossing $(e_1,e_2)_p$ in the drawing $\phi^*$ of $G$, with point $p$ lying very close to point $p'$. We say that crossing $(e_1,e_2)_p$ of $\phi^*$ is responsible for the crossing $(e_1',e_2')_{p'}$ of $\psi'$. It is immediate to verify that every crossing $(e_1,e_2)_p$ of $\phi^*$ may be responsible for at most $n'_{e_1}\cdot n'_{e_2}$ crossings of $\psi'$.

We classify the crossings of $\psi'$ into three types. Let $(e_1',e_2')_{p'}$ be a crossing of $\psi'$, and let  $(e_1,e_2)_p$ be the crossing of $\phi^*$ responsible for it. We say that $(e_1',e_2')_{p'}$ is a type-1 crossing if $e_1,e_2\in E(C)$. We say that it is a type-2 crossing if $e_1,e_2\in E(G)\setminus(E(C)\cup \delta_G(C))$. Otherwise, we say that it is a type-3 crossing. We now bound the expected number of type-1 and type-3 crossings; type-2 crossings will eventually be eliminated.

In order to bound the expected number of type-1 crossings, consider any crossing $(e_1,e_2)_p$ of $\phi^*$  with $e_1,e_2\in E(C)$. Recall that this crossing may be responsible for at most $n'_{e_1}\cdot n'_{e_2}\leq (n'_{e_1})^2+(n'_{e_2})^2$ type-1 crossings of $\psi'$, and moreover, $(e_1,e_2)_p\in \chi(C)$ must hold. Since we have assumed that $C\in \lset^{\gd}$, for every edge $e\in E(C)$, $\expect{(n'_e)^2}=\expect{(\cong_G(\qset,e))^2} \leq \beta$. Therefore, the expected number of type-1 crossings of $\psi'$ for which $(e_1,e_2)_p$ is responsible for is at most $\expect{(n'_{e_1})^2+(n'_{e_1})^2}\leq 2\beta$.
Overall, the total expected number of type-1 crossings in $\psi'$ is then bounded by $O(\beta\cdot |\chi(C)|)$.

In order to bound the expected number of type-3 crossings, consider any crossing $(e_1,e_2)_p$ of $\phi^*$, and assume that neither  $e_1,e_2\in E(C)$ nor $e_1,e_2\in E(G)\setminus (E(C)\cup \delta_G(C))$ holds. Recall that this crossing may be repsonsible for at most $n'_{e_1}\cdot n'_{e_2}$ type-3 crossings of $\psi'$. Moreover, $n'_{e_1},n'_{e_2}$ are independent random variables, and the expected value of each such variable is at most $\beta$. Therefore, the expected number of type-3 crossings of $\psi'$ for which crossing $(e_1,e_2)_p$ of $\phi^*$ is responsible for is at most $\beta^2$.
Notice that one of the edges $e_1,e_2$ lies in $E(C)\cup \delta_G(C)$, and so
$(e_1,e_2)_p\in \chi(C)$ must hold. Overall, the total expected number of type-3 crossings in $\psi'$ is then bounded by $O(\beta^2\cdot |\chi(C)|)$.

We conclude that the total expected number of type-1 and type-3 crossings in $\psi'$ is at most $O(\beta^2\cdot |\chi(C)|)$.

Next, we construct a set $\hat \qset'=\set{\hat Q'(e)\mid e\in E'}$ of edge-disjoint paths in graph $H'$, routing the edges of $E'$ to vertex $u'$. In order to do so, we assign, for every path $Q'(e)\in \qset'$, for every edge $e'\in E(Q'(e))\setminus\set{e}$, a copy of edge $e'$ to path $Q'(e)$. Observe that path set $\qset'$ in graph $G$ was denoted by $\qset_0$ in Step 1 of the algorithm, and, as observed before, for every edge $e'\in E(G)\setminus (E(C)\cup \delta_G(C))$, $n_{e'}=n'_{e'}$ and so $J(e')=J'(e')$. For each such edge $e'\in E(G)\setminus (E(C)\cup \delta_G(C))$, we assign a distinct copy of $e'\in J'(e')$ to every path in $\qset'$ that contains $e'$. We ensure that this assignment is exactly the same as the assignment done in Step 1 of the algorithm. For each edge $e\in E'$, we then obtain a path $\hat Q'(e)$ in graph $H'$ from path $Q'(e)$ by replacing each edge $e'\in E(Q'(e))\setminus\set{e}$ with the copy of $e'$ that was assigned to $e'$. We then denote $\hat \qset'=\set{\hat Q'(e)\mid e\in E'}$. From our construction, $\hat \qset'$ is a set of edge-disjoint paths in graph $H'$, routing the edges of $E'$ to vertex $u'$, and all inner vertices on the paths in $\hat \qset'$ are disjoint from $C$. Moreover, from our construction, $\hat \qset'=\hat \qset_0$ – the set of edge-disjoint paths in $H$ that we have constructed in Step 1 of the algorithm.

We also construct a set $\hat \qset=\set{\hat Q(e)\mid e\in E'}$ of edge-disjoint paths in graph $H'$, routing the edges of $E'$ to vertex $u$. In order to do so, we assign, for every path $Q(e)\in \qset$, for every edge $e'\in E(Q(e))\setminus\set{e}$, a copy of edge $e'$ to path $Q(e)$.
Consider now any edge $e'\in E(C)$. If edge $e'$ is not incident to vertex $u$, then we assign every copy of $e$ in $J'(e')$ to a distinct path of $\qset$ containing $e'$ arbitrarily. If edge $e'$ is incident to vertex $u$, then we perform the assignment more carefully, using the same procedure that we used for every cluster $C_i\in \wset^{\gd}$ in order to assign, for each edge $e'$ incident to $u_i$, copies of $e'$ to paths in $\qset_i$; we do not repeat the description of the procedure there. For each edge $e\in E'$, we  obtain a path $\hat Q(e)$ in graph $H'$ from path $Q(e)$ by replacing each edge $e'\in E(Q(e))\setminus\set{e}$ with the copy of $e'$ that was assigned to $e'$. We then denote $\hat \qset=\set{\hat Q(e)\mid e\in E'}$.
Recall that $\oset=\oset(C)$ is a circular ordering of the edges of $E'=\delta_G(C)$ that is guided by the set $\qset$ of paths and the rotation system $\Sigma$. As in Step 1 of the algorithm, our assignment of edges incident to vertex $u$ ensures the following crucial property. Denote $E'=\set{e_1,\ldots,e_k}$, where the edges are indexed according to the ordering $\oset$. For each such edge $e_j$, let $e'_j$ be the last edge on path $\hat Q(e_j)$. Then the images of edges $e'_1,\ldots,e'_k$ enter the image of the vertex $u$ in the drawing $\psi'$ of $H'$ in the order of their indices.

We view every path of $\hat \qset'$ as being directed towards the vertex $u'$. We use the algorithm from <Ref> in order to compute a type-2 uncrossing, that produces, for every edge $e_j\in E'$, a directed curve $\hat \gamma'(e_j)$, that connects the image of the endpoint of $e_j$ lying in $C$ to $u'$. Recall that we are guaranteed that the curves in the resulting set $\hat \Gamma'=\set{\hat \gamma'(e_j)\mid e_j\in E'}$ do not cross each other, and each such curve is aligned with the drawing of graph $\bigcup_{\hat Q'(e_{\ell})\in \hat \qset'}\hat Q'(e_{\ell})$ induced by $\psi'$ (which is identical to the drawing induced by $\psi$).
Notice that the steps that we have followed in constructing the set $\hat \Gamma'$ of curves are identical to those we followed in order to construct the set $\Gamma_0$ of curves, and so the resulting two sets of curves are identical. In particular, the order in which the curves of $\hat \Gamma$ enter the image of vertex $u'$ in $\psi'$ is exactly $\oset'$.

We now construct another set of curves, $\hat \Gamma=\set{\hat \gamma(e_j)\mid e_j\in E'}$, by letting, for each edge $e_j\in E'$, $\hat \gamma(e_j)$ be the image of the path $\hat Q(e_j)\in \hat \qset$ in the drawing $\psi'$ of $H'$. From our construction of the set $\hat \qset$ of paths, the order in which the curves of $\hat \Gamma$ enter the image of vertex $u$ in $\psi$ is exactly $\oset$. For every edge $e_j\in E'$, we then let $\gamma(e_j)$ be a curve, connecting the images of $u$ and $u'$ in $\psi'$, obtained by combining the curves $\hat \gamma(e_j)$ and $\hat \gamma'(e_j)$. In order to combine the two curves, let $y_j$ be the endpoint of $e_j$ lying in $C$, and let $p_j$ be the unique point on $\psi'(e_j)$ that lies on the boundary of the tiny $y_j$-disc $D_{\psi'}(y_j)$. We truncate curve $\hat\gamma'(e_j)$ so it connects point $p_j$ to the image of vertex $u'$, and we truncate the curve $\hat \gamma(e_j)$, so it connects point $p_j$ to the image of vertex $u$. We then concatenate the resulting two curves to obtain the curve $\gamma(e_j)$.

Consider the resulting set $\Gamma=\set{\gamma(e_j)\mid e_j\in E'}$ of curves. From the above discussion, the curves enter the image of $u'$ in $\psi'$ according to the ordering $\oset'$, and they enter the image of $u$ according to the ordering $\oset$. The total number of crossings between the curves in $\Gamma$ is bounded by $\cro(\psi')$. We call all such crossings primary crossings. Recall that the expected number of primary crossings is at most $O(\beta^2\cdot |\chi(C)|)$. However, the curves in $\Gamma$ may not be in  general position. This is since some vertices $x\in V(C)$ may lie on a number of paths in $\hat \qset$. In the next step we perform “nudging” around such vertices, to ensure that the resulting curves are in general position.

The nudging procedure and its analysis are identical to those from Step 2 of the algorithm. We only need to perform nudging of the curves in $\Gamma$ around vertices $x\in V(C)\setminus\set{u}$.

We process each vertex $x\in V(C)\setminus \set{u}$ one by one. Consider any such vertex $x$, and let $\qset^x\subseteq \hat\qset$ be the set of all paths containing vertex $x$. Note that $x$ must be an inner vertex on each such path. For convenience, we denote $\qset^x=\set{\hat Q(e_1),\ldots,\hat Q(e_z)}$. Consider the tiny $x$-disc $D=D_{\psi'}(x)$. For all $1\leq j\leq z$, denote by $s_j$ and $t_j$ the two points on the curve $\gamma(e_j)$ that lie on the boundary of disc $D$. We use the algorithm from <Ref> to compute a collection $\set{\sigma_1,\ldots,\sigma_z}$ of curves, such that, for all $1\leq j\leq z$, curve $\sigma_j$ connects $s_j$ to $t_j$, and the interior of the curve is contained in the interior of $D$. Recall that every pair of resulting curves crosses at most once, and every point in the interior of $D$ may be contained in at most two curves.
Consider now a pair $\sigma_{\ell},\sigma_{\ell'}$ of curves, and assume that these two curves cross. Recall that, from <Ref>, this may only happen if the two pairs $(s_{\ell},t_{\ell})$, $(s_{\ell'},t_{\ell'})$ of points cross. Denote by $e_1,e_2$ the two edges that lie on path $\hat Q(e_{\ell})$ immediately before and immediately after vertex $x$, and denote by $e_1',e_2'$ the two edges that lie on path $\hat Q(e_{\ell'})$ immediately before and immediately after vertex $x$. We assume that edges $e_1,e_2$ are copies of edges $\hat e_1,\hat e_2$ of $G$, and similarly, $e_1',e_2'$ are copies of edges $\hat e_1',\hat e_2'$ of $G$, respectively. Assume first that there are four distinct edges in set $\set{\hat e_1,\hat e_1',\hat e_2,\hat e_2'}$. From the fact that the two pairs  $(s_{\ell},t_{\ell})$, $(s_{\ell'},t_{\ell'})$ of points cross, we get that these four edges must appear in $\oset_x\in \Sigma$ in the order $(\hat e_1,\hat e_1',\hat e_2,\hat e_2')$. Since the paths of $\qset$ are non-transversal with respect to $\Sigma$, this is impossible. Therefore, we conclude that paths $Q(e_{\ell}),Q(e_{\ell'})$ must share an edge that is incident to $x$. If $e^*$ is an edge incident to $x$ that the two paths share, then we say that $e^*$ is responsible for the crossing between $\sigma_{\ell}$ and $\sigma_{\ell'}$.

For all $1\leq j\leq z$, we modify the curve $\gamma(e_j)$, by replacing the segment of the curve that is contained in disc $D$ with $\sigma_j$.
Once every vertex $x\in V(C)\setminus \set{u}$ is processed, we obtain the final set $\Gamma^*=\set{\gamma^*(e)\mid e\in E'}$ of curves, which are now guaranteed to be in general position. Notice that as before, the curves in $\Gamma^*$ enter the image of $u'$ according to the ordering $\oset'$, and they enter the image of $u$ according to the ordering $\oset$. It now only remains to bound the expected number of crossings between the curves of $\Gamma^*$.

Notice that the nudging operation may have introduced some new crossings. Each such new crossing must be contained in a disc $D_{\psi'}(x)$, for some vertex $x\in V(C)\setminus\set{u}$. We call all such new crossings secondary crossings. We now bound the expected number of secondary crossings.

Consider some vertex $x\in V(C)\setminus\set{u}$. Every secondary crossing that is contained in $\dset_{\psi'}(x)$ is a crossing between a pair $\sigma_{\ell},\sigma_{\ell'}$ of curves that we have defined when processing vertex $x$, and each such crossing was charged to an edge of $G$ that is incident to $x$. If $e$ is an edge of $G$ that is incident to $x$, then there are at most $(\cong_G(\qset,e))^2$ pairs of paths in $\qset^x$ that contain copies of $e$, and each such pair of paths may give rise to a single secondary crossing in $D_{\psi'}(x)$ that is charged to edge $e$. Therefore, the total expected number of secondary crossings is bounded by:

\[ \sum_{e\in E(C)}O(\expect{(\cong_G(\qset,e))^2})\leq O(\beta \cdot|E(C)|),\]

since we have assumed that $C\in \wset^{\gd}$.

Overall, the expected number of crossings between the curves in $\Gamma^*$ is at most  $O(\beta^2\cdot (|\chi(C)|+|E(C)|))$, proving that $\expect{\dist(\oset,\oset')}\leq  O(\beta^2\cdot (|\chi(C)|+|E(C)|))$.

§ PROOFS OMITTED FROM <REF>

§.§ Proof of <Ref>

Note that, since graph $G$ is connected, $|V(G)|\leq m+1\leq 2m$ must hold.
Throughout, we use a parameter $\eta'=c\eta\log_{3/2}m\log_2m$, were $c$ is a large enough constant, whose value we set later.

The algorithm maintains a collection $\cset$ of disjoint clusters of $G\setminus T$, such that $\bigcup_{C\in \cset}V(C)=V(G)\setminus T$. Set $\cset$ of clusters is partitioned into two subsets: set $\cset^A$ of active clusters and set $\cset^I$ of inactive clusters. We will ensure that every cluster $C\in \cset^I$ has the $\alpha'$-bandwidth property. Set $\cset^I$ of inactive clusters is, in turn, partitioned into three subsets, $\cset_1^I,\cset_2^I$, and $\cset_3^I$. For every cluster $C\in \cset_3^I$, we will define  a vertex $u(C)\in V(C)$, and an internal $C$-router $\qset(C)$, whose center vertex is $u(C)$, such that the paths in $\qset(C)$ are edge-disjoint. For every cluster
$C\in \cset^I_1$, we will ensure that $|E(C)|\leq O(\eta^4\log^8m)\cdot |\delta_G(C)|$ holds.
Lastly, for every cluster $C\in \cset^I_2$, we will ensure that
$\optcro(C)\geq \Omega(|E(C)|^2/(\eta^2\poly\log m))$, and $|E(C)|> \Omega(\eta^4 |\delta_G(C)|\log^8m)$. We start with $\cset^I=\emptyset$, and $\cset^A$ containing a single cluster $G\setminus T$ (note that graph $G\setminus T$ is connected since $G$ is connected and every terminal has degree $1$). The algorithm terminates once $\cset^A=\emptyset$, and once this happens, we return $\cset^I$ as the algorithm's outcome.

In order to bound the number of edges in the contracted graph $E(G_{|\cset})$, we will use edge budgets and vertex budgets, that are defined as follows.

Edge Budgets.
If an edge $e$ belongs to the boundary $\delta_G(C)$ of a cluster $C\in \cset$, then, if $C\in \cset^I$, we set the budget $B_C(e)=1$, and otherwise we set it to be $B_C(e)=\log_{3/2}(|\delta_G(C)|)$. If cluster $C$ is the unique cluster with $e\in \delta_G(C)$, then we set $B(e)=B_C(e)$. If there are two clusters $C\neq C'\in \cset$ with $e\in \delta_G(C)$ and $e\in \delta_G(C')$, then we set $B(e)=B_C(e)+B_{C'}(e)$. Lastly, if no cluster $C\in \cset$ with $e\in \delta_G(C)$ exists, then we set $B(e)=0$.

Vertex Budgets.
Vertex budgets are defined as follows. For every cluster $C\in \cset^A$, for every vertex $v\in V(C)$, we set the budget $B(v)=\frac{c\deg_C(v)\log_{3/2}m\cdot \log_{2}(|E(C)|)}{8\eta'}$, where $c$ is the constant used in the definition of $\eta'$. The budgets of all other vertices are set to $0$.

Cluster Budgets and Total Budget.
For a cluster $C\in\cset$, we define its edge-budget $B^E(C)=\sum_{e\in \delta_G(C)}B_C(e)$, and its vertex-budget $B^V(C)=\sum_{v\in V(C)}B(v)$. The total budget of a cluster $C\in \cset$ is $B(C)=B^E(C)+B^V(C)$, and the total budget in the system is $B^*=\sum_{C\in \cset}B(C)=\sum_{e\in E(G)}B(e)+\sum_{v\in V(G\setminus T)}B(v)$.

Notice that at the beginning of the algorithm, the budget of every vertex $v\in V(G)\setminus T$ is bounded by:

$$\frac{c\cdot \deg_{G\setminus T}(v)\cdot \log_{3/2}m\cdot \log_2|E(G)|}{8\eta'}\leq \frac{\deg_G(v)}{8\eta},$$

the budget of every edge incident to a vertex in $T$ is at most $\log_{3/2}(|T|)\leq 16\log m$, while the budget of every other edge is $0$. Therefore, the total budget $B^*$ in the system at the beginning of the algorithm is:

\[	\frac{m}{4\eta}+ 16k\log m\leq \frac{m}{\eta},\]

since $k\leq \frac{m}{16\eta\log m}$ from the statement of <Ref>.

We will ensure that, throughout the algorithm, the total budget $B^*$ never increases. Since, from the definition, $B^*\geq \sum_{C\in \cset}|\delta_G(C)|$, this ensures that, when the algorithm terminates,  $|E(G_{|\cset})|\leq m/\eta$, so the set $\cset^I$ of clusters and its partition $(\cset_1^I,\cset_2^I,\cset_3^I)$ is a valid output of the algorithm.

As mentioned above, the algorithm starts with $\cset^I=\emptyset$, and $\cset^A$ contains a single cluster – cluster $G\setminus T$. As long as $\cset^A\neq \emptyset$, we perform iterations, where in each iteration we select an arbitrary cluster $C\in \cset^A$ to process.
We now describe the execution of an iteration in which cluster $C\in \cset^A$ is processed.
The algorithm for processing cluster $C$ consists of three steps, that we describe next.

Step 1: Bandwidth Property.
In this step we will either establish that $C$ has the $\alpha'$-bandwidth property, or we will partition it into smaller clusters that will replace $C$ in set $\cset^A$.
Let $C^+$ be the augmentation of cluster $C$. Recall that $C^+$ is a graph that is obtained as follows. We start with the graph $G$, and we subdivide every edge $e\in \delta_G(C)$ with a vertex $t_e$, letting $T(C)=\set{t_e\mid e\in \delta_G(C)}$ be this new set of vertices. We then let $C^+$ be the subgraph of the resulting graph induced by $V(C)\cup T(C)$. From <Ref>, cluster $C$ has the $\alpha'$-bandwidth property iff the set $T(C)$ of vertices is $\alpha'$-well-linked in $C^+$. We apply the algorithm  to graph $C^+$ and terminal set $T(C)$, to obtain an  $\alphasc(m)=O(\sqrt{\log m})$-approximate sparsest cut $(X,Y)$ in graph $C^+$ with respect to the set $T(C)$ of terminals.

We can assume without loss of generality that, for every vertex $t_e\in T(C)$, if $t_e\in X$, and $e'=(t_e,v)$ is the unique edge that is incident to $t_e$ in $C^+$, then $v\in X$ as well (as otherwise we can move $t_e$ to $Y$, making the cut only sparser). Similarly, if $t_e\in Y$, then $v\in Y$ as well.
We assume w.l.o.g. that $|X\cap T(C)|\leq |Y\cap T(C)|$.
We then consider two cases. First, if $|E(X,Y)|\geq \alpha'\cdot \alphasc(m)\cdot |X\cap T(C)|$, then we are guaranteed that vertex set $T(C)$ is $\alpha'$-well-linked in $C^+$, and therefore cluster $C$ has the $\alpha'$-bandwidth property. Assume now that  $|E(X,Y)|< \alpha'\cdot \alphasc(m)\cdot |X\cap T(C)|$.

Let $X'=X\setminus T(C)$ and $Y'=Y\setminus T(C)$, so $(X',Y')$ is a partition of $C$. Note that $|T(C)\cap X|=|\delta_G(C)\cap \delta_G(X')|$ and similarly $|T(C)\cap Y|=|\delta_G(C)\cap \delta_G(Y')|$.

We remove cluster $C$ from $\cset^A$, and we add all connected components of $C[X']$ and $C[Y']$ to $\cset^A$ instead. Observe that we are still guaranteed that $\bigcup_{C'\in \cset}V(C')=V(G)\setminus T$. We now show that the total budget in the system does not increase as the result of this step.

Since $|X'|,|Y'|<|V(C)|$, it is immediate to verify that, for every vertex $v$ of $C$, its budget may only decrease. The only edges whose budget may increase are the edges of $E_C(X',Y')$. The number of such edges is bounded by $\alpha'\cdot \alphasc(m)\cdot |X\cap T(C)|=\alpha'\cdot \alphasc(m)\cdot |\delta_G(C)\cap \delta_G(X')|$, and the budget of each of them increases by at most $2\log_{3/2}m\leq 8\log m$, so the total increase in the budget of all edges due to this step is bounded by:

\[8\alpha'\cdot \alphasc(m)\cdot |\delta_G(C)\cap \delta_G(X')|\cdot \log m\leq |\delta_G(C)\cap \delta_G(X')|,\]

since $\alpha'=\frac{1}{16\alphasc(m)\cdot \log m}$.

Consider now some edge $e\in \delta_G(C)\cap \delta_G(X')$. Since we have assumed that $|X\cap T(C)|\leq |Y\cap T(C)|$, it is easy to verify that $|\delta_G(X')|\leq 2|\delta_G(C)|/3$. Therefore, if an endpoint of an edge $e\in \delta_G(C)$ belongs to a new cluster $C'\subseteq G[X']$, then the new budget $B_{C'}(e)$ becomes at most:

\[\log_{3/2}(|\delta_G(X')|)\leq \log_{3/2}(|\delta_G(C)|)-1. \]

The total decrease in the global budget due to the edges of
$\delta_G(X')\cap \delta_G(C)$ is then at least $|\delta_G(C)\cap \delta_G(X')|$. We conclude that overall the global budget does not increase.

We assume from now on that algorithm returned a cut $(X,Y)$ of $C^+$ with $|E(X,Y)|\geq \alpha'\cdot \alphasc(m)\cdot |X\cap T(C)|$, and so cluster $C$ has the $\alpha'$-bandwidth property.

Assume now that $|E(C)|\leq (\eta')^4|\delta_G(C)|$. From the definition of $\eta'$, we are then guaranteed that $|E(C)|\leq O(\eta^4\log^8m)\cdot |\delta_G(C)|$.
We then remove cluster $C$ from $\cset^A$ and add it to the set $\cset^I$ of inactive clusters, and to the set $\cset^I_1$ of clusters. Therefore, we assume from now on that
$|E(C)|> (\eta')^4|\delta_G(C)|$.

As a first step, we apply the algorithm from <Ref> to compute a well-linked decomposition $\wset$ of $C$, with parameter $\alpha'$. Recall that we are guaranteed that vertex sets
$\set{V(W)}_{W\in \wset}$ partition $V(C)$;
for each cluster $W\subseteq\wset$, $|\delta_G(W)|\le |\delta_G(C)|$, and each cluster $W\subseteq\wset$ has the $\alpha'$-bandwidth property.
We now consider two cases. If $\wset$ contains more than a single cluster, then we say that the well-linked decomposition step was successful; otherwise we say that it was unsuccessful. We assume first that the well-linked decomposition step was successful. We then remove $C$ from $\cset^A$, and add all clusters of $\wset$ to $\cset^A$ instead. We now show that the tota budget $B^*$ in the system did not increase. Let $B^*$ denote
; and

* $\sum_{R\in \rset}|\delta(R)|\le |\delta(S)|\cdot\left(1+O(\alpha\cdot \log^{3/2} n)\right)$

There is an efficient algorithm, that, given any graph $G=(V,E)$,  any cluster $S$ of $G$ and any parameter $\alpha\le 1/(48\log^2 n)$, computes a set $\rset$ of clusters of $S$, such that,

* the vertex sets $\set{V(R)}_{R\in \rset}$ partition $V(S)$;

* for each cluster $R\subseteq\rset$, $|\delta(R)|\le |\delta(S)|$;

* each cluster $R\subseteq\rset$ has the $\alpha$-bandwidth property; and

* $\sum_{R\in \rset}|\delta(R)|\le |\delta(S)|\cdot\left(1+O(\alpha\cdot \log^{3/2} n)\right)$.

Step 2: Sparse Balanced Cut.

In this step, we apply the algorithm from <Ref> to graph $C$ with parameter $\hat c=3/4$, to obtain a $\hat c'$-edge-balanced cut $(Z,Z')$ of $C$ (where $1/2<\hat c'<1$), whose value is at most
$O(\alphasc(m))$ times the value of a minimum $3/4$-edge-balanced cut  of $C$. We say that this step is successful if $|E_G(Z,Z')|<|E(C)|/\eta'$. Assume first that the step was successful. Then we remove cluster $C$ from set $\cset^A$, and add all connected components of graphs $C[Z],C[Z']$ to set $\cset^A$ insead. We now show that the total budget in the system does not increase as the result of this step. Observe that the budget of every vertex may only decrease, and the same is true for the budget of every edge, except for the edges in set $\delta_G(C)\cup E_G(Z,Z')$. The budget of each such edge may increase by at most $2\log_{3/2}m$, so the total increase in the budgets of all edges is bounded by $(|\delta_G(C)|+|E_G(Z,Z')|)\cdot 2\log_{3/2}m \leq \frac{4|E(C)|\cdot \log_{3/2}m}{\eta'}$ (we have used the fact that $|E(C)|> (\eta')^4|\delta_G(C)|$). We now show that this increase in total budget is compensated by the decrease in the budgets of the vertices of $Z$.

Assume without loss of generality that $|E(Z)|\leq |E(Z')|$.
Recall that for every vertex $v\in Z$, its original  budget is:
$B(v)=\frac{c\deg_C(v)\log_{3/2}m\cdot \log_{2}(|E(C)|)}{8\eta'}$.
From our assumption that $|E(Z)|\leq |E(Z')|$, $\log_{2}(|E(Z)|)\leq \log_{2}(|E(C)|)-1$.
The new budget of vertex $v$ is:

$$B'(v)=\frac{c\deg_Z(v)\log_{3/2}m\cdot \log_{2}(|E(Z)|)}{8\eta'}\leq \frac{c\deg_Z(v)\log_{3/2}m\cdot (\log_{2}(|E(C)|)-1)}{8\eta'}.$$

Therefore, for every vertex $v\in Z$, its budget decreases by at least

From the definition of a $(3/4)$-edge-balanced cut, $|E(Z')|\leq \hat c'|E(C)|$, for some universal constant $\hat c'$. In particular:

\[
\sum_{v\in Z}\deg_Z(v)\geq  |E(C)|-|E(Z')|\geq (1-\hat c')|E(C)|. \label{eq: many edges in Z}
\]

Overall, the budget of the vertices in $Z$ decreases by at least:

\[\frac{c\log_{3/2}m}{8\eta'}\cdot \sum_{v\in Z}\deg_Z(v)\geq \frac{c\log_{3/2}m}{8\eta'}\cdot (1-\hat c')\cdot |E(C)|.\]

Since $\hat c'<1$, and we can set $c$ to be a large enough constant, we can ensure that this is at least $\frac{4|E(C)|\cdot \log_{3/2}m}{\eta'}$, so the overall budget in the system does not increase.

If the current step is successful, then we replace cluster $C$ with the connected components of $C[Z]$ and $C[Z']$ in set $\cset^A$ and continue to the next iteration. Therefore, we assume from now on that the current step was not successful. In other words, the algorithm from  <Ref> returned a cut$(Z,Z')$ with $|E_G(Z,Z')|\geq |E(C)|/\eta'$. Since this cut is within factor $\alphasc(m)=O(\sqrt{\log m})$ from the minimum $3/4$-edge-balanced cut, we conclude that the value of the minimum $3/4$-edge-balanced cut in $C$ is at least $\rho=\frac{|E(C)|}{\eta'\cdot  \alphasc(m)}$.

From <Ref>, if the maximum vertex degree $\Delta$ in graph $C$ is at most $|E(C)|/2^{40}$ and $\optcro(C)\le |E(C)|^2/2^{40}$,
then graph $C$ has a $(3/4)$-edge-balanced cut of value at most $\tilde c\cdot\sqrt{\optcro(C)+\Delta\cdot|E(C)|}$ where $\tilde c>2^{40}$ is some universal constant.
As the size of the minimum $3/4$-balanced cut in $C$ is at least $\rho$, we conclude that either $\Delta\geq |E(C)|/2^{40}$, or $\optcro(C)> |E(C)|^2/2^{40}$, or
$\sqrt{\optcro(C)+\Delta\cdot|E(C)|}\geq \rho/\tilde c$. The latter can only happen if either $\optcro(C)\geq \rho^2/\tilde c^2$, or $\Delta\geq \rho^2/(\tilde c^2\cdot |E(C)|)$. Substituting the value of $\rho=\frac{|E(C)|}{\eta'\cdot  \alphasc(m)}$, we conclude that either $\optcro(C)\geq \frac{|E(C)|^2}{(\tilde c \eta'\alphasc(m))^2} $, or $\Delta\geq \frac{|E(C)|}{(\tilde c\eta'\alphasc(m))^2}$, or $\Delta\geq \frac{|E(C)|}{2^{40}}$. Note that we can check whether the last two conditions hold efficiently. If they do not hold, then we are guaranteed that $\optcro(C)\geq \frac{|E(C)|^2}{(\tilde c\eta'\alphasc(m))^2 }\geq \frac{|E(C)|^2}{\eta^2\poly\log m }$. Recall that we are also guaranteed that $|E(C)|> (\eta')^4\cdot |\delta_G(C)|=\Omega(\eta^4|\delta^G(C)|\log^8m)$. We then remove cluster $C$ from the set $\cset^A$ of active clusters and add it to set $\cset^I$ of inactive clusters, where it joins the set $\cset^I_2$ of clusters.

From now on we can assume that
$|E(C)|>\Omega(\eta^4|\delta^G(C)|\log^8m)$, and that either $\Delta\geq \frac{|E(C)|}{(\tilde c \eta'\alphasc(m))^2}$, or $\Delta\geq \frac{|E(C)|}{2^{40}}$ hold. Note that, since $\eta'=c\eta\log_{3/2}m\log_2 m$, and since we can set $c$ to be a large enough constant, we can ensure that $\frac{|E(C)|}{2^{40}}\geq \frac{|E(C)|}{\tilde c^2(\eta')^2\alphasc(m)}$. Therefore, from now on we assume that there is some vertex $v^*$ in graph $C$, whose degree in $C$ is at least $\frac{|E(C)|}{(\tilde c \eta'\alphasc(m))^2}$.
Since we have assumed that $|E(C)|\geq (\eta')^4|\delta_G(C)|$, we get that
$\deg_G(v^*)\geq 8|\delta_G(C)|\eta'$.

Step 3: routing to a vertex

We consider again the graph $C^+$ that we have defined in Step 1, with the corresponding set $T(C)=\set{t_e\mid e\in \delta_G(C)}$ of terminal vertices.
Using standard Maximum Flow computation, we compute a maximum-cardinality set $\pset$ of edge-disjoint paths, where each path connects a distinct vertex of $T(C)$ to to vertex $v^*$. We now consider two cases. In the first case, $|\pset|=|\delta_G(C)|$. In this case, there is a set $\qset(C)$ of edge-disjoint paths in cluster $C$, routing edges of $\delta_e(C)$ to vertex $v^*$, which can be easily obtained from $\pset$. We then remove cluster $C$ from the set $\cset^A$ of active clusters and add it to set $\cset^I$ of inactive clusters, where it joins cluster set $\cset^I_3$.

Assume now that $|\pset|<|\delta_G(C)|$. From the maximum flow / minimum cut theorem, there is a collection $E'$ of at most $|\delta_G(C)|$ edges in graph $C^+$, such that, in graph $C^+\setminus E'$, there is no path connecting an edge of $\delta_G(C)$ to vertex $u^*$. Let $C'$ be the connected component of $C^+\setminus E'$ containing $v^*$, so $C'\subseteq C$. Note that $\delta_G(C')\subseteq E'$, so there is a set $\qset(C')$ of edge-disjoint paths routing the edges of $\delta_G(C')$ to vertex $v^*$, with all inner vertices of the paths in $\qset(C')$ lying in $C'$; in other words, $\qset(C')$ is an internal $C'$-router. We add cluster $C'$ to set $\cset^I$ and $\cset^I_3$. Next, we delete cluster $C$ from $\cset^A$, and we add every connected component of $C\setminus C'$ as a new cluster to set $\cset^A$.

It now remains to prove that the total budget in the system does not increase as the result of these changes. Note that the budget of every vertex may only decrease, and the budget of every edge, except for the edges of $\delta_G(C)\cup E'$, may also only decrease. The increase in the budget of every edge in $\delta_G(C)\cup E'$ is bounded by $2\log_{3/2}m$. Therefore, the total increase in the budget is bounded by $(|\delta_G(C)|+|E'|)\cdot 2\log_{3/2}m\leq 4|\delta_G(C)|\cdot  \log_{3/2}m$. Note that the budget of vertex $v^*$ was initially at least $\frac{c\deg_C(v)\log_{3/2}m\cdot \log_{2}(|E(C)|)}{8\eta'}$, and it becomes $0$ at the end of this step. Therefore, the decrease in the budget is at least:

\[\frac{c\deg_C(v^*)\log_{3/2}m\cdot \log_{2}(|E(C)|)}{8\eta'}\geq 4|\delta_G(C)|\cdot  \log_{3/2}m,\]

since $\deg_C(v^*)\geq 8|\delta_G(C)|\eta'$. Overall, the budget does not grow.
The algorithm terminates once $\cset^A$ becomes empty, and it returns the set $\cset^I$ of clusters. From our invariants, it is immediate to verify that this set of clusters has all required properties. It remains to establish that the algorithm is efficient. In every iteration of the algorithm, we either add a cluster to set $\cset^I$, or we split a single cluster of $\cset^A$ into at least two clusters. Once a cluster is added to $\cset^I$, it remains there until the end of the algorithm. It is then easy to verify that the number of iterations is bounded by $O(|V(G)|)\le O(m)$, and every iteration can be executed efficiently.

§.§ Proof of <Ref>

Let $\phi^*$ be the optimal solution to instance $(\tilde C,\Sigma_{\tilde C})$. We can assume w.l.o.g. that every pair of edges cross at most once in $\phi^*$. Denote by $\chi$ the collection of all pairs $e,e'\in E(\tilde C)$ of edges, such that the images of $e$ and $e'$ cross in $\phi^*$.

Assume for now that, for every cluster $W\in \wset^{\light}$, the routers $\qset(W)$ and $\hat \qset(W)$ are fixed, and so the rotation system $\hat \Sigma$ for graph $H$ is fixed as well. For every edge $e\in E(\tilde C)$, we define an integer $N(e)$ as follows. If there is a cluster $W\in \wset^{\light}$ with $e\in E(W)$, then we let $N(e)$ be the number of paths in $\hat \qset(W)$ containing $e$. Therefore, $N(e)=\cong_G(\hat \qset(W),e)\leq \cong_G(\qset(W),e)$. Otherwise, we set $N(e)=1$.
We will prove the following observation:

Suppose the routers $\hat \qset(W)$ for all clusters $W\in \wset^{\light}$ are fixed, and let $\hat \Sigma$ be the corresponding rotation system for $H$. Then:

$$\optcrors(H, \hat \Sigma)\leq O\left(\sum_{(e,e')\in \chi}N(e)\cdot N(e')\right )+O\left(\sum_{e\in E(\tilde C)}(N(e))^2\right )$$

The proof of <Ref> immediately follows from <Ref>. Indeed:

\[
\begin{split}
\expect{\optcrors(H, \hat \Sigma)}&\leq \expect{\sum_{(e,e')\in \chi}O(N(e)\cdot N(e'))+\sum_{e\in E(\tilde C)}O((N(e))^2)}\\