We associate every pair $(e',e'')\in M$ of edges with a distinct path $R_1(e)\in \rset_1(v)$ that contains $e'$ as is last edge, and with a distinct path $R_2(\tilde e)\in \rset_2(v)$ that contains $e''$ as its first edge. Therefore, we can view the set $M$ of edge pairs as defining a matching $M'$ between the paths of $\rset_1(v)$ and the paths of $\rset_2(v)$. For every edge $e\in \hat E$ with $R'(e)\in \rset(v)$, we define a new path $R''(e)$, that is obtained by concatenating the path $R_1(e)$ with the path $R_2(\tilde e)$, where $R_2(\tilde e)$ is the path of $\rset_2$ that is matched to $R_1(e)$ by $M'$. Let $\rset'(v)=\set{R''(e)\mid R'(e)\in \rset(v)}$ be this new set of paths. We then update the path set $\rset'$ by deleting all paths of $\rset(v)$ from it, and adding the paths of $\rset'(v)$ to it instead. Note that the resulting set of path is still guaranteed to only contain left-monotone paths in graph $G$, that route the edges of $\hat E$ to vertices of $V'$, with edge-congestion at most $O(\log^{18}m)$. Note that, for every pair of paths in $\rset'$ that contain the vertex $v$, their intersection at vertex $v$ is now non-transversal.

Once every vertex of $V''$ is processed, we obtain the final set of paths $\pset^{\out,\lef}=\rset'$. It is immediate to verify that each resulting path must be simple (from the fact that $H'$ is acyclic). From the above discussion, the paths in $\pset^{\out,\lef}$ cause edge-congestion at most $O(\log^{18}m)$, and, for each edge $e\in \hat E$, there is a unique path $P^{\out,\lef}(e)\in \pset^{\out,\lef}$, whose first edge is $e$, and the path is left-monotone. Moreover, our algorithm ensures that the paths in $\pset^{\out,\lef}$ are non-transversal with respect to $\Sigma$, and that, for every vertex $v\in V'$, exactly $n_1(v)$ paths in $\pset^{\out,\lef}$  terminate at $v$.

§.§ Proof of <Ref>

In order to prove the claim, we use the following observation.

Let $\iset$ be a collection of $k$ intervals of non-zero length, where for each interval $I\in \iset$, $I\subseteq [0,r]$, interval $I$ is closed on the left and open on the right, and the endpoints of $I$ are integers in $\set{0,\ldots,r}$.
Let $\iset'$ be another collection of $k$ intervals of non-zero length, where for each interval $I'\in \iset'$, $I'\subseteq [0,r]$, interval $I'$ is closed on the left and open on the right, and the endpoints of $I'$ are integers in $\set{0,\ldots,r}$. Assume further that for every integer $0\leq i\leq r$, the number of intervals of $\iset$ for which $i$ serves as the left endpoint is equal to the number of intervals of $\iset'$ for which $i$ serves as the left endpoint, and similarly, the number of intervals of $\iset$ for which $i$ serves as the right endpoint is equal to the number of intervals of $\iset'$ for which $i$ serves as the right endpoint. Then for every integer $p\in [0,r)$, the total number of intervals in $\iset$ containing $p$ is equal to the total number of intervals in $\iset'$ containing $p$.

Let $p$ be any integer in $[0,r)$.
Consider any interval $I=(a,b)\in \iset\cup \iset'$. Clearly, $p\in I$ iff $a\leq p<b$.

Let $\iset_1\subseteq \iset$ be the set of all intervals $I=[a,b)\in \iset$ with $a\leq p$, and let $\iset_2\subseteq \iset$ be the set of all intervals $I=[a,b)\in \iset$ with $b\leq p$. Clearly, $\iset_2\subseteq \iset_1$, and an interval $I\in \iset$ contains the point $p$ iff $I\in \iset_1\setminus \iset_2$. We define subsets $\iset_1',\iset_2'$ of intervals of $\iset'$ similarly. As before, an interval $I'\in \iset'$ contains the point $p$ iff $I'\in \iset'_1\setminus \iset'_2$. Since, for every integer $0\leq i\leq p$, the number of intervals in $\iset$ whose left endpoint is $i$ is equal to the number of intervals in $\iset'$ whose left endpoint is $i$, we get that $|\iset_1|=|\iset_1'|$. Similarly, since, for every integer $0\leq i\leq p$, the number of intervals in $\iset$ whose right endpoint is $i$ is equal to the number of intervals in $\iset'$ whose right endpoint is $i$, we get that $|\iset_2|=|\iset'_2|$.
Therefore, $|\iset_1\setminus \iset_2|=|\iset_2'\setminus \iset_2'|$. Since $\iset_1\setminus \iset_2$ is precisely the set of all  intervals $I\in \iset$ that contain $p$, and $\iset_1'\setminus \iset_2'$ is precisely the set of all intervals $I'\in \iset'$ that contiain $p$, the observation follows.

We construct two collections of intervals, $\iset=\set{I(e)\mid e\in \hat E}$, and $\iset'=\set{I'(e)\mid e\in \hat E}$, as follows. Consider an edge $e\in \hat E$. Assume that $\spann'(e)=\set{i',i'+1,\ldots,j'-1}$, and that $\spann''(e)=\set{i'',i''+1,\ldots,j''-1}$. We then let $I(e)=[i',j')$ and $I'(e)=[i'',j'')$.

Let $L$ be the multiset of integers, that serve as the left endpoint of every interval in $\iset$. Consider an integer $1\leq i\leq r$. The number of times that $i$ appears in set $L$ is equal to the number of edges $e\in \hat E$, such that $i$ is the first element of $\spann'(e)$; equivalently, the prefix path $P^1(e)$ must terminate at a vertex of $S_i$. Therefore, the number of times that integer $i$ appears in $L$ is $\sum_{v\in V(S_i)}n_1(v)$. Note that, if $i$ is the left endpoint of some interval $I'(e)\in \iset'$, then path $P^{\out}(e)$ must originate at a vertex of $S_i$. Therefore, path $P^{\out,\lef}(e)$ that was constructed by the algorithm from <Ref> must terminate at a vertex of $S_i$. From <Ref>, for every vertex $v\in V'$, the number of paths of $\pset^{\out,\lef}$ terminating at $v$ is exactly $n_1(v)$. Therefore, the number of intervals of $\iset'$ for which $i$ serves as the left endpoint is equal to $\sum_{v\in V(S_i)}n_1(v)$, which is exactly the number of intervals of $\iset$, for which $i$ serves as the left endpoint.

Using similar reasoning, for every integer $1\leq i\leq r$,
the number of intervals of $\iset'$ for which $i$ serves as the right endpoint is equal to  the number of intervals of $\iset$, for which $i$ serves as the right endpoint.

Note that for each integer $1\leq t\leq r$, the number of intervals of $\iset$ containing $t$ is precisely $N_t$, while the number of intervals of $\iset'$ containing $t$ is precisely $N'_t$. We conclude that $N_t=N'_t$.

In order to prove the second assertion, observe that, for every index $1\leq t<r$, for every edge $e\in \hat E $ with $t\in \spann'(e)$, the mid-segment $P^2(e)$ of the nice guiding path $P(e)\in \hat \pset$ must contain some edge of $E_t$. Since the paths in $\hat \pset$ cause congestion at most $O(\log^{18}m)$, we get that $N_t\leq O(\log^{18}m)\cdot |E_t|$.

§.§ Proof of <Ref>

Consider an edge $e\in E(G)$.  Recall that, if $e$ is a primary edge for an index $1\leq z\leq r$ (that is, $e\in E(\tilde S_z)\cup \delta_G(\tilde S_z)$), then $N'_z(e)=1$. Otherwise, $N'_z(e)$ is the number of paths in set:
$$\set{Q(e')\mid e'\in E_{z-1}\cup E_z^{\lef}}\cup \set{Q'(e')\mid e'\in E_z\cup E_z^{\rig}}$$
that contain $e$. Here, for an edge  $e'\in E_{z-1}\cup E_z^{\lef}$, $Q(e')$ is the unique path of the internal router $\qset(U_{z-1})$ that originates at $e'$, and for an edge $e'\in E_z\cup E_z^{\rig}$, $Q'(e')$ is the unique path of the external router $\qset'(U_z)$ that originates at $e'$.
If a secondary edge $e\in E(S_{z-1})\cup E(S_{z+1})$, then, from <Ref>, $\expect{N'_z(e)}\leq \expect{N_z(e)}\leq \hat \eta$.
Otherwise, $N'_z(e)$ is the total number of auxiliary cycles in set $\set{W(e')\mid e'\in  E_z^{\lef}\cup E_z^{\rig}}$
that contain the edge $e$. Consider now some edge $e'\in \hat E$, and assume that $\spann(e')=\set{i,\ldots,j-1}$. Then $e'$ may lie in set $E_z^{\lef}\cup E_z^{\rig}$ only for $z\in \set{i,j}$. It may also be a primary edge only for indices $z\in \set{i,j}$.
Since, from <Ref>, edge $e$ may appear on at most $O(\log^{34}m)$ cycles in $\wset$, and since there are at most $O(1)$ indices $z$, for which $e\in E_{z-1}\cup E_z\cup E_z^{\lef}\cup E_z^{\rig}$, or $e$ is a primary edge, we get that, overall,

\[\expect{\sum_{z=1}^rN'_z(e)}\leq O(\hat \eta)+O(\log^{34}m)\leq O(\hat \eta).\]

§.§ Proof of <Ref>

Recall that, for $1\leq z\leq r$, $\Pi^T_z$ is the set of all triples $(e,e',v)$, where $e\in E_z^{\rig}$, $e'\in \hat E_z$, and $v$ is a vertex that lies on both $W(e)$ and $W(e')$, such that cycles $W(e)$ and $W(e')$ have a transversal intersection at $v$.  Note that $E_z^{\rig}\subseteq \hat E_z$.
Recall that, from <Ref>, for every pair $e,e'\in \hat E_z$ of edges, there is at most
one vertex $v$, such that $W(e)$ and $W(e')$ have a transversal intersection at vertex $v$. We say that a triple $(e,e',v)\in \Pi^T_z$ is a type-1 triple if the cycles $W(e), W(e')$ share an edge. Let $(e,e',v)$ be a type-1 triple of $\Pi^T_z$, and  let $e^*$ be an arbitrary edge shared by $W(e)$ and $W(e')$. We say that edge $e^*$ is responsible for the triple $(e,e',v)$. If the cycles $W(e),W(e')$ do not share edges, then we say that triple $(e,e',v)$ is a type-2 triple.

We now bound the total number of type-1 triples in $\bigcup_{z=1}^r\Pi^T_z$. Consider an edge $e^*\in E(G)$. From <Ref>, edge $e^*$ may appear on at most $O(\log^{34}m)$ cycles in $\wset$. Consider now any such pair $W(e),W(e')$ of cycles. Assume that $\spann(e)=\set{i,\ldots,j-1}$, and $\spann(e')=\set{i',\ldots,j'-1}$. Recall that a triple $(e,e',v)$ may only lie in a set $\Pi^T_z$ if $e\in E_z^{\rig}$, so $z=i$ must hold. Therefore, every pair $e,e'\in \hat E$ of edges, for which $e^*\in E(W(e))\cap E(W(e'))$, contributes at most $O(1)$ triples to set $\bigcup_{z=1}^r\Pi^T_z$. Overall, edge $e^*$ may be responsible for at most $O(\log^{68}m)$ triples in  $\bigcup_{z=1}^r\Pi^T_z$, and the total number of type-1 triples in $\bigcup_{z=1}^r\Pi^T_z$ is at most $|E(G)|\cdot O(\log^{68}m)$.

Next, we consider a type-2 triple $(e,e',v)\in \Pi^T_z$. Observe that $v$ is the only vertex at which $W(e)$ and $W(e')$ have a transversal intersection, and cycles $W(e),W(e')$ do not share any edges. It is then easy to see that, in the drawing $\phi^*$ of graph $G$, there must be a crossing between an edge of $W(e)$ and an edge of $W(e')$. We say that this crossing is responsible for the triple $(e,e',v)$.

Consider now some crossing $(e_1,e_2)\in \chi^*$. As before, from <Ref> edge $e_1$ lies on at most $O(\log^{34}m)$ cycles of $\wset$, and the same bound holds for edge $e_2$. Therefore, there are at most $O(\log^{68}m)$ pairs $(e,e')\in \hat E$ of edges, with $e_1\in W(e)$ and $e_2\in W(e')$. As before, there is at most one index $z$ for which $e_1\in E_z^{\rig}$, and at most one index $z$, for which $e_2\in E_z^{\rig}$. Therefore, crossing $(e_1,e_2)$ may be responsible for at most $O(\log^{68}m)$ triples in $\bigcup_{z=1}^r\Pi^T_z$, and the total number of type-2 triples in $\bigcup_{z=1}^r\Pi^T_z$ is at most $|\chi^*|\cdot O(\log^{68}m)$.

§.§ Proof of <Ref>

From now on, we assume for contradiction that
we assume that $E(H(e_1))\cap E(H(e_2))=\emptyset$, and, additionally, there is no pair of edges $\tilde e_1\in H(e_1)$, $\tilde e_2\in H(e_2)\cup W''(e_2)$, whose images cross in $\phi^*$, and similarly, there is no pair of edges $\tilde e_1'\in H(e_1)\cup W''(e_1)$, $\tilde e_2'\in H(e_2)$,  whose images cross in  $\phi^*$.
From <Ref>, edges $\hat a_{e_1}',\hat a_{e_2}',a'_{e_1},a'_{e_2}$ appear in this order in the rotation $\oset_{u_{z-1}}\in \Sigma$.

We now define two points in the drawing $\phi^*$ of $G$: point $p$, that is an internal point on the image of edge $\hat a_{e_2}$, that is very close to the image of the vertex $\hat x_{e_2}$, such that the segment of the image of edge $a_{e_2}$ between $p$ and the image of $\hat x_{e_2}$ does not participate in any crossings. The second point, $p'$, is defined similarly on the image of edge $a_{e_2}$, very close to the image of vertex $x_{e_2}$
(see <Ref>).

Illustration for the proof of <Ref>. Edges $\hat a_{e_1}$ and $a_{e_2}$ are shown in red, with points $p$ and $p'$ marked. Path $W'(e_1)$ is the concatenation of the brown path and edges $a_{e_1}, \hat a_{e_1}$. Path $W''(e_1)$ is shown in pink.

Next, we consider three curves in the drawing $\phi^*$ of $G$. The first curve, $\gamma_1$, is the union of the images of paths  $\hat P(e_1)$ and $ P(e_1)$ in $\phi^*$. The second curve, $\gamma_2$, is the image of the path $W'(e_1)$, and the third curve, $\gamma_3$, is the image of the path $W''(e_1)$ in $\phi^*$
(see <Ref>).
Observe that the endpoints of each of the three curves are the images of vertices $y_{e_1}$ and $\hat y_{e_1}$, and that points $p$ and $p'$ may not lie on any of these curves, as we have assumed that $E(H(e_1))\cap E(H(e_2))=\emptyset$. We will next show that the closed curve obtained by the union of curves $\gamma_1$ and $\gamma_2$ may not separate points $p$ and $p'$; the closed curve obtained by the union of the curves $\gamma_1$ and $\gamma_3$ must separate points $p$ and $p'$; and the closed curve obtained by the union of the curves $\gamma_2$ and $\gamma_3$ may not separate points $p$ and $p'$. We will then show that this is impossible, reaching a contradiction.

Curves $\gamma_1,\gamma_2$, and  $\gamma_3$.

Let $\tilde \gamma_1$ be the closed curve obtained by the union of the curves $\gamma_2$ and $\gamma_3$. The points $p$ and $p'$ are not separated by $\tilde \gamma_1$. In other words, if we consider the open regions into which curve $\tilde \gamma_1$ partitions the sphere, then points $p,p'$ lie in the same region.

Assume otherwise. Consider another curve $\gamma^*$, which is obtained from the image of the path $W'(e_2)$, by truncating it so it connects point $p$ to point $p'$.

Notice that path $W'(e_2)$ may not share any vertices with $W''(e_1)$ (except possibly for the endpoints of path $W'(e_2)$, whose images do not appear on curve $\gamma^*$).
Moreover, cycles $W(e_1)$ and $W(e_2)$ may not have transversal intersections at a vertex of $V(S_{z-1})$ (from <Ref>).
Since we have assumed that no edge of $W'(e_2)\subseteq H(e_2)$ may cross an edge of $H(e_1)\cup W''(e_1)$, we get that curve $\gamma^*$ may not cross curve $\tilde \gamma_1$, and so points $p$ and $p'$ may not be separated by curve $\tilde \gamma_1$.

From <Ref>, we can define a simple curve $\zeta$, whose endpoints are $p$ and $p'$, such that neither of the curves $\gamma_2,\gamma_3$ crosses $\zeta$.

Let $\tilde \gamma_2$ be the closed curve obtained by the union of the curves $\gamma_1$ and $\gamma_2$. Then points $p$ and $p'$ are not separated by $\tilde \gamma_2$. In other words, if we consider the open regions into which curve $\tilde \gamma_2$ partitions the sphere, then points $p,p'$ lie in the same region.

Assume otherwise. Consider another curve $\gamma^*$, which is obtained from the image of the path $W''(e_2)$, by appending to it the image of edge $\hat a_{e_2}$ between the image of vertex $\hat y_{e_2}$ and point $p$, and the image of edge $a_{e_2}$ between the image of vertex $y_{e_2}$ and point $p'$.

Notice that path $W''(e_2)$ may not share any vertices with paths $W'(e_1)$, $P(e_1)$, and $P(e_2)$ (except for possibly the endpoints of $W''(e_2)$). Observe also that paths $W'(e_1),P(e_1)$ both contain the edge $a_{e_1}=(x_{e_1},y_{e_1})$, so, even if vertex $y_{e_1}\in W''(e_2)$, curve $\gamma^*$ may not cross curve $\tilde \gamma_2$ at the image of vertex $y_{e_1}$. Similarly, paths $W'(e_1),\hat P(e_1)$ both contain the edge $\hat a_{e_1}=(\hat x_{e_1},\hat y_{e_1})$. Therefore, even if vertex $\hat y_{e_1}\in W''(e_2)$, curve $\gamma^*$ may not cross curve $\tilde \gamma_2$ at the image of vertex $\hat y_{e_1}$. Since we have assumed that no edge of $W''(e_2)$ may cross an edge of $H(e_1)$, we conclude that curve $\gamma^*$ may not cross curve $\gamma_2$. Therefore, points $p$ and $p'$ must lie in the same region defined by $\tilde \gamma_2$.

From <Ref>, we can now define a simple curve $\zeta'$, whose endpoints are $p$ and $p'$, such that neither of the curves $\gamma_1,\gamma_2$ crosses $\zeta'$.
Let $\zeta^*$ be the curve obtained from the union of the curves $\zeta,\zeta'$. Recall that curve $\gamma_2$, that connects the images of the vertices $y_{e_1}$ and $\hat y_{e_1}$, may not cross the curve $\zeta^*$. Therefore, if we denote by $q$ and $q'$ the images of the vertices $y_{e_1}$ and $\hat y_{e_1}$, respectively, then points $q$ and $q'$ do not lie on curve $\zeta^*$, and they are not separated by curve $\zeta^*$. Lastly, we need the following observation.

Let $\tilde \gamma_3$ be the closed curve obtained by the union of the curves $\gamma_1$ and $\gamma_3$. Then points $p$ and $p'$ are separated by $\tilde \gamma_3$. In other words, if we consider the set $\fset$ open regions into which curve $\tilde \gamma_3$ partitions the sphere, then points $p,p'$ lie in different regions.

Recall that we have assumed that $E(H(e_1))\cap E(H(e_2))=\emptyset$, and that no edge of $H(e_1)\cup W''(e_1)$ may cross an edge of $P(e_2)\cup \hat P(e_2)\subseteq H(e_2)$. Additionally, path $W''(e_1)$ is internally disjoint from paths $P(e_2)$ and $\hat P(e_2)$, and,
since paths in $\qset(S_{z-1})$ are non-transversal with respect to $\Sigma$, paths $P(e_1),\hat P(e_1),P(e_2),\hat P(e_2)$ do not have transversal intersections. Therefore, the image of path $P(e_2)$  beween point $p'$ and the image of vertex $u_{z-1}$ may not cross the curve $\tilde \gamma_3$, and it must be contained in a single region of $\fset$, that we denote by $F$. Similarly, the image of path $\hat P(e_2)$  beween point $p$ and the image of vertex $u_{z-1}$ may not cross the curve $\tilde \gamma_3$, and it must be contained in a single region of $\fset$, that we denote by $F'$. Lastly, recall that we have established that the images of edges  $\hat a_{e_1}',\hat a_{e_2}',a'_{e_1},a'_{e_2}$ enter the image of edge $u_{z-1}$ in this circular order. Recall that edges $\hat a_{e_1}',a'_{e_1}$ lie on paths $\hat P(e_1),P(e_1)$, respectively, while edges  $\hat a_{e_2}',a'_{e_2}$ lie on paths $\hat P(e_2),P(e_2)$, respectively. Since curve $\tilde \gamma_3$ is a closed curve, it must be the case that $F\neq F'$.

To summarize, so far we have defined two points $p,p'$, and two curves $\zeta,\zeta'$ connecting them. We have also denoted by $\zeta^*$ the closed curve obtained by taking the union of these two curves. We also defined two points $q$ and $q'$, and two curves $\gamma_1,\gamma_3$ connecting them, and we denoted by $\tilde \gamma_3$ the closed curve obtained by taking the union of these two curves. We have established that curve $\zeta^*$ may not separate $q$ and $q'$, while curve $\tilde \gamma_3$ must separate $p$ and $p'$. Lastly, from the definition, curve $\gamma_1$ may not cross $\zeta'$, while curve $\gamma_3$ may not cross $\zeta$. We now show that this is impossible to achieve. We denote by $D$ a disc in the plane, whose boundary lies on curve $\zeta^*$, and whose interior contains the points $q$ and $q'$, and does not contain any point of $\zeta^*$. Such a disc must exist, since points $q$ and $q'$ are not separated by $\zeta^*$. Note that points $p$ and $p'$ do not lie in the interior of the disc $D$, and yet they are separated by curve $\tilde \gamma_3$. this may only happen if curve $\tilde \gamma_3$ intersects both $\zeta$ and $\zeta'$.

Consider curve $\tilde \gamma$ that is obtained from $\tilde \gamma_3$ by deleting the point $q$ from it. On this curve, we can mark two points $a$ and $b$, such that $a$ lies on $\zeta$, $b$ lies on $\zeta'$, and no point of $\tilde \gamma$ that lies between $a$ and $b$ belongs to $\zeta^*$. Denote by $\tilde \gamma'$ the segment of $\tilde \gamma$ between $a$ and $b$. Note that this segment is disjoint from the interior of $D$, so it may not contain the point $q'$. Therefore, either $\tilde \gamma\subseteq \gamma_1$, or $\tilde \gamma\subseteq \gamma_3$. In the former case, we get that $\gamma_1$ crosses $\zeta'$, while in the latter case, we get that $\gamma_3$ crosses $\zeta$, a contradiction.

Consider now the drawing $\phi^*$ of graph $G$. We let $p_1$ be an inner point on the image of edge $\hat a_{e_1}$, that is very close to the image of vertex $\hat x_{e_1}$, and we let $p_1'$ be an inner point on the image of edge $a_{e_1}$, that is very close to the image of vertex $x_{e_1}$. We delete from drawing $\phi^*$ the images of all edges and vertices except for those that belong to graph $H(e_1)$. The resulting drawing partitions the sphere into open regions, and we denote this set of open regions by $\fset_1$. We denote by $F_1,F_1'\in \fset_1$ the regions in whose interiors points $p_1$ and $p_1'$ lie, respectively.

Similarly, we let $p_2$ be an inner point on the image of edge $\hat a_{e_2}$, that is very close to the image of vertex $\hat x_{e_2}$, and we let $p_2'$ be an inner point on the image of edge $a_{e_2}$, that is very close to the image of vertex $x_{e_2}$. We delete from drawing $\phi^*$ the images of all edges and vertices except for those that belong to graph $H(e_1)$. The resulting drawing partitions the sphere into open regions, and we denote this set of open regions by $\fset_2$. We denote by $F_2,F_2'\in \fset_2$ the regions in whose interiors points $p_1$ and $p_1'$ lie, respectively. We need the following claim:

Assume that for every pair of edges $\tilde e_1'\in E(H(e_1)), \tilde e_2'\in E(H(e_2))$, the images of $\tilde e_1'$ and $\tilde e_2'$ do not cross in the drawing $\phi^*$ of $G$. Then
either $F_1\neq F_1'$, or $F_2\neq F_2'$ must hold.

We prove the claim below, after we complete the proof of <Ref> using it.

It now remains to prove <Ref>.

Assume for contradiction that $F_1=F_1'$ and that $F_2=F_2'$. Consider the drawing $\phi^*$ of graph $G$. Then we can draw a curve $\gamma_1$, connecting points $p_1$ and $p_1'$, so that $\gamma_1$ does not cross the image of any vertex or any edge in $H(e_2)$. Let $\gamma^*_1$ be the curve obtained by the union of curve $\gamma_1$, the images of the paths $P(e_1),\hat P(e_1)$, the image of edge  $\hat a_{e_1}$  between the image of $\hat x_{e_1}$ and point $p_1$, and the image of edge $a_{e_1}$, bewteen the image of vertex $x_{e_1}$ and point $p_1'$. Since we have assumed that no edge lies in both $H(e_1)$ and $H(e_2)$, and since the paths in $\qset(S_z)$ are non-transversal with respect to $\Sigma$, the images of the paths $P(e_2),\hat P(e_2)$ may not cross the curve $\gamma^*_1$, except at the image of vertex $u_{z-1}$.

Similarly, we can draw a curve $\gamma_2$, connecting points $p_2$ and $p_2'$, so that $\gamma_2$ does not cross the image of any vertex or any edge in $H(e_1)$. Let $\gamma^*_2$ be the curve obtained by the union of curve $\gamma_2$, the images of the paths $P(e_2),\hat P(e_2)$, the image of edge  $\hat a_{e_2}$  between the image of vertex $\hat x_{e_2}$ and point $p_2$, and the image of edge $a_{e_2}$, between the image of vertex $x_{e_2}$ and point $p_2'$. Since we have assumed that no edge lies in both $H(e_1)$ and $H(e_2)$, and since the paths in $\qset(S_z)$ are non-transversal with respect to $\Sigma$, the images of the paths $P(e_1),\hat P(e_1)$ may not cross the curve $\gamma^*_2$, except at the image of vertex $u_{z-1}$.

We now obtained two closed curves, $\gamma^*_1$ and $\gamma^*_2$.

only old stuff below

§.§ Proof of <Ref>

We first prove property <ref>.
First, from the construction of $\wset_i$ and <Ref>, every edge in $E(G)\setminus \big(\bigcup_{1\le i\le r}E(S_i)\big)$ participates in at most $O(\cong(\pset))\le O(\log^{18} m)\le \beta^*$ paths in $\wset$.
Consider now an index $1\le i\le r$ and consider an edge $e\in E(S_i)$.

Assume first that $i\in Z_{\text{fail}}$. From the construction of $\wset$, <Ref> and the analysis in Step 1,
$$\expect[]{\cong_G(\wset,e)}\le O(\log^{18} m)\cdot \expect[]{\cong_G(\qset_i,e)}\le O(\log^{18} m)\cdot O(\log^4m/\alpha^*)\le \beta^*.$$

Assume now that $i\in Z_{\text{succ}}$. From <Ref>,

$$\expect[]{\cong_G(\wset,e)}\le O(\log^{18} m)\cdot \expect[]{\cong_G(\qset_i,e)}\le O(\log^{18} m)\cdot \expect[]{(\cong_G(\qset_i,e))^2} \le O(\log^{18} m)\cdot\beta^*.$$

We then prove property <ref>. Let $1\le i_1<\cdots<i_k\le r$ be all indices in $Z_{\text{fail}}$. We will show that, for each $1\le t\le k-1$, $\sum_{i_t\le i <i_{t+1}} |\wset^{\bad}_i|\le |\delta(S_{i_t})|\cdot\cong_G(\pset)$. In fact, since a bad path in $\wset_i$ must contain an edge from a bad cluster, from the construction of set $\wset_i$, for an edge $e\in E(U_i,\notU_i)$, if the path $W_i(e)$ in $\wset_i$ is bad, then it has to visit the cluster $S_{i_t}$, and therefore contain an edge of $|\delta(S_{i_t})|$. From <Ref>, each edge of $\delta(S_{i_t})$ participates in at most $\cong_G(\pset)$ paths in $\wset$, and it follows that $\sum_{i_t\le i <i_{t+1}} |\wset^{\bad}_i|\le |\delta(S_{i_t})|\cdot\cong_G(\pset)$.

\begin{equation*}
\begin{split}
\sum_{1\le i\le r-1}|\wset^{\bad}_i|^2 & \text{ }\le
\sum_{1\le t\le k}\bigg(\sum_{i_t\le i<i_{t+1}}|\wset^{\bad}_i|\bigg)^2\le
\sum_{1\le t\le k}|\delta(S_{i_t})|^2\cdot(\cong_G(\pset))^2\\
&\text{ }\le \sum_{1\le t\le k}O\big(\eta^*\cdot(\cong_G(\pset))^2\cdot (\chi(S_{i_t})+|E(S_{i_t})|)\big)
\le O\big(\eta^*\cdot \log^{36}m\cdot(\cro(\phi^*)+|E(G)|)\big).\\
\end{split}
\end{equation*}

We now prove <ref>. Note that the paths in $\wset^{\gd}$ does not intersect any cluster $S_i$ with $i\in Z_{\text{fail}}$. Therefore,
from <Ref>, for each edge $e\notin\bigcup_{S\in \sset}E(S)$, $\expect[]{(\cong_G(\wset^{\gd},e))^2}\le (\cong_G(\pset))^2\le O(\log^{36}m)$; for each edge $e\in E(S_i)$ where $i\in Z_{\text{fail}}$, $\expect[]{(\cong_G(\wset^{\gd},e))^2}=0$; and for each edge $e\in E(S_i)$ where $i\in Z_{\text{succ}}$, $\expect[]{(\cong_G(\wset^{\gd},e))^2}\le (\cong_G(\pset))^2\cdot\beta^*\le O(\log^{36}m\cdot \beta^*)$.

We then prove property <ref>. From <Ref>,

\[
\expect[]{\sum_{e\in E(S_i)}(\cong_G(\wset,e))^2}\le
O(\log^{36}m)\cdot\expect[]{(\cong_G(\qset_i,e))^2}\le O(\log^{36}m)\cdot \beta^*.
\]

We then prove property <ref>.
In fact,

\[
\begin{split}
& \expect{\sum_{e,e'\in E(G)}\chi(e,e')\cdot \cong_G(\wset^{\gd},e)\cdot \cong_G(\wset^{\gd},e')}\\
\le & \sum_{e,e'\in E(G)}\chi_{\phi}(e,e')\cdot \expect{\frac{(\cong_G(\wset^{\gd},e))^2+ (\cong_G(\wset^{\gd},e'))^2}{2}}
\\
\le & \sum_{e\in E(G)}\bigg(\sum_{e'\in E(G)}\chi_{\phi}(e,e')\bigg)\cdot \expect{(\cong_G(\wset^{\gd},e))^2}
\\
\le & \sum_{e\in E(G)}\chi_{\phi}(e)\cdot\expect{(\cong_G(\wset^{\gd},e))^2}\le O(\beta^*\cdot\log^{36}m\cdot \cro(\phi^*)),
\end{split}
\]

where the last inequality uses property <ref>.

§.§ Proof of <Ref>

We will prove that:

if $e\in E_{\text{succ}}$, then $\expect[]{\cong_G(\wset^{\gd},e)\cdot \cong_G(\wset^{\bad},e')}\le O\big(\beta^*\cdot \log^{36}m\big)$;

if $e\in E_{\text{fail}}$, then $\expect[]{\cong_G(\wset^{\gd},e)\cdot \cong_G(\wset^{\bad},e')}=0$; and

if $e\notin E_{\text{succ}}\cup E_{\text{fail}}$, then $\expect[]{\cong_G(\wset^{\gd},e)\cdot \cong_G(\wset^{\bad},e')}\le O(\beta^*\cdot \log^{18}m)$.

We first show <ref>. Assume $e\in E(S_i)$ and $e'\in E(S_j)$, so index $i\in Z_{\text{succ}}$. If $i=j$, then $e'\in E_{\text{succ}}$, so

\[
\begin{split}
\expect{ \cong_G(\wset^{\gd},e)\cdot \cong_G(\wset^{\bad},e')} &\le  \expect{\frac{(\cong_G(\wset^{\gd},e))^2+ (\cong_G(\wset^{\bad},e'))^2}{2}}\\
&\le \expect{\frac{(\cong_G(\wset,e))^2}{2}}+\expect{\frac{(\cong_G(\wset,e'))^2}{2}}
\le O(\log^{36}m)\cdot \beta^*.
\end{split}
\]

We then show <ref>.
Note that, by definition, a path in $\wset^{\gd}$ may not contain an edge in $E_{\text{fail}}$, so $\cong_G(\wset^{\gd},e)=0$, and it follows that $\expect[]{\cong_G(\wset^{\gd},e)\cdot \cong_G(\wset^{\bad},e')}=0$.

We next show <ref>.  Since $e\notin E_{\text{succ}}\cup E_{\text{fail}}$, from <Ref>, $\cong_G(\wset^{\gd},e)\le O(\log^{18}m)$. Therefore, from property <ref> in <Ref>,

\[\expect[]{\cong_G(\wset^{\gd},e)\cdot \cong_G(\wset^{\bad},e')}\le O(\log^{18}m) \cdot \expect[]{\cong_G(\wset^{\bad},e')}\le  O(\beta^*\cdot \log^{36}m).\]

§ PROOFS OMITTED FROM <REF>

§.§ Proof of <Ref>

Consider the $\jset$-contracted instance $\hat I =(\hat G ,\hat \Sigma )$. Since it is a wide instance, there is a high-degree vertex $v^*\in V(\hat G )$, a partition $(E_1,E_2)$ of the edges of $\delta_{\hat G }(v^*)$, such that the edges of $E_1$ appear consequently in the rotation $\oset_{v^*}\in \hat \Sigma $, and a collection $\rset$  of at least $\floor{|E(\hat G)|/\mu^{50}}=\floor{\hat m(I)/\mu^{50}}$ simple edge-disjoint cycles in $\hat G$, such that every cycle $P\in \rset$ contains one edge of $E_1$ and one edge of $E_2$.
Note that we can compute the vertex $v^*$, the partition $(E_1,E_2)$ of the edges of $\delta_{\hat G }(v^*)$, and the set $\rset$ of cycles with the above properties efficiently.

Assume first that $v^*=v_J$. In this case, $\delta_{\hat G}(v^*)=\delta_G(J)$, so $(E_1,E_2)$ is also a partition of the edges of $\delta_G(J)$. From the definition of a $\jset$-contracted instance, the rotation $\oset_{v^*}\in \hat \Sigma$ is identical to the ordering $\oset(J)$ of the edges of  $\delta_{\hat G}(v^*)=\delta_G(J)$. Therefore, edges of $E_1$ appear consecutively in the ordering $\oset(J)$.
The set $\rset$ of cycles in graph $\hat G$ then naturally defines a set $\pset$ of simple paths in graph $G$, where every path $P'\in \pset$ has an edge of $E_1$ as its first edge, an edge of $E_2$ as its last edge, and it is internally disjoint from $J$. We discard arbitrary paths from $\pset$ until $|\pset|=\floor{\frac{\hat m(I)}{\mu^{50}}}$ holds, obtaining the desired set of promising paths.

From now on we assume that $v^*\neq v_J$, that is, $v^*$ is a vertex of $G$. From the definition of a high-degree vertex,
$\deg_G(v)\geq \frac{\hat m(I)}{\mu^4}$. Therefore, there is a collection $\qset$ of at least $\ceil{\frac{2\hat m(I)}{\mu^{50}}}$ edge-disjoint paths in $G$ connecting $v^*$ to vertices of $J$, and we can compute such a collection of paths efficiently using standard Maximum $s$-$t$ Flow. We can assume w.l.o.g. that every path in $\qset$ is internally disjoint from $J$, and we view the paths in $\qset$ as being directed away from $v^*$. We can then compute a partition $(E_1',E_2')$ of the edges of $\delta_G(J)$, such that the edges of $E_1'$ appear consecutively in the ordering $\oset(J)$, and there are two subsets $\qset_1,\qset_2\subseteq \qset$ of paths of cardinality $\floor{\frac{\hat m(I)}{\mu^{50}}}$ each, such that the last edge of every path in $\qset_1$ lies in $E_1'$, and the last edge of every path in $\qset_2$ lies in $E_2'$. By arbitrarily matching the paths in $\qset_1$ to the paths in $\qset_2$ and concatenating the  pairs of matched paths, we obtain a  collection $\pset$ of edge-disjoint paths, each of which has an edge of $E_1'$ as its first edge, an edge of $E_2'$ as its last edge, and is internally disjoint from $J$. We discard paths from $\qset$ until $|\qset|=\floor{\frac{\hat m(I)}{\mu^{50}}}$ holds, obtaining the desired promising set of paths.

§.§ Proof of <Ref>

We denote the input instances by $I=(G,\Sigma)$,  $I_{1}=(G_{1},\Sigma_{1})$, and $I_{2}=(G_{2},\Sigma_{2})$. We denote the core structure by $\jset=(J,\set{b_u}_{u\in V(J)},\rho_J, F^*(\rho_J))$, and the $\jset$-enhancement structure by  $\aset=\set{P,\set{b_u}_{u\in V(J')},\rho'}$, where $J'=J\cup P$.
We let $(\jset_1,\jset_2)$ be the split of the core structure $\jset$ via the enhancement structure $\aset$, and we denote  $\jset_1=(J_1,\set{b_u}_{u\in V(J_1)},\rho_{J_1}, F_1)$ and $\jset_2=(J_2,\set{b_u}_{u\in V(J_2)},\rho_{J_2}, F_2)$.

Let $E^{\del}=E(G)\setminus(E(G_1)\cup E(G_2))$, let $G'=G\setminus E^{\del}$, and let $\Sigma'$ be the rotation system for $G'$ that is induced by $\Sigma$. We first compute a $\jset$-clean solution $\phi'$ to instance $I'=(G',\Sigma')$ of with $\cro(\phi')\leq \cro(\phi_1)+\cro(\phi_2)$, and then insert the edges of $E^{\del}$ into this drawing, to obtain the final solution $\phi$ to instance $I$.

We now describe the construction of the solution $\phi'$ to instance $I'$.
Consider the drawing $\rho'$ of graph $J'$, and the faces $F_1,F_2$ of this drawing that were used to define the split $(\jset_1,\jset_2)$ of the core structure $\jset$.
Recall that the drawing of graph $J_1$ induced by $\rho'$ is precisely $\rho_{J_1}$, and the drawing of graph $J_2$ induced by $\rho'$ is precisely $\rho_{J_2}$.

Consider now the $\jset_1$-clean drawing $\phi_1$ of graph $G_1$ on the sphere. The drawing of $J_1$ induced by $\phi_1$  is identical to $\rho_{J_1}$, and the images of all edges and vertices of $G_1$ are contained in region $F_1$ of this drawing. We plant the drawing $\phi_1$ of $G_1$ into the face $F_1$ of drawing $\rho'$, so that the images of the edges and the vertices of $J_1$ in both drawings coincide, and the images of all vertices and edges of $G_1$ appear in face $F_1$. We similarly plant drawing $\phi_2$ of $G_2$ inside face $F_2$ of $\rho'$, obtaining a solution $\phi'$ to instance $I'$, whose cost is bounded by $\cro(\phi_1)+\cro(\phi_2)$. Since the images of all edges and vertices of $G'$ are contained in region $F^*_{\rho_J}=F_1\cup F_2$, this drawing is $\jset$-clean.

In order to complete the construction of the solution $\phi$ to instance $I$, it remains to “insert” the images of the edges of $E^{\del}$ into $\phi'$.
We do so using <Ref>.
There is, however, one subtlety in using this lemma directly in order to insert the edges of $E^{\del}$ into the drawing $\phi'$: we need to ensure that the drawing remains $\jset$-clean, so the images of the newly inserted edges may not cross the images of the edges of $J$. This is easy to achieve, for example, by first contracting core $J$ into a supernode and modifying the drawing $\phi$ to obtain a drawing of the resulting graph in a natural way. We then insert the edges of $E^{\del}$ into this drawing of the contracted instance using the algorithm from  <Ref>, and then un-contract the supernode $v_J$. We obtain a $\jset$-clean solution $\phi$ to instance $I$, whose number of crossings is bounded by $\cro(\phi_1)+\cro(\phi_2)+|E^{\del}|\cdot |E(G)|$.

§.§ Proof of <Ref>

The proof of <Ref> is similar to the proof of Claim 9.9 in [16].
For all $1\leq i\leq 4k+2$, we denote by $\gamma_i$ the image of path $P_i$ in $\phi$, that is, $\gamma_i$ is the concatenation of the images of the edges of $P_i$. Clearly, all curves in the resulting set $\Gamma=\set{\gamma_1,\ldots,\gamma_{4k+2}}$ connect $\phi(u)$ to $\phi(v)$, and they enter the image of $u$ in $\phi$ in the order of their indices.
Notice that the curves $\gamma_i\in \Gamma$ are not necessarily simple: if a pair of edges lying on path $P_i$ cross at some point $p$, then curve $\gamma_i$ crosses itself at point $p$.
In such a case, point $p$ may not lie on any other curve in $\Gamma$.

Next, we will slightly modify the curves in $\Gamma$ by “nudging” them in the vicinity of their common vertices. In order to do so, we consider every vertex $x\in V(G)\setminus\set{u,v}$ that belongs to at least two paths of $\pset$ one by one.

We now describe an iteration when a vertex $x\in V(G)\setminus\set{u,v}$ is processed.
Let $\pset^x\subseteq \pset$ 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{P_{i_1},\ldots,P_{i_z}}$. Consider the tiny $x$-disc $D(x)=D_{\phi}(x)$. For all $1\leq j\leq z$, denote by $s_j$ and $t_j$ the two points on the curve $\gamma_{i_j}$ that lie on the boundary of disc $D(x)$. 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(x)$. Recall that every pair of resulting curves crosses at most once, and every point in the interior of $D(x)$ may be contained in at most two curves. Moreover, a pair $\sigma_r,\sigma_q$ of such curves may only cross if the two pairs $(s_r,t_r),(s_q,t_q)$ of points on the boundary of $D(x)$ cross. This, in turn, may only happen if paths $P_{i_r},P_{i_q}$ have a transversal intersection at vertex $x$, which is impossible. Therefore, the curves $\sigma_1,\ldots,\sigma_z$ do not cross each other.
For all $1\leq j\leq z$, we modify the curve $\gamma_{i_j}$, by replacing the segment of the curve that is contained in disc $D(x)$ with $\sigma_j$.

Once every vertex $x\in V(G)\setminus\set{u,v}$ is processed, we obtain the final set $\Gamma'=\set{\gamma'_1,\ldots,\gamma'_{4k+2}}$ of curves.
Notice that for any pair $1\leq j<j'\leq 4k+2$ of indices, curves $\gamma'_j,\gamma'_{j'}$ cross if and only if there is a crossing $(e,e')_{p}$ in $\phi$ with $e\in E(P_j)$ and $e'\in E(P_{j'})$.

It is now enough to prove that curves $\gamma'_1$ and $\gamma'_{2k+1}$ do not cross. Assume for contradiction that the two curves cross.  Among all crossing points between these two curves, let $p'$ be the point that is closest to $\phi(u)$ on $\gamma'_1$. Let $\lambda$ be the segment of $\gamma'_1$ from $\phi(u)$ to $p'$, and let $\lambda'$ be defined similarly for $\gamma'_{2k+1}$. We modify curves $\lambda$ and $\lambda'$ to remove all their self-loops, so the curves become simple. Note that curves $\lambda$ and $\lambda'$ both originate at $\phi(u)$ and terminate at $p'$, and they do not cross. Let $\lambda^*$ be the simple closed curve obtained from the union of $\lambda$ and $\lambda'$. Curve $\lambda^*$ partitions the sphere into two internally disjoint discs, that we denote by $D$ and $D'$.
Since the curves $\gamma'_1,\ldots,\gamma'_{4k+2}$ enter the image of $u$ in $\phi$ in the order of their indices, either (i) for all $1< i<2k+1$, the intersection of $\gamma'_i$ with the tiny $u$-disc $D_{\phi}(u)$ lies in $D$, and for all  $2k+1< i\leq 4k+2$, the intersection of $\gamma'_i$ with $D_{\phi}(u)$ lies in $D'$, or (ii) the opposite is true. We assumme without loss of generality  that it is the former.
Note that point $\phi(v)$ must lie in the interior of one of these discs – we assume without loss of generality that it is $D'$.

Consider now some index $1<i<2k+1$.  Recall that the segment of $\gamma'_i$ that is contained in $D_{\phi}(u)$ is contained in $D$, while point $\phi(v)$, that is an endpoint of $\gamma'_i$, lies in the interior of $D'$. Therefore, there must be some point $r$ that lies on $\gamma_i$ and on $\lambda^*$, such that the two curves have a transversal intersection at $r$.
This point may not be $p'$, since curves $\gamma'_1$ and $\gamma'_{2k+1}$ have a crossing at $p'$, and this crossing corresponds to a crossing between an edge of $P_1$ and an edge of $P_{2k+1}$ in $\phi$. Therefore, $\gamma_i'$ has a transversal crossing with either $\lambda$ or $\lambda'$. In the former case, there is a  crossing  between an edge of $P_1$ and an edge of $P_i$, while in the latter case there is a  crossing between an edge of $P_{2k+1}$ and an edge of $P_i$. We conclude that for all $1<i<2k+1$, some edge of $P_i$ must cross an image of an edge of $P_1$ or of $P_{2k+1}$ in $\phi$. Since the edges of $P_1$ participate in at most $k$ crossings, and so do the edges of $P_{2k+1}$, and since we have assumed that an edge of $P_1$ crosses an edge of $P_{2k+1}$, this is impossible.

Let $\gamma$ be a curve on the sphere. If $p$ is a point at which $\gamma$ crosses itself, then we say that $p$ is a self-crossing point of $\gamma$.

Consider now a pair $\gamma,\gamma'$ of curves, such that the number of points that lie on both curves (that is, their crossing points) is finite. Let $p$ be a point lying on both $\gamma$ and $\gamma'$, and assume that $p$ is not a self-crossing point for either of the two curves. Consider the tiny $p$-disc $D$. Let $s,t$ denote the two points of $\gamma$ that lie on the boundary of $D$, and let $s',t'$ denote the two points of $\gamma'$ lying on the boundary of $D$. We say that the crossing of curves $\gamma,\gamma'$ at $p$ is transversal iff points $s,s',t',t'$ appear in this circular order on the boundary of $D$. Otherwise, we say that the crossing is non-transversal. If a crossing of $\gamma$ and $\gamma'$ at point $p$ is non-transversal, we sometimes say that $\gamma$ and $\gamma'$ touch at point $p$. If the crossing is transversal, we may say that $\gamma$ and $\gamma'$ cross but do not touch at point $p$.

We will use the following simple auxiliary claim several times. The proof is  similar to the proof of Claim 9.9 in [16] and is deferred to Section <ref> of Appendix.

Let $\Gamma=\set{\gamma_1,\ldots,\gamma_{4k+2}}$ be a collection of curves on the sphere for which the following hold:

* the number of points $r$ that belong to two or more curves of $\Gamma$ is finite, and so is the number of self-crossing points of each curve;

* all curves in $\Gamma$ originate at point $p$ and terminate at point $q$;

* points $p,q$ may not be inner points on any curve in $\Gamma$;

* curves $\gamma_1,\ldots,\gamma_{4k+2}$ enter point $p$ in the order of their indices;

* if two distinct curves $\gamma_i,\gamma_j\in \Gamma$ have a transversal intersection at point $r$, then $r$ does not belong to any curve in $\Gamma\setminus\set{\gamma_i,\gamma_j}$; and

* if point $p$ is a self-crossing point of some curve $\gamma\in \Gamma$, then $p$ may not lie on another curve of $\Gamma$.

Assume further that curve $\gamma_1$ has at most $k$ transversal crossings with other curves in $\Gamma$, and the same is true for curve $\gamma_{2k+1}$. Then there are no transversal crossings between $\gamma_1$ and $\gamma_{2k+1}$.

§.§ Proof of <Ref>

The proof of <Ref> is similar to the proof of Claim 9.9 in [16].

Assume for contradiction that there is some point $p'$, such that curves $\gamma_1$ and $\gamma_{2k+1}$ have a transversal crossing at $p'$. Among all such points $p'$, we choose the one that is closest to point $p$ on $\gamma_1$. Let $\gamma$ be the segment of $\gamma_1$ from $p$ to $p'$, and let $\gamma'$ be defined similarly for $\gamma_{2k+1}$. We modify curves $\gamma$ and $\gamma'$ to remove all their self-loops, so the curves become simple. Note that curves $\gamma$ and $\gamma'$ both originate at $p$ and terminate at $p'$, and any crossing between these two curves must be non-transversal.

We will further slightly modify the curves $\gamma$ and $\gamma'$, to eliminate all crossing points between them. In order to do so, we iteratively consider every crossing point $r$ between $\gamma$ and $\gamma'$. Let $D(r)$ be a tiny $r$-disc. Denote by $s,t$ the points of $\gamma$ lying on the boundary of $D(r)$, and assume that $s$ appears closer to $p$ than $t$ on $\gamma$. Denote by $s',t'$ the points of $\gamma'$ lying on the boundary of $D(r)$, and assume that $s'$ appears closer to $p$ than $t'$ on $\gamma$. Since the crossing of $\gamma$ and $\gamma'$ at $r$ is non-transversal, we can define two disjoint segments of the boundary of $D(r)$: segemnt $\sigma$ connecting $s$ to $t$, and segment $\sigma'$ connecting $s'$ to $t'$. We  modify curve $\gamma$ by replacing the segment of $\gamma$ between $s$ and $t$ with $\sigma$, and we similarly modify curve $\gamma'$ by replacing the segment of $\gamma'$ between $s'$ and $t'$ with $\sigma'$ (see Figure <ref>).

[The curves $\gamma$ and $\gamma'$ touch at the image of $u$ in $\tilde\phi$.]0.13

[The curves $\hat \gamma,\hat \gamma'$ share only endpoints $p$ and $\tilde\phi(v')$.]
Modifying curves $\gamma,\gamma'$ around their crossing point $r$. could you please update this figure so it matches the notation of this claim? and also delete the green boundary around the blue circles?.

Once every crossing point of $\gamma$ and $\gamma'$ is processed, we let $\gamma^*$ be the simple closed curve obtained from the union of $\gamma$ and $\gamma'$. Note that $\gamma^*$ partitions the sphere into two internally disjoint discs, that we denote by $D$ and $D'$.
Since the curves $\gamma_1,\ldots,\gamma_{4k+2}$ enter point $p$ in the order of their indices, either (i) for all $1< i<2k+1$, the intersection of $\gamma_i$ with the tiny $p$-disc $D(p)$ lies in $D$, and for all  $2k+1< i\leq 4k+2$, the intersection of $\gamma_i$ with $D(p)$ lies in $D'$, or (ii) the opposite is true. We assumme without loss of generality  that it is the former.
Note that point $q$ must lie in the interior of one of these discs – we assume without loss of generality that it is $D'$.

We now prove that for all $1<i<2k+1$, there must be a transversal intersection between $\gamma_i$ and at least one of the curves $\gamma_1,\gamma_{2k+1}$. This will lead to contradiction, since one of the curves $\gamma_1,\gamma_{2k+1}$ must participate in more than $k$ transversal crossings (including the crossing between these two curves). In order to complete the proof of <Ref>, it is now enough to prove the following observation.

For all $1<i<2k+1$, there is a transversal intersection between $\gamma_i$ and at least one of the curves $\gamma_1,\gamma_{2k+1}$.

Fix an index $1<i<2k+1$. Recall that the segment of $\gamma_i$ that is contained in $D(p)$ is contained in $D$, while point $q$, that is an endpoint of $\gamma_i$ lies in the interior of $D'$. Therefore, there must be some point $z$ that lies on $\gamma_i$ and on $\gamma^*$, such that the two curves have a transversal intersection at $z$. We let $z$ be such a point that is closest to $p$ on $\gamma_i$.

Note that $z\neq p$ must hold, since point $p$ may not be an inner point of $\gamma_i$. It is also impossible that $z=p'$, since curves $\gamma_1,\gamma_{2k+1}$ have a transversal intersection at point $p'$, so $p'$ may not lie on $\gamma_i$.

If point $z$ lies on $\gamma_1\cap \gamma$ or $\gamma_{2k+1}\cap \gamma'$, then $\gamma_i$ must have a transversal intersection with $\gamma_1$ or $\gamma_{2k+1}$.

Assume now that this is not the case. Then there must be some point $r$ at which $\gamma_1$ and $\gamma_{2k+1}$ touch, with point $z$ lying on the boundary of disc $D(r)$, either on segment $\sigma$ or on segment $\sigma'$ that we have defined.  Assume w.l.o.g. that $z\in \sigma$.
We will show that $\gamma_i$ and $\gamma_1$ must have a tranversal crossing at point $r$.

Assume for contradiction that this is not the case.
As before, let $s,t$ be the points of $\gamma_1$ lying on the boundary of $D(r)$, with $s$ lying closer to $p$ than $t$ on $\gamma_1$. Similarly, let $s',t'$ the points of $\gamma_{2k+1}$ lying on the boundary of $D(r)$, and assume that $s'$ appears closer to $p$ than $t'$ on $\gamma_{2k+1}$. Recall that $\sigma$ and $\sigma'$ are two disjoint segments of the boundary of $D(R)$, with $\sigma$ connecting $s$ to $t$, and $\sigma'$ connecting $s'$ to $t'$. Since $\gamma_i$ intersects $D(r)$, point $r$ must lie on $\gamma_i$. Let $s''$ and $t''$ denote the two points on $\gamma_i$ that lie on the boundary of $D(r)$. Since $\gamma_i$ contains a point of $\sigma$, and since we have assumed that the crossing of $\gamma_1$ and $\gamma_i$ at $r$ is non-transversal, points $s,t,s'',t''$ must appear on the boundary of $D(r)$ in one of the following two orderings: either $(s,s'',t'',t)$, or $(s,t'',s'',t)$. In other words, both $s'',t''\in \sigma$.

Let $\lambda_1$ be the segment of $\gamma$ from $p$ to $s$. Let $\lambda_2$ be the segment of the boundary of $D(r)$ between $s$ and $s'$ that is internally disjoint from $\sigma$. Let $\lambda_3$ be the segment of $\gamma'$ from $s'$ to $p$, and let $\lambda^*$ be a simple closed curve x

§.§ Proof of <Ref>

Assume for contradiction that there is a vertex $x\in V(G)\setminus V(J)$, and a set $\qset\subseteq \pset^*$ of $\ceil{\frac{512\mu^{13b}\cro(\phi)}{m}}$ good paths that are unlucky with respect to $x$. We denote $\qset=\set{Q_1,\ldots, Q_{\lambda}}$, where ${\lambda}=\ceil{\frac{512\mu^{13b}\cro(\phi)}{m}}$. Let ${\lambda}'=4\cdot  \ceil{{\frac{4\mu^{13b}\cro(\phi)}{m}}}$, so ${\lambda}/{\lambda}'\geq 16$. For all $1\leq i\leq {\lambda}$, we denote by $\hat e_i$ the first edge on path $Q_i$ that is incident to vertex $x$, and by $\hat e_i'$ the edge following $\hat e_i$ on path $Q_i$. We assume that the paths in $\qset$ are indexed so that the edges $\hat e_1,\ldots,\hat e_\lambda$ appear in the rotation $\oset_x\in \Sigma$ in the order of their indices.

Recall that we are given a partition $(E_1,E_2)$ of the edges of $\delta_G(J)$, such that the edges of $E_1$ appear consecutively in the ordering $\oset(J)$, and every path in $\pset$ has an edge of $E_1$ as its first edge, and an edge of $E_2$ as its last edge. From our construction, every path in $\pset^*$, and hence in $\qset$, has an edge of $E_1$ as its first edge, and an edge of $E_2$ as its last edge. Consider the  solution $\phi$ to instance $I$, that is $\jset$-valid. Let $\phi'$ be the drawing that is obtained from $\phi$ after we delete all edges and vertices from it, except for those lying in $J$, and on the paths of $\qset$. Since all paths in $\qset$ are good, there are no crossings in $\phi'$ in which the edges of $J$ are involved. Let $D(J)$ be the disc associated with core $J$ in $\phi$. This disc contains the image of $J$ in $\phi'$ in its interior, and its boundary follows closely the drawing of $J$.
Notice that the image of every path $Q\in \qset$ in $\phi$ must intersect the interior of the region $F^*$, from the definition of a valid core structure (see <Ref>), and since each such path contains edges incident to vertices of $J$. Therefore, the image of every path $Q\in \qset$ in $\phi'$ is contained in the region $F^*$. We can then ensure that no crossing points of $\phi'$ are contained in disc $D(J)$; the only vertices and edges whose images in $\phi'$ are contained in $D(J)$ are the vertices and edges of $J$; and the only other edges whose images intersect $D(J)$ in $\phi'$ are the edges of $\delta_G(J)$ that lie on the paths of $\qset$. Moreover, for each such edge $e$, the intersection of $\phi'(e)$ and $D(J)$ is a simple curve.

We partition the boundary of disc $D(J)$ into two segment $\sigma$ and $\sigma'$, such that $\sigma$ contains all intersection points of the boundary of $D(J)$ with the images of the edges in $E_1$ in $\phi$, while $\sigma'$ contains all intersection points of the boundary of $D(J)$ with the images of the edges in $E_2$ in $\phi$ (see <Ref>).

Partitioning the boundary of disc $D(J)$ into segments $\sigma$ (black) and $\sigma'$ (red).
Edges of $E_1$ are shown in  light blue and edges of $E_2$ are shown in  green.

Let $\phi''$ be the drawing that is obtained from $\phi'$ by deleting the images of the vertices and the edges of $J$ from it, and deleting the segment of the image of every edge $e\in \delta_G(J)$ that is contained in the interior of $D(J)$. We then contract segment $\sigma$ into a point $p$, and segment $\sigma'$ into a point $q$, so that the image of every path $Q\in \qset$ in the resulting drawing connects $p$ to $q$, and for every edge $e\in \bigcup_{Q\in \qset}E(Q)$, the number of crossings in which $e$ participates in $\phi''$ is bounded by the number of crossings in which $e$ participates in $\phi'$.

For all $1\leq i\leq {\lambda}$, we let $R_i$ be the subpath of $Q_i$ from its first vertex to $x$, so $R_i$ contains an edge of $E_1$, and let $\rset=\set{R_i\mid 1\leq i\leq {\lambda}}$.
We also denote $\qset'=\set{Q_{i\cdot {\lambda}'}\mid 1\leq i\leq 16}$, and, for all $1\leq i\leq 16$, we let $\tilde R_i=R_{i\cdot {\lambda}'}$ – the subpath of path $Q_{i\lambda'}$, from its first endpoint to vertex $x$. Let $\tilde \rset=\set{\tilde R_1,\ldots,\tilde R_{16}}$.

Recall that all paths in $\qset$ are good, and so each such path participates in at most $\frac{\cro(\phi)\cdot \mu^{12b}}{m}$ crossings. Since for every pair $P,P'\in \pset^*$ of paths, for every vertex $v\in V(P)\cap V(P')$ with $v\not\in V(J)$, the intersection of $P$ and $P'$ at $v$ is non-transversal with respect to $\Sigma$, the paths in set $\rset$ are non-transversal with respect to $\Sigma$, so are the paths in $\tilde \rset$. Therefore, from <Ref>, for any pair $2\cdot  \ceil{\frac{\cro(\phi)\cdot \mu^{12b}}{m}}< i<j\leq {\lambda}$ of indices with $j-i> 2\cdot\ceil{ \frac{\cro(\phi)\cdot \mu^{12b}}{m}}$, there is no crossing in $\phi''$ between an edge of $R_i$ and an edge of $R_j$. In particular, since  ${\lambda}'=4\cdot  \ceil{{\frac{4\mu^{13b}\cro(\phi)}{m}}}$, there are no crossings in $\phi''$ between pairs of edges lying in distinct paths of $\tilde \rset$.

For $1\leq i\leq 16$, we let $\gamma_i$ be the curve that is obtained from the image of path $\tilde R_i$ in $\phi''$, after removing all self-loops. Consider the resulting collection $\Gamma=\set{\gamma_1,\ldots,\gamma_{16}}$ of curves. All curves in $\Gamma$ originate at point $p$ and terminate at the image of $x$ in $\phi''$. The curves do not cross themselves or each other, and they enter the image of $x$ in the order of their indices. The curves in $\Gamma$ partition the sphere into $16$ regions, that we denote by $\tilde F_1,\ldots,\tilde F_{16}$. Region $\tilde F_1$ has curves $\gamma_1$ and $\gamma_{16}$ as its boundaries, and for $1<i\leq 16$, region $\tilde F_i$ has curves $\gamma_{i-1}$ and $\gamma_i$ as its boundaries. Note that point $q$ must be contained in the interior of one of these regions. We assume without loss of generality that it is $\tilde F_1$ (as otherwise we could re-index the paths of $\qset$ accordingly).

Next, we consider the path $Q^*=Q_{8\lambda'+1}$, and we prove that path $Q^*$ is not unlucky for vertex $x$, reaching a contradiction.

Path $Q^*$ is not unlucky for vertex $x$.

Let $e^*$, $e^{**}$ be the edges of $Q^*$ that are incident to $x$, with $e^*$ lying before $e^{**}$ on the path.
Let  $\hat E_1(x)\subseteq \delta_G(x)$ be the set of edges $\hat e\in \delta_G(x)$, such that $\hat e$ lies between $e^*$ and $e^{**}$ in the rotation $\oset_x\in \Sigma$ (in clock-wise orientation), and $\hat e$ lies on some good path of $\pset^*$. Let $\hat E_2(x)\subseteq \delta_G(x)$ be the set of edges $\hat e\in \delta_G(x)$, such that $\hat e$ lies between $e^{**}$ and $e^{*}$ in the rotation $\oset_x\in \Sigma$ (in clock-wise orientation), and $\hat e$ lies on some good path of $\pset^*$. It is enough to prove that $|\hat E_1(x)|,|\hat E_2(x)|\geq \frac{\cro(\phi)\mu^{13b}}{m}$.

For all $2\leq i\leq 16$, let $\qset_i=\set{Q_j\mid (i-1){\lambda}'<j< i\lambda'}$. Recall that ${\lambda}'=4\cdot  \ceil{\frac{4\mu^{13b}\cro(\phi)}{m}}$, and every path $\tilde R_i\in \tilde \rset$ participates in at most  $ \frac{\cro(\phi)\cdot \mu^{12b}}{m}$  crossings in $\phi''$, since the paths in $\qset$ are good. Therefore, there must be a subset $\qset'_i\subseteq \qset_i$ of at least $2\cdot  \ceil{\frac{4\mu^{13b}\cro(\phi)}{m}}$ paths, such that for every path $Q_j\in \qset'_i$, the image of $Q_j$ in $\phi$ does not cross the curves $\gamma_{i-1}$ and $\gamma_i$. In particular, the image of every path in set $\set{R_j\mid Q_j\in \qset'_i}$ is contained in region $\tilde F_i$ in $\phi''$.

Recall that we have defined a set $\qset'_4\subseteq \qset_4$ of at least $2\cdot \ceil{\frac{4\mu^{13b}\cro(\phi)}{m}}$ paths, where for each path $Q_j\in \qset'_4$, the image of the corresponding path $R_j$ is contained in $\tilde F_{4}$. Recall that, for every path $Q_j\in \qset$, we denoted by
$\hat e_j$ the first edge on path $Q_j$ that is incident to $x$.
We denote by $E^L=\set{\hat e_j\mid Q_j\in \qset'_4}$. Clearly, for every edge $\hat e_j\in E^L$, the image of $\hat e_j$ in $\phi''$ lies in region $\tilde F_4$.

Similarly, we have defined a set
$\qset'_{14}\subseteq \qset_{14}$ of at least $2\cdot \ceil{\frac{4\mu^{13b}\cro(\phi)}{m}}$ paths, where for each path $Q_j\in \qset'_{14}$, the image of the corresponding path $R_j$ is contained in $\tilde F_{14}$.
We denote by $E^R=\set{\hat e_j\mid Q_j\in \qset'_{14}}$. Clearly, for every edge $\hat e_j\in E^R$, the image of $\hat e_j$ in $\phi''$ lies in region $\tilde F_{14}$.

It is also easy to see that the imgage of edge $e^*$ must be contained in $\tilde F_7\cup \tilde F_8\cup \tilde F_9\cup \tilde F_{10}$ (as otherwise path $Q^*$ would need to cross more than $\frac{\cro(\phi)\cdot \mu^{12b}}{m}$ other paths in $\qset$, for example, the paths of $\qset'_7$, or the paths of $\qset'_{10}$).

Lastly, we show that the intersection of the image of edge $e^{**}$ and the tiny $x$-disc $D_{\phi''}(x)$, that we denote by $\sigma(e^{**})$, must be contained in $\tilde F_2\cup \tilde F_1\cup \tilde F_{16}$. Note that, if this is the case, then either (i) $E^L\subseteq \hat E_1(x)$ and $E^R\subseteq \hat E_2(x)$; or (ii) $E^R\subseteq \hat E_1(x)$ and $E^L\subseteq \hat E_2(x)$ hold. In either case, since $|E^R|,|E^L|\geq
2\cdot \ceil{\frac{4\mu^{13b}\cro(\phi)}{m}}$, path $Q^*$ is not unlucky for $x$.

It now remains to prove that $\sigma(e^{**})$ is contained in $\tilde F_2\cup \tilde F_1\cup \tilde F_{16}$. Assume otherwise. From the definition of tiny $x$-disc, $\sigma(e^{**})$ must be contained in some region $\tilde F_i$, for $3\leq i\leq 15$. Recall that we have defined a subset $\qset'_2\subseteq \qset_2$ of at least $2\cdot \ceil{\frac{4\mu^{13b}\cro(\phi)}{m}}$ paths, such that, for every path $Q_j\in \qset'_2$, the image of the corresponding path $R_j\in \rset$ is contained in region $\tilde F_2$. We have also defined a collection $\qset'_{16}\subseteq \qset_{16}$ of at least
$2\cdot \ceil{\frac{4\mu^{13b}\cro(\phi)}{m}}$ paths, such that, for every path $Q_j\in \qset'_{16}$, the image of the corresponding path $R_j\in \rset$ is contained in region $\tilde F_{16}$.

Consider now the segment $\gamma^*$ of the image of path $Q^{*}$ in $\phi''$ from vertex $x$ to point $q$. Since $\sigma(e^{**})$ is contained in $\bigcup_{3\leq i\leq 15}\tilde F_i$, while point $q$ is contained in $\tilde F_1$, curve $\gamma^*$ has to either cross the image of every path in $\set{R_j\mid Q_j\in \qset'_2}$, or it has to cross the image of every path in $\set{R_j\mid Q_j\in \qset'_{16}}$. In either case, since the paths of $\qset$ are non-transversal with respect to $\Sigma$, the edges of path $Q^*$ must participate in at least $2\cdot \ceil{\frac{4\mu^{13b}\cro(\phi)}{m}}$ crossings, contradicting the fact that $Q^*$ is a good path.

§.§ Proof of <Ref>

We start with $\phi'$ being the drawing of graph $G'$ that is induced by $\phi$.
Since bad event $\event_1$ did not happen, drawing $\phi'$ does not contain crossings between edges of $E(P^*)$ and edges of $E(J)$, but it may contain crossings between pairs of edges in $E(P^*)$. We next show how to modify this drawing in order to eliminate all such crossings.
Let $\gamma$ be the image of the path $P^*$ in $\phi'$. Notice that $ \gamma$ is either a closed or an open curve, that may cross itself in a number of points.
Recall that path $P^*$ is internally disjont from $J$, and there are no crossings in $\phi'$ between edges of $P^*$ and edges of $J$. Moreover, from the definition of valid core structure (see <Ref>), and since $\phi$ is a $\jset$-valid drawing of $G$, $\gamma$ must intersect the interior of the region $F^*$. Therefore, $\gamma\subseteq F^*$ must hold. In order to obtain the desired final drawing of graph $G'$, we will only modify the images of the edges and vertices that lie on $P^*$, with the new images contained in $F^*$, so that the resulting drawing of $G'$ is  $\phi$-compatible.

We can partition the curve $\gamma$ into a collection $\Gamma$ of curves, for which the following hold. First, there is a single special curve $\gamma^*\in \Gamma$, which is either a simple closed or a simple open curve. In the former case, $\gamma^*$ contains the image of exactly one vertex of $J$, and in the latter case, the endpoints of $\gamma^*$ are images of two distinct vertices of $J$. All other curves in $\Gamma$ are simple closed curves. For every pair $\gamma_1,\gamma_2\in \Gamma$ of distinct curves, $\gamma_1$ and $\gamma_2$ may share at most one point, and that point must be a crossing point between a pair of edges of $E(P^*)$ in $\phi'$. We ensure that every point of $ \gamma$ lies on at least one curve of $\Gamma$. Since all curves in $\Gamma$ are simple, no curve in $\Gamma$ may cross itself.
We need the following observation.

If neither of the Events $\event_1,\event_3$ happenned, then for every curve $\gamma'\in \Gamma\setminus\set{\gamma^*}$, every vertex $x$ with $\phi'(x)\in \gamma'$ is a light vertex.

Assume otherwise. Let  $\gamma'\in \Gamma\setminus\set{\gamma^*}$ be a curve, and $x$ a vertex with  $\phi'(x)\in \gamma'$, such that $x$ is a heavy vertex. Denote $\phi'(x)$ by $p$, and notice that point $p$ may not lie on any other curves in $\Gamma$ (since every point shared by a pair of curves in $\Gamma$ is a crossing point between a pair of edges from $E(P^*)$.)

Let $D=D_{\phi'}(x)$ be a tiny $x$-disc. For every edge $\hat e$ that is incident to $x$, we denote by $\sigma(\hat e)$ the intersection of $\phi'(\hat e)$ with $D$. Let $e,e'$ be the two edges of $P^*$ that are incident to $x$.
Denote by  $\hat E_1(x)\subseteq \delta_G(x)$ the set of edges $\hat e\in \delta_G(x)$, such that $\hat e$ lies strictly between $e$ and $e'$ in the rotation $\oset_x\in \Sigma$ (in clock-wise orientation), and $\hat e$ lies on some good path of $\pset^*$. Let $\hat E_2(x)\subseteq \delta_G(x)$ be the set of edges $\hat e\in \delta_G(x)$, such that $\hat e$ lies strictly between $e'$ and $e$ in the rotation $\oset_x\in \Sigma$ (in clock-wise orientation), and $\hat e$ lies on some good path of $\pset^*$. Since Event $\event_3$ did not happen, path $P$ may not be unlucky with respect to $x$, so  $|\hat E_1(x)|,|\hat E_2(x)|\geq \frac{\cro(\phi)\mu^{13b}}{m}$ holds.

Curve $\gamma'$ partitions the sphere into two regions, that we denote by $\tilde F$ and $\tilde F'$. Since the curves $\sigma(e),\sigma(e')$ are contained in $\gamma'$, it must be the case that either (i) for every edge $\hat e\in \hat E_1(x)$, $\sigma(\hat e)\subseteq \tilde F$, and for every edge $\hat e\in \hat E_2(x)$, $\sigma(\hat e)\subseteq \tilde F'$, or (ii) the opposite is true. We assume w.l.o.g. that it is the former. Note that, since $\gamma$ is disjoint from the image of the core $J$ in $\phi'$ (except for its endpoints), the image of $J$ in $\phi'$ must be contained either in   the interior of $\tilde F$, or in the interior of $\tilde F'$; we assume w.l.o.g. that it is the former. Consider now some edge $\hat e\in \hat E_2(x)$, and let $\hat P\in \pset^*$ be a path that contains $\hat e$. Observe that $\sigma(\hat e)\subseteq \tilde F'$, while both endpoints of $\hat P$ belong to $J$, whose image lies in the interior of $\tilde F$. Therefore, the image of path $\hat P$ in $\phi'$ must cross the curve $\gamma'$. Let $q$ be a point of $\gamma'$ that lies on the image of $\hat P$, such that the image of $\hat P$ and $\gamma'$ have a transversal intersection at $q$. Note that $q$ may not be the image of a vertex of $G$, since for every vertex $v\in V(G)\setminus V(J)$, for every pair $P,P'\in \pset^*$ of paths containing $v$, the intersection of $P$ and $P'$ at $v$ is non-transversal  with respect to $\Sigma$. Therefore, $q$ is a crossing point between an edge of $\hat P$ and an edge of $P^*$. We conclude that the edges of $P^*$ participate in at least $|\hat E_2(x)|\geq \frac{\cro(\phi)\mu^{13b}}{m}$ crossings. But since we have assumed that Event $\event_1$ did not happen, path $P^*$ must be good, a contradiction. (Note that it is possible that, for some good path $\hat P\in \pset^*$, both edges of $\hat P$ that are incident to $x$ lie in $\hat E_2(x)$. But in that case, the image of $\hat P$ must cross $\gamma$ twice, since both endpoints of $\hat P$ lie in $J$).

Let $p_1,\ldots,p_z$ denote the points on the curve $\gamma^*$ that correspond to crossing points between pairs of edges of $P^*$, and assume that these points appear on $\gamma^*$ in this order. For all $1\leq i\leq z$, let $e_i,e'_i$ be the pair of edges of $P^*$ that cross at point $p_i$, with edge $e_i$ appearing before edge $e'_i$ on path $P^*$.
For all $1\leq i\leq z$, let $Q_i$ be the subpath of path $P^*$ from edge $e_i$ to edge $e'_{i}$, and we denote by $y_i,y'_i$ the second and the penultimate vertices of $Q_i$, respectively. Let $Q'_i$ be the subpath of $Q_i$ connecting $y_i$ to $y'_i$. From <Ref>, if Events $\event_1,\event_3$ did not happen, the every vertex of $Q'_i$ is a light vertex. Since we have deleted all edges of $E'$ from $G$ to obtain graph $G'$, every vertex of $Q'_i$ is incident to exactly two edges in $G'$, and these edges lie on path $P^*$.

We let $D_i$ be a tiny $p_i$-disc in the drawing $\phi'$. Let $s_i$ be the point on the image of edge $e_i$ lying on the boundary of $D_i$, and let $t_i$ be the point on the image of edge $e'_i$ lying on the boundary of $D_i$. We modify the drawing $\phi'$ in order to “straighten” the loop corresponding to the image of the path $Q'_i$, as follows. First, we truncate the images of the edges $e_i$ and $e'_i$, by deleting the segment of $\phi'(e_i)$ between $s_i$ and $\phi'(y_i)$, and similarly deleting the segment of $\phi'(e'_i)$ between $t_i$ and $\phi'(y'_i)$. We then delete the images of all vertices and edges of $Q'_i$ from $\phi'$. We place the new image of $y_i$ at point $s_i$, and the new image of $y'_i$ at point $t_i$. We then add an image of the path $Q'_i$ as a simple curve with endpoints $s_i$ and $t_i$, that is contained in $D_i$, so that the image of $Q'_i$ is contained in $\gamma^*\cap D_i$ (see <Ref>).

[Before: tiny $p_i$-disc $D_i$ is shown in gray, and the original image of path $Q_i$ is shown in blue.]

[After: the new images of vertices $y_i,y'_i$ are shown in brown, and the new image of path $Q_i$ is shown in blue.]0.42

Modifying the image of path $Q_i$.

Clearly, this modification does not increase the number of crossings, and it is local to region $F^*$. Once every point $p_1,\ldots,p_z$ is processed, we obtain the final solution $\phi'$ to instance $I'$ that is compatible with $\phi$, with $\cro(\phi')\leq \cro(\phi)$. Note that our transformation step does not introduce any new crossings. Therefore, if $(e_1,e_2)_p$ is a crossing in drawing $\phi'$, then there is a crossing between edges $e_1$ and $e_2$ at point $p$ in drawing $\phi$.

§.§ Proof of <Ref>

Assume for contradiction that Event $\event$ did not  happen, but $|E''|> \frac{2\cro(\phi)\cdot \mu^{12b}}{m}+|\chi^{\dirty}(\phi)|$. From the Maximum Flow - Minimum Cut Theorem, there is a collection $\qset$ of $\ceil{ \frac{2\cro(\phi)\cdot \mu^{12b}}{m}}+|\chi^{\dirty}(\phi)|$ edge-disjont paths connecting $s$ to $t$ in $H$. Note that every edge in $H$ corresponds to some distinct edge in graph $G$. We do not distinguish between these edges. We  show that, for every path $Q\in \qset$, there is a crossing between an edge of $Q$ and an edge of $E(P^*)\cup E(\thecore)$ in $\phi'$. From <Ref>, and since the number of crossings in which the edges of $\thecore$ may participate is bounded by $|\chi^{\dirty}(\phi)|$, it then follows that the edges of $P^*$ participate in at least $\ceil{ \frac{2\cro(\phi)\cdot \mu^{12b}}{m}}$ crossings in $\phi$. But, since we have assumed that Event $\event_1$ did not happen, path $P^*$ is good, so its edges may particpate in at most $\frac{\cro(\phi)\cdot \mu^{12b}}{m}$ crossings, a contradiction. It now remains to prove that, for every path $Q\in \qset$, there is a crossing between an edge of $Q$ and an edge of $E(P^*)\cup E(\thecore)$ in $\phi'$.

Consider any path $Q\in \qset$. This path naturally defines a path $Q'$ in graph $G$, whose first edge, denoted by $e(Q)$, lies in $\tilde E_1$, and last edge, denoted by  $e'(Q)$, lies in $\tilde E_2$. Then the image of edge $e(Q)$ in $\phi'$ must intersect the interior of region $F_1$, while the image of edge $e'(Q)$ in $\phi'$ must intersect the interior of region $F_2$.  Therefore, the image of the path $Q'$ in $\phi'$ must cross the boundary of the face $F_1$.
Since path $Q'$ is internally disjoint from $V(J')$, the image of some edge on path $Q'$ must cross the image of some edge of $E(J')=E(P^*)\cup E(\thecore)$ in $\phi'$.

§.§ Proof of <Ref>

We start by recalling how the enhancement path $P^*$ was selected. Recall that initial set $\pset^*$ of paths had cardinality
$k\geq \frac{15m}{16\mu^{b}}$.
We denoted by $E^*_1=\set{e_1,\ldots,e_{k}}\subseteq E_1$ the subset of edges that belong to the paths of $\pset^*$, where the edges are indexed so that $e_1,\ldots,e_{k}$ appear consecutively, in the order of their indices in the ordering $\oset(J)$. For all $1\leq j\leq k$, we denote by $P_j\in \pset^*$ the unique path originating at the edge $e_j$. We then selected an index $\floor{k/3}<j^*<\ceil{2k/3}$ uniformly at random, and we let $P^*=P_{j^*}$.
Let $e'\in E_2$ be the edge of $P^*$ lying in $E_2$. Let $\tilde E_1$ be the set of edges lying between $e_{j^*}$ and $e'$ in  $\oset(\thecore)$, and let $\tilde E_2$ be the set of edges lying between $e'$ and $e_{j^*}$  in $\oset(\thecore)$. Then one of the sets $\tilde E_1, \tilde E_2$ of edges must contain all edges in $\set{e_1,\ldots,e_{\floor{k/3}-1}}$, while the other must contain all edges in $\set{e_{\ceil{2k/3}+1},\ldots,e_{k}}$. Therefore, $|\tilde E_1|, |\tilde E_2|\geq \frac {k} 6\geq  \frac{m}{12\mu^{b}}$.

Notice that graph $G_1$ may only contain edges from one of the sets $\tilde  E_1, \tilde E_2$, and so $|E(G_1)|\leq m-\frac{m}{32\mu^{b}}$. Using similar reasoning, $|E(G_2)|\leq  m-\frac{m}{32\mu^{b}}$.

§ PROOFS OMITTED FROM <REF>

§.§ Proof of <Ref>

We use a parameter $\tau'=c\tau\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 $H\setminus T$, with $\bigcup_{C\in \cset}V(C)=V(H)\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, and $|E(C)|\leq m/\tau$. We start with $\cset^I=\emptyset$, and $\cset^A$ containing all connected components of $H\setminus T$. The algorithm terminates once $\cset^A=\emptyset$, and, when this happens, we return $\cset^I$ as the algorithm's outcome.

In order to bound the number of edges in $|\bigcup_{C\in \cset}\delta_H(C)|$, we use edge budgets and vertex budgets, that we define next.

Edge budgets.
Consider a cluster $C\in \cset$ and an edge $e\in \delta_H(C)$. 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}(2|\delta_H(C)|)$. If cluster $C$ is the unique cluster with $e\in \delta_H(C)$, then we set the budget of the edge $e$ to be $B(e)=B_C(e)$. If there are two clusters $C\neq C'\in \cset$ with $e\in \delta_H(C)$ and $e\in \delta_H(C')$, then we set the budget of the edge $e$ to be $B(e)=B_C(e)+B_{C'}(e)$. Lastly, if no cluster $C\in \cset$ with $e\in \delta_H(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\tau'}$, where $c$ is the constant used in the definition of $\tau'$. 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_H(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)= 2\cdot\sum_{e\in E(G)}B(e)+\sum_{v\in V(G)}B(v)$.

Initial budget.
At the beginning of the algorithm, the budget of every vertex $v\in V(H)\setminus T$ is at most:

$$\frac{c\deg_{H\setminus T}(v) \log_{3/2}m\log_2|E(H)|}{8\tau'}\leq \frac{\deg_H(v)}{8\tau},$$

the budget of every edge incident to a vertex in $T$ is at most $\log_{3/2}(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 at most:

\[	\frac{m}{4\tau}+ 2\cdot 16k\log m\leq \frac{m}{\tau},\]

since $k\leq m/(64\tau\log m)$.

We will ensure that, throughout the algorithm, the total budget $B^*$ never increases. Since, from the definition, $B^*\geq \sum_{C\in \cset}|\delta_H(C)|$, this ensures that, when the algorithm terminates,  $\sum_{C\in \cset}|\delta_H(C)|\leq m/\tau$, so the set $\cset^I$ of clusters is a valid output of the algorithm.

Algorithm execution.
As mentioned above, the algorithm starts with $\cset^I=\emptyset$, and $\cset^A$ containing all connected components of $H\setminus T$, with $\cset=\cset^A\cup \cset^I$. 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 a cluster $C\in \cset^A$ is processed.
The algorithm for processing cluster $C$ consists of two parts, that we describe next.

Part 1: bandwidth property.
In this step we either establish that $C$ has the $\alpha'$-bandwidth property, or we partition it into smaller clusters that will replace $C$ in set $\cset^A$.
Recall that an augmentation $C^+$ of cluster $C$ is a graph that is obtained from graph $H$, by subdividing every edge $e\in \delta_H(C)$ with a vertex $t_e$, letting $T(C)=\set{t_e\mid e\in \delta_H(C)}$ be this new set of vertices, and then letting $C^+$ be the subgraph of the resulting graph induced by $V(C)\cup T(C)$. Recall that 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)$-approximate sparsest cut $(X,Y)$ in graph $C^+$ with respect to the set $T(C)$ of terminals. We assume w.l.o.g. that $|X\cap T(C)|\leq |Y\cap T(C)|$.

We consider two cases. First, if $|E(X,Y)|\geq \alpha'\cdot \alphasc(m)\cdot |X\cap T(C)|$, then we are guaranteed that the set $T(C)$ of vertices is $\alpha'$-well-linked in $C^+$, and therefore cluster $C$ has the $\alpha'$-bandwidth property. In this case, we continue to Part 2 of the algorithm. Assume now that  $|E(X,Y)|< \alpha'\cdot \alphasc(m)\cdot |X\cap T(C)|$.

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 (since otherwise we can move vertex $t_e$ to $Y$, only making the cut sparser). Similarly, if $t_e\in Y$, then $v\in Y$ as well.

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_H(C)\cap \delta_H(X')|$ and similarly $|T(C)\cap Y|=|\delta_H(C)\cap \delta_H(Y')|$.

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

Since every cluster that was newly added to $\cset^A$ is contained in $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_H(C)\cap \delta_H(X')|$, and the budget of each such edge increases by at most $\log_{3/2}(2m)\leq 4\log m$, so the total increase in the budget of all edges due to this step is bounded by:

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

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

Consider now some edge $e\in \delta_H(C)\cap \delta_H(X')$. Since we have assumed that $|X\cap T(C)|\leq |Y\cap T(C)|$, it is easy to verify that $|\delta_H(X')|\leq 2|\delta_H(C)|/3$. Therefore, for every edge  $e\in \delta_H(X')\cap \delta_H(C)$, if $C'\subseteq H[X']$ is the new cluster with $e\in \delta(C')$, then:

\[B_{C'}(e)=\log_{3/2}(2|\delta_H(C')|)\leq \log_{3/2}(2|\delta_H(X')|)\leq \log_{3/2}(2|\delta_H(C)|)-1. \]

Therefore, the total decrease in the global budget due to the edges of
$\delta_H(X')\cap \delta_H(C)$ is at least $|\delta_H(C)\cap \delta_H(X')|$. We conclude that overall the budget $B^*$ 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.

If $|E(C)|\leq m/\tau$, then we remove cluster $C$ from $\cset^A$, and add it to the set $\cset^I$ of inactive clusters. It is easy to verify that total budget $B^*$ may not increase as the result of this step. Therefore, we assume from now on that
$|E(C)|>  m/\tau$.

Part 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 size is at most
$O(\alphasc(m))$ times the size of a minimum $3/4$-edge-balanced cut  of $C$. We say that this step is successful if $|E_H(Z,Z')|<|E(C)|/\tau'$. Assume first that the step was successful. Then we remove cluster $C$ from $\cset^A$ and from $\cset$, and add all connected components of  $C[Z],C[Z']$ to $\cset^A$ and to $\cset$ instead. 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_H(Z)\cup \delta_H(Z')$.

We first bound the increase in the budgets of the edges of $\delta_H(Z)\cup \delta_H(Z')$. We consider two cases. The first case happens if $|\delta_H(C)|\leq \frac{8 |E(C)|}{\tau'}$. Since the budget of every edge is always bounded by  $\log_{3/2}(2m)$,
and since $|E_H(Z,Z')|\leq \frac{|E(C)|}{\tau'}$,
so the total increase in the budgets of all edges is bounded by $\frac{10|E(C)|\cdot \log_{3/2}(2m)}{\tau'}$.

Consider now the second case, where $|\delta_H(C)|> \frac{8 |E(C)|}{\tau'}$, and assume without loss of generality that $|\delta_H(Z)|\leq |\delta_H(Z')|$. In this case, since $|E_H(Z,Z')|\leq \frac{|E(C)|}{\tau'}$, $|\delta_H(Z)|\leq |\delta_H(C)|$, so the budgets of the edges in $\delta_H(Z)\cap \delta_H(C)$ may not grow. As before, the budgets of the edges of $E_H(Z,Z')$ may grow by at most $|E_H(Z,Z')|\cdot\log_{3/2}(2m)\leq \frac{|E(C)|\cdot \log_{3/2}(2m)}{\tau'}$. Lastly, for every edge $e\in \delta_H(Z')\cap \delta_H(C)$, the original budget $B_C(e)$ is $\log_{3/2}(2|\delta_H(C)|)$, and, if $C'\subseteq H[Z']$ is the new cluster with $e\in \delta_H(C')$, then the new budget $B_{C'}(e)=
\log_{3/2}(2|\delta_H(C')|)$. Since $|\delta_H(C')|\leq |\delta_H(C)|+|E_H(Z,Z')|$, we get that the increase in the budget of $e$ is bounded by $\log_{3/2}\left (\frac{|\delta_H(C)|+|E_H(Z,Z')|}{|\delta_H(C)|}\right )=\log_{3/2}\left (1+\frac{|E_H(Z,Z')|}{|\delta_H(C)|}\right )$.

Since we have assumed that $|\delta_H(C)|> \frac{8 |E(C)|}{\tau'}$, while $|E_H(Z,Z')|<\frac{|E(C)|}{\tau'}$, we get that $\frac{|E_H(Z,Z')|}{|\delta_H(C)|}<1/2$. Since for all $\eps\in (0,1/2)$, $\ln(1+\eps)\leq \eps$, we get that the increase in the budget of $e$ is bounded by $\frac{|E_H(Z,Z')|}{|\delta_H(C)|\cdot \ln(3/2)}\leq \frac{4|E_H(Z,Z')|}{|\delta_H(C)|}$. Overall, we get that the budget of the edges of $\delta_H(Z')\cap \delta_H(C)$ increases by at most:

\[|\delta_H(Z')\cap \delta_H(C)|\cdot \frac{4|E_H(Z,Z')|}{|\delta_H(C)|}\leq  4|E_H(Z,Z')|\leq \frac{4|E(C)|}{\tau'}.  \]

To summarize, regardless of which of the above two cases happened, the total increase in the budgets of all edges is bounded by $\frac{10|E(C)|\cdot \log_{3/2}(2m)}{\tau'}$. Next, we show that the total decrease in the budgets of the vertices is high enough to compensate for this increase.

Assume without loss of generality that $|E(Z)|\leq |E(Z')|$. From the definition of edge-balanced cut, $|E(Z')|\leq \hat c'|E(C)|$, for some universal constant $\hat c'$. In particular:

\begin{equation}
\sum_{v\in Z}\deg_Z(v)\geq 2(|E(C)|-|E(Z')|-|E(Z,Z')|)\geq 2(1-\hat c'-1/\tau')\cdot |E(C)|. \label{eq: many edges in Z 2}
\end{equation}

On the other hand, from our assumption that $|E(Z)|\leq |E(Z')|$, $\log_{2}(|E(Z)|)\leq \log_{2}(|E(C)|)-1$.
Recall that for every vertex $v\in Z$, its original vertex budget is:
$B(v)=\frac{c\deg_C(v)\log_{3/2}m\cdot \log_{2}(|E(C)|)}{8\tau'}$, and its new budget is:

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

Therefore, for every vertex $v\in Z$, its budget decreases by at least
$\frac{c\deg_Z(v)\log_{3/2}m}{8\tau'}$. Overall, the budget of the vertices in $Z$ decreases by at least:

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

(from Equation <ref>.) Since $\tau'=c\tau\log_{3/2}m\log_2m$, and since we can set $c$ to be a large enough constant, we can ensure that this is at least $\frac{16|E(C)|\cdot \log_{3/2}(2m)}{\tau'}$, so the overall budget in the system does not increase.

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_H(Z,Z')|\geq |E(C)|/\tau'$. Since the size of this cut is within factor $O(\alphasc(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=\Omega\left(\frac{|E(C)|}{\tau'\cdot  \alphasc(m)}\right )$.

Recall that, 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$ must contain a $(3/4)$-edge-balanced cut of value at most $\tilde c\cdot\sqrt{\optcro(C)+\Delta\cdot|E(C)|}$ where $\tilde c$ 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$ must hold.
The latter can only happen if either $\optcro(C)\geq \frac{\rho^2}{2\tilde c^2}$, or $\Delta\geq \frac{\rho^2}{2\tilde c^2\cdot |E(C)|}$. Substituting the value of $\rho=\Omega\left(\frac{|E(C)|}{\tau'\cdot  \alphasc(m)}\right )$,
and recalling that $|E(C)|>m/\tau$, while $\tau'=c\tau\log_{3/2}m\log_2m$,
we conclude that either (i) $\optcro(C)\geq \Omega\left(\frac{|E(C)|^2}{2(\tilde c \tau'\alphasc(m))^2}\right ) \geq \Omega \left( \frac{|E(C)|^2}{ \tau^2\log^5 m} \right ) \geq \Omega \left( \frac{m^2}{ \tau^4\log^5 m} \right )$; or (ii) $\Delta\geq \Omega\left(\frac{|E(C)|}{2(\tilde c\tau'\alphasc(m))^2}\right )\geq  \Omega\left(\frac{m}{\tau^3\log^5m}\right ) $; or (iii) $\Delta\geq \frac{|E(C)|}{2^{40}}\geq \frac{m}{2^{40}\tau} $.
However, since we are guaranteed that $\Delta\leq \frac{m}{c^*\tau^3\log^5m}$ for a large enough constant $c^*$, we can rule out the latter two options, and conclude that $\optcro(H)\geq \optcro(C)\geq \Omega \left( \frac{m^2}{ \tau^4\log^5 m} \right )$.

If Phase 2 is unsuccessful, then we terminate the algorithm and declare that $\optcro(H)\geq  \Omega \left( \frac{|E(H)|^2}{ \tau^4\log^5 m} \right )$.

§.§ Proof of <Ref>

Let $\phi'$ be a solution to instance $I'$.
Throughout the proof, we denote by $D=D_{\phi'}(u^*)$ the tiny $u^*$-disc in drawing $\phi'$.
Recall that
$\delta_{G'}(u^*)=\set{a'_{1,1},\ldots,a'_{1,\hat q_1},a'_{2,1},\ldots,a'_{2,\hat q_2},\ldots,a'_{k,1},\ldots,a'_{k,\hat q_k}}$. Moreover, the edges of $\delta_{G'}(u^*)$ appear in this circular order in the rotation $\oset_{u^*}'\in \Sigma'$.
We assume w.l.o.g. that the orientation of this ordering in $\phi'$ is positive. In other words, the edges are encountered in this order as we traverse the boundary of $D$ so that the interior of $D$ always lies to our left (see, e.g. <Ref>, in which the orientation of the ordering $\oset_{u^*}'$  is positive).

Consider now vertex $u_i$, for some $1\leq i\leq k$. Recall that
the set $\delta_{G'}(u_i)$ of edges is the union of two subsets: set
$A'_i=\set{a'_{i,1},\ldots,a'_{i,\hat q_i}}$ of parallel edges connecting $u_i$ to $u^*$, and set $A_i=\set{a_{i,1},\ldots,a_{i, q_i}}$ of edges corresponding to the edge set $E_i\subseteq E(G)$. Recall that the ordering of the edges in $\delta_{G'}(u_i)$ in the rotation system $\Sigma'$ is: $(a'_{i,1},a'_{i,2},\ldots,a'_{i, \hat q_i}, a_{i, q_i}, a_{i, q_i-1},\ldots, a_{i,1})$. We say that vertex $u_i$ is synchronized with $u^*$, if the orientation of the above ordering in $\phi'$ is negative  (see <Ref>). In other words, if we traverse the boundary of the tiny $u_i$-disc $D_{\phi'}(u_i)$ so that its interior always lies to our right, then we will encounter the edges of $\delta_{G'}(u_i)$ in the order $(a'_{i,1},a'_{i,2},\ldots,a'_{i, \hat q_i}, a_{i, q_i}, a_{i, q_i-1},\ldots, a_{i,1})$.
We need the following simple observation.

If, for some index $1\leq i\leq k$, vertex $u_i$ is not synchronized with $u^*$, then there are at least $\hat q_i^2/8$ crossings $(e,e')$ in $\phi'$ with $e,e'\in A_i'$.

We delete from drawing $\phi'$ all vertices and edges except for vertices $u^*,u_i$ and edges of $A'_i$. For all $1\leq j\leq \hat q_i$, let $s_j$ be the point on the boundary of $D$ that lies on the image of edge $e_{i,j}$, let $t_j$ be the point on the boundary of $D_{\phi'}(u_i)$ that lies on the image of $e_{i,j}$, and let $\gamma_{j}$ be the segment of the image of edge $e_{i,j}$ between $s_j$ and $t_j$.
We assume without loss of generality that $\gamma_j$ does not cross itself; if it does, then we remove self loops until $\gamma_j$ does not cross itself. Denote $\Gamma=\set{\gamma_1,\ldots,\gamma_{\hat q_j}}$ the resulting set of curves.

[The ordering $\oset'_{u^*}$ with positive orientation.
]		0.45

[Vertex $u_i$ is synchronized with $u^*$. Note that edges of $A'_i$ may cross each other but they intersect the boundaries of the discs $D_{\phi'}(u^*)$ and $D_{\phi'}(u_i)$  in the order indicated above.]
An illustration of the positive orientation of $\oset'_{u^*}$ and the oriented rotation of the synchronized vertex $u_i$.

From our assumptions, points $s_1,\ldots,s_{\hat q_i}$ appear in this order on the boundary of $D$, when we traverse it so that the interior of $D$ lies to our left, while points $t_1,\ldots,t_{\hat q_i}$ appear in this order on the boundary of $\eta_i$, when we traverse it so that the interior of the disc is to our left (see <Ref>).

[Points $\set{s_k,t_k}_{1\le k\le  \hat q_i}$ and curves $\gamma_1, \gamma',\gamma''$.

[Curves $\sigma,\gamma'',\sigma', \gamma'$ and disc $\tilde D$.
Illustrations for the proof of <Ref>.

Assume for contradiction that there are fewer than $\hat q_i^2/8$ crossings $(e,e')$ in $\phi'$ with $e,e'\in A_i'$. Then there is some curve $\gamma_j\in \Gamma$, whose image crosses fewer than $\hat q_i/8$ curves in $\Gamma$. Assume w.l.o.g. that this curve is $\gamma_1$.

Let $\Gamma'\subseteq \Gamma\setminus\set{\gamma_1}$ be the set of curves that do not cross $\gamma_1$, so $|\Gamma'|\geq |\Gamma|/2$. We next show that every pair distinct of curves in $\Gamma'$ must cross, leading to a conradiction. 	Indeed, consider any pair $\gamma_x,\gamma_y\in \Gamma'$ of distinct curves in $\Gamma'$, and assume without loss of generality that $x<y$.
Let $\gamma'$ and $\gamma''$ be two curves that follow curve $\gamma_1$ immediately to the left and immediately to the right, respectively. Let $s',s''$ be the endpoints of curves $\gamma'$ and $\gamma''$ lying on the boundary of $D$, respectively, and let $t',t''$ be  be the endpoints of curves $\gamma'$ and $\gamma''$ lying on the boundary of $D_{\phi'}(u_i)$, respectively. Notice that points $s',s''$ partition the boundary of $D$ into two segments, whose endpoints are $s'$ and $s''$; we let $\sigma$ be the segment that does not contain $s_1$. Similarly,  points $t',t''$ partition the boundary of $D_{\phi'}(u_i)$ into two segments, whose endpoints are $t'$ and $t''$; we let $\sigma'$ be the segment that does not contain $t_1$. Let $\lambda$ be the closed curve obtained by concatenating curves $\sigma,\gamma'',\sigma'$, and $\gamma'$ (see <Ref>), and let $\tilde D$ be the disc whose boundary is $\lambda$, that contains the images of the curves $\gamma_x$ and $\gamma_y$. Then points $s_x,s_y,t_x,t_y$ appear on the boundary of $\eta^*$ in this order. Therefore, curves $\gamma_x,\gamma_y$ must cross. We conclude that every pair of curves in $\Gamma'$ must cross, a contradiction.

In order to transform the drawing $\phi'$ of $G'$ into a drawing $\phi$ of $G$, we start by considering the tiny $u^*$-disc $D$ in the drawing $\phi'$. For each edge $a'_{i,j}\in \delta_{G'}(u^*)$, the image of the edge in $\phi'$ intersects the boundary of $D$ at exactly one point, that we denote by $p_{i,j}$.
Recall that, from our assumptions, points $ p_{1,1},\ldots, p_{1, \hat q_1}, p_{2,1},\ldots, p_{2, \hat q_2},\ldots, p_{k,1},\ldots, p_{k, \hat q_k}$ appear in this order on the boundary of $D$, if we traverse it so that the interior of $D$ lies to our left.

For all $1\leq i\leq k$, we define a segment $\sigma_i$ of the boundary of $D$, that contains all points $p_{i,1},\ldots, p_{i,\hat q_i}$. Observe that these segments can be defined so that they are mutually disjoint, and they appear on the boundary of $D$ in their natural order $ \sigma_1,\ldots, \sigma_k$, as we traverse the boundary  of $D$ so that its interior lies to our left. Next, for each $1\leq i\leq k$, we define a disc $D_i$, that is contained in $D$, such that the intersection of the boundary of $D$ and the boundary of $D_i$ is precisely $\sigma_i$, the image of $u^*$ lies outside $D_i$, and all discs $D_1,\ldots,D_k$ are mutually disjoint.
From the above discussion, for all $1\leq i\leq k$, the points $ p_{i,1},\ldots, p_{i,\hat q_i}$ appear in this order on segment $ \sigma_i$ of the boundary of $D_i$, as we traverse this boundary so that the interior of the disc $D_i$ lies to our left (see <Ref>).

The interior of the disc $D$. Segments $\sigma'_1,\ldots,\sigma'_k$ are shown in purple.

Consider now some index $1\leq i\leq k$.
Let $\sigma'_i$ be any segment of non-zero length on the boundary of disc $D_i$, that is disjoint from segment $\sigma_i$.
Let $p'_{i,1},\ldots,p'_{i,q_i}$ be an arbitrary collection of distinct points on $\sigma'_i$, that appear on $\sigma'_i$ in this order, as we traverse the boundary of $D_i$ so that its interior lies to our right  (see <Ref>). We can then define, for each $1\leq i\leq k$ and $1\leq j\leq q_i$, a curve $\zeta_{i,j}$, that originates at the image of $u^*$ and terminates at point $p'_{i,j}$, such that all curves in set $\set{\zeta_{i,j}\mid 1\leq i\leq k, 1\leq j\leq q_i}$ are mutually internally disjoint. From our definitions so far, the circular order in which these curves enter the image of $u^*$ is:
$(\zeta_{1,1},\ldots,\zeta_{1,q_1},\zeta_{2,1},\ldots,\zeta_{2,q_2},\ldots,\zeta_{k,1},\ldots,\zeta_{k,q_k})$ (see <Ref>). For all $1\leq i\leq k$ and $1\leq j\leq q_i$, we will use the curve $\zeta_{i,j}$ in order to draw the edge $e_{i,j}\in E_i$; in fact we will refer to $\zeta_{i,j}$ as the first segment of the drawing of edge $e_{i,j}$. We will later define a second segment of the drawing of this edge, and then eventually stitch the two segments together to complete the drawing of the edge.

Notice that so far, for all $1\leq i\leq k$, we have defined a collection $\set{p'_{i,1}, p'_{i,2},\ldots,p'_{i,q_i},p_{i,\hat q_i},p_{i,\hat q_i-1},\ldots, p_{i,1}}$  of points on the boundary of $D_i$, that appear on it in this order, as we traverse the boundary so that the interior of $D_i$ lies to our right (see <Ref>).
Lastly, for all $1\leq i\leq k$, we define another disc  $D'_i\subseteq D_i$, whose boundary is disjoint from the boundary of $D_i$ (see <Ref>).

Discs $D_i$ and $D'_i$. Segments $\sigma_i$ and $\sigma'_i$ on the boundary of $D_i$ are shown in red and purple, respectively.

[Discs $D_i$ and $D'_i$. Segments $\sigma_i$ and $\sigma'_i$ on the boundary of $D_i$ are shown in red and purle, respectively. There is again a mistake in indexing the $p'_{i,j}$ points. Last index should be $p_{i,q_i}$, not $p_{i,\hat q_i}$. Also, if it's not too much trouble, the $\ldots$ signs should appear outside of the disc $D_i$ in both cases, otherwise it's not clear what it is that they refer to]0.2

[Schematic view of images of edges of $A'_i$ and $A_i$ and relevant points on the boundary of $D$ and $\tilde D_i$. Images of edges of $A_i$ are shown in red. Image of each edge $a_{i,j}\in A_i$ is shown in purple, with segments $\zeta_{i,j}$ dotted.  can you please rename $z_{i,j}$ points as $z'_j$ (note: no $i$-index anymore), add the $z_j$ points to the boundary of $D$? (see Figure 10 in the updated figures file). Also, the points $p'_{i,j}$ should become $p''_{i,j}$, and the index of the last point should be $p''_{i,q_i}$, not $\hat q_i$. Can you also move the placement of $\ldots$ signs to correct locations? The pink one should be outside the disc and before the last $z$-vertex, and for the green ones the sign is missing. If you could also move $p_{i,2}$ outside of the disc and move blue $\ldots$ outside of the disc it would be great.  ]
An illustration of discs and curves used in <Ref>.	can you please split the figure below into two separate figures. I think this will improve readability, things are confusing enough without putting these two together. Also the caption of the joint figure does not make sense.

In the remainder of the algorithm, we process each index $1\leq i\leq k$ one by one. We let $G_0=G'$, and for all $1\leq i\leq k$, we let $G_i$ be the graph obtained from $G'$ by contracting vertices $u_1,\ldots,u_i$ into the vertex $u^*$; we delete self-loops but keep parallel edges. Note that graph $G_k$ is identical to graph $G$, except that some of the edges of $G$ are subdivided in $G_k$. Therefore, a drawing of graph $G_k$ immediately gives a drawing of graph $G$. For each $1\leq i\leq k$, the input to the $i$th iteration is a drawing $\phi_{i-1}$ of graph $G_{i-1}$, in which, for all $1\leq i'\leq i-1$, all vertices and edges of $X_{i'}$ are drawn inside the disc $D'_{i'}$. The goal of the $i$th iteration is to produce a drawing $\phi_i$ of graph $G_i$, in which,  for all $1\leq i'\leq i$, all vertices and edges of $X_{i'}$ are drawn inside the disc $D'_i$. The final drawing $\phi_k$ of graph $G_k$, obtained at the end of the last iteration immediately provides a drawing of graph $G$. Let $\phi_0=\phi'$ be the given drawing of graph $G_0$, that is a solution to instance $I'$ of . For all $1\leq i\leq k$, we denote by $\cro_i$ the total number of crossings in $\phi_0$, in which edges of $E(X'_i)\cup A'_i\cup \hat A_i$ participate. Clearly, $\sum_{i=1}^k\cro_i\leq 2\cro(\phi)$.
We will ensure that the following invariants hold, for all $1\leq i\leq k$:

* over the course of iteration $i$, we may only change the images of the vertices and edges of $X'_i$, and the images of the edges of $\delta_G(X_i)\cup \delta_{G'}(X'_i)$; the images of the remaining edges and vertices of the graph remain unchanged;

* for every edge $e\in E(G_{i-1})\setminus (E(X'_i)\cup A'_i\cup\hat A_i)$, the number of crossings in which edge $e$ participates in $\phi_i$ is bounded by the number of crossings in which edge $e$ participated in $\phi_{i-1}$; and

* $\cro(\phi_i)\leq \cro(\phi)+O(\cro_i)$.

From the above invariants, it is immediate to see that the final drawing $\phi_k$ of graph $G_k$ has at most $O(\cro(\phi))$ crossings.

In order to execute the $i$th iterations, we use the two sets $\qset_i,\qset'_i$ of paths that we have defined, in order to define two sets $\Gamma_i,\Gamma'_i$ of curves, that will serve as “guiding curves” for the transformation of the drawing $\phi_{i-1}$. We also use the current drawing $\phi_{i-1}$ in order to compute a “nice” drawing $\psi_i$ of graph $X_i$, together with a partial drawing of edges incident to vertices of $X_i$ in $G$. We then “plant” this drawing inside the disc $D'_i$, and then complete the drawings of the edges of $\delta_G(X_i)$.

The input to the first iteration is the initial drawing $\phi_0=\phi'$ of graph $G_0=G'$ on the sphere.
We now fix a single index $1\leq i\leq k$, and describe the iteration in which index $i$ is processed. Our starting point is a drawing $\phi_{i-1}$ of graph $G_{i-1}$.
Note that, from Invariant <ref>, the total number of crossings in which the edges of $E(X'_i)\cup A'_i\cup \hat A_i$ participate in drawing $\phi_{i-1}$ is at most $\cro_i$. We will use this fact later.

The algorithm for processing index $i$ consists of three stages. In the first stage, we use the set $\qset_i$ of paths in order to define the first set $\Gamma_i$, of “guiding” curves. In the second stage, we use the set $\qset'_i$ of paths in order to define the second set $\Gamma'_i$ of “guiding” curves, and we compute a drawing $\psi_i$ of $X_i$, together with a partial drawing of edges of $\delta_{G}(X_i)$. In the third and the final stage stage, we “plant” this drawing inside the disc $D'_i$, and complete the drawing $\phi_i$. We now describe each of the three stages in turn.

§.§.§ Stage 1: First Set of Guiding Curves, and Partial Drawing of Edges of $\hat E_i$

Recall that we have defined a collection $\qset_i=\set{Q(e)\mid e\in \hat E_i}$ of edge-disjoint paths in graph $G$, where for each edge $e\in \hat E_i$, path $Q(e)$ has $e$ as its first edge and $u^*$ as its last vertex, and all its inner vertices are contained in $X_i$. From the definition of graph $X'_i$, and from the fact that there are $|\hat E_i|=\hat q_i$ edges connecting $u_i$ to $u^*$ in $G'$ (the edges of $A'_i$), it is immediate to see that there must be a set $\hat \qset_i=\set{\hat Q(\hat a)\mid \hat a\in \hat A_i}$ of edge-disjoint paths in graph $G'_{i-1}$, where for each edge $\hat a\in \hat A_i$, path $\hat Q(\hat a)$ contains $\hat a$ as its first edge and terminates at vertex $u^*$, such that all inner vertices of $\hat Q(\hat a)$ are contained in $X'_i$.

We apply the algorithm from <Ref> to perform a type-2 uncrossing of the paths in $\hat \qset_i$. The input to this algorithm is graph $G_{i-1}$ and its drawing $\phi_{i-1}$ on the sphere, and the set $\hat \qset_i$ of paths, which we view as being directed away from $u^*$. Let $\Gamma_i=\set{\gamma(\hat a)\mid \hat a\in \hat A_i}$ denote the set of curves that the algorithm outputs, that are aligned with the graph $\bigcup_{Q\in \hat Q_i}Q$. For each edge $\hat a\in \hat A_i$, if $y(\hat a)$ is the endpoint of $\hat a$ that does not lie in $X'_i$, then curve $\gamma(\hat a)$ originates at the image of $u^*$ and terminates at the image of $y(\hat a)$. Moreover, the curves in set $\Gamma_i$ do not cross each other.

Recall that, for every path $\hat Q\in \hat \qset_i$, the first edge of $\hat Q$ (the edge incident to $u^*$) must be an edge of $A'_i$. From the definition of aligned curves, the theorem guarantees that, for every edge $a'_i\in A'_i$, there is a unique curve $\gamma(\hat a)\in \Gamma_i$ that contains the segment of the image of $a'_i$ that lies inside disc $D$. In particular, for all $1\leq j\leq \hat q_i$, there is a unique curve $\gamma(\hat a)\in \Gamma_i$ containing the point $p_{i,j}$ on the boundary of $D_i$. We denote $\hat A_i=\set{\hat a_{i,1},\ldots,\hat a_{i,\hat q_i}}$, where for all $1\leq j\leq \hat q_i$, edge $\hat a_{i,j}$ is the unique edge whose corresponding curve $\gamma(\hat a_{i,j})$ contains the point $p_{i,j}$. From the definition of aligned curves, each such curve $\gamma(\hat e_{i,j})$ intersects the boundary of $D$ at a unique point - point $p_{i,j}$. For all $1\leq j\leq \hat q_i$, we denote $\hat a_{i,j}=(\hat x_{i,j},\hat y_{i,j})$, where $x_{i,j}\in X'_i$. For all $1\leq j\leq \hat q_j$, we let $\hat \zeta_{i,j}$ be the segment of curve $\gamma(\hat a_{i,j})$ from the image of $y_{i,j}$ to point $p_{i,j}$ on the boundary of disc $D$. We denote the resulting set of curves by $\hat Z_{i}=\set{\hat \zeta_{i,j}\mid 1\leq j\leq \hat q_i}$.

Consider now the drawing $\phi_{i-1}$ of graph $G_{i-1}$. We slightly modify this drawing, as follows. First, we delete from $\phi_{i-1}$ the images of all vertices of $X'_i$ and all edges of $E(X'_i)\cup \hat A_i\cup A'_i$. Next, we add to this drawing the set $Z_i=\set{\zeta_{i,j}\mid 1\leq j\leq q}$ of curves; recall that for all $1\leq j\leq q$, curve $\zeta_{i,j}$ is contained in disc $D$, is internally disjoint from disc $D_i$, and connects the image of $u^*$ to point $p'_{i,j}$ on the boundary of disc $D_i$ (see <Ref>). Recall that we called curve $\zeta_{i,j}$ the first segment in the drawing of edge $e_{i,j}$. Additionally, we add to the current drawing the set $\hat Z_i=\set{\hat \zeta_{i,j}\mid 1\leq j\leq \hat q_i}$ of curves. Recall that, for all $1\leq j\leq \hat q_i$, curve $\hat \zeta_{i,j}$ is internally disjoint from disc $D$, and it connects the image of vertex $y_{i,j}$ (the endpoint of edge $\hat a_{i,j}\in \hat A_i$ lying outside $X'_i$) to point $p_{i,j}$ on the boundary of disc $D_i$ (see also <Ref>). We refer to curve $\hat \zeta_{i,j}$ as the first segment in the drawing of edge $\hat a_{i,j}$.
We denote the resulting drawing by $\phi'_{i-1}$. Note that, since the curves in $\Gamma_i$ are aligned with the graph $\bigcup_{Q\in \hat \qset_i}Q$, and, since the paths in set $\hat \qset_i$ are edge-disjoint, the total number of crossings in drawing $\phi'_{i-1}$ (including crossings between curves representing edges that were not erased and curves in sets $Z_{i}$ and $\hat Z_i$) is bounded by $\cro(\phi_{i-1})$. Moreover, for every edge $e\in E(G_{i-1})\setminus (E(X'_i)\cup A_i'\cup \hat A_i$), the number of crossings in which $e$ participates in $\phi'_{i-1}$ is bounded by the number of crossings in which $e$ participates in $\phi_{i-1}$, and the image of $e$ is disjoint from disc $D_i$.
This completes the first stage of the algorithm.

§.§.§ Stage 2: Second Set of Guiding Curves and Drawing of $X_i$

In this stage we consider again drawing $\phi_{i-1}$ of graph $G_{i-1}$. We will start by defining another set $\Gamma'_i$ of guiding curves in this graph (which we will eventually use in order to draw a second segment of each edge in $\hat A_i$). We then exploit the drawing $\phi_{i-1}$ and the curves in $\Gamma'_i$ in order to compute a drawing $\psi_i$ of graph $X_i$, and, for each edge $e\in \delta_{G}(X_i)$, a drawing of a segment of $e$ that is incident to its endpoint that lies in $X_i$. We will also define a new collection $\Gamma^*_i$ of curves, that will be useful for us in Stage 3.

Set $\Gamma'_i$ of guiding curves.
We start by defining a set $\Gamma'_i$ of guiding curves. Consider the drawing $\phi_{i-1}$ of $G_{i-1}$.

Recall that petal $X_i$ is routable in graph $G$. Therefore, there is a set $\qset'_i$ of paths routing the edges of $\hat E_i$ to vertex $u^*$ in graph $G$, such that the paths in $\qset'_i$ are internally disjoint from $X_i$, and cause congestion at most $3000$.
Consider any path $Q=Q(\hat e)\in \qset'_i$, whose first edge is $\hat e \in \hat E_i$. Recall that we have subdivided each such edge $\hat e\in \hat E_i$ with a vertex in graph $G'$. Let $e',e''$ denote the two edges that we obtained from subdividing edge $\hat e$, and assume that $e'\in \hat A_i$. We then replace edge $\hat e$ with $\hat e''$ on path $Q$. Assume now that the last edge of $Q$ is $e_{i',j}\in E_{i'}$. Since path $Q$ is internally disjoint from $X_i$, $i'\neq i$ must hold. If $i'>i$, then, by replacing edge $e_{i',j}$ with the corresponding edge $a_{i',j}$, we obtain a new path $Q'$ in graph $G_{i-1}$, whose first vertex is an endpoint of an edge of $\hat A_i$, and last vertex is $u_{i'}$. If $i'<i$, then we set $Q'=Q$. Let $\qset''_i=\set{Q'\mid Q\in \qset'_i}$ be the resulting set of paths in graph $G_{i-1}$.

Consider now any vertex $u_{i'}$, for $i< i'\leq k$. Every path $Q'\in \qset''_i$ that terminates at $u_{i'}$ must contain an edge of $\hat A_{i'}$. Therefore, the number of paths in $\qset''_i$ terminating at $u_{i'}$ is bounded by $3000\hat q_{i'}$. Since, for all $1\leq i''\leq k$, $|A'_{i''}|=\hat q_{i''}$, we can then extend all such paths, using the edges of $A'_{i'}$, to ensure that they terminate at vertex $u^*$, such that  all such paths cause congestion at most $3000$ in $G_{i-1}$. Therefore, we have established that there is a set $\qset'''_i=\set{Q'''_{i,j} \mid 1\leq j\leq \hat q_i}$ of paths in graph $G_{i-1}$ that cause congestion at most $3000$, such that, for all $1\leq j\leq \hat q_i$, path $Q'''_{i,j}$ originates at vertex $\hat y_{i,j}$ (the endpoint of the edge $\hat a_{i,j}\in \hat A_i$ that does not lie in $X'_i$), terminates at vertex $u^*$, and is internally disjoint from $X'_i$.

In order to construct the set $\Gamma'_i$ of curves, we consider a graph $H$, that is obtained as follows. We start with $H=G_{i-1}$. We delete from this graph all edges $e\in E(G_{i-1})\setminus (E(X'_i)\cup \hat A_i\cup A'_i)$ that do not participate in the paths of $\qset'''_i$. For all remaining edges  $e\in E(G_{i-1})\setminus (E(X'_i)\cup \hat A_i\cup A'_i)$, we replace $e$ with  $\cong_{G_{i-1}}(\qset'''_i,e)$ parallel copies. Lastly, we delete all isolated vertices from the resulting graph. Note that drawing $\phi_{i-1}$ of graph $G_{i-1}$ naturally defines a drawing $\phi'$ of graph $H$: after deleting all edges of $E(G_{i-1})\setminus E(H)$ and all vertices of $V(G_{i-1})\setminus V(H)$ from the drawing, for every remaining edge $e\in E(H)\setminus (E(X'_i)\cup \hat A_i\cup A'_i)$, we draw the parallel copies of $e$ along the original image of edge $e$ in $\phi_{i-1}$.
We can now use the set $\qset'''_i$ paths in graph $G_{i-1}$ in order to define a set $\hat \qset'_i=\set{\hat Q'_{i,j}\mid 1\leq j\leq \hat q_i}$ of edge-disjoint paths in graph $H$, where for all $1\leq j\leq \hat q_i$, path $\hat Q_{i,j}$ originates at vertex $\hat y_{i,j}$, terminates at vertex $u^*$, and is disjoint from $X_i'$.

We use the algorithm from <Ref> in order to compute a type-2 uncrossing of the paths in $\hat \qset'_i$. Specifically, the algorithm is applied to graph $H$, its drawing $\phi'$, and the set $\hat \qset'_i$ of edge-disjoint paths.
The algorithm returns a set $\hat \Gamma=\set{\hat \gamma_{i,j}\mid 1\leq j\leq \hat q_i}$
of internally disjoint curves, where, for all $1\leq j\leq \hat q_i$, curve $\hat \gamma_{i,j}$ connects the image of $\hat y_j$ to the image of vertex $u^*$ in drawing $\phi'$, and all curves in $\hat \Gamma$ are aligned with the graph $\bigcup_{\hat Q\in \hat \qset'_i}Q$. We will also consider the curves in set $\hat \Gamma$ in the drawing $\phi_{i-1}$ of $G_{i-1}$. As before, each curve $\hat \gamma_{i,j}$ connects the image of $\hat y_{i,j}$ to the image of vertex $u^*$ in drawing $\phi_{i-1}$.
Since the paths in the original set $\qset'$ caused congestion at most $3000$, it is immediate to verify that the number of crossings between the images of the edges of $E(X'_i)\cup A'_i\cup \hat A_i$ in $\phi_{i-1}$ and the  curves of $\hat \Gamma$ is at most $3000\cdot\cro_i$.

Since the curves in $\hat \Gamma$ are aligned with the graph $\bigcup_{\hat Q\in \hat \qset'_i}Q$, each curve $\hat \gamma_{i,j}\in \hat \Gamma$ intersects the boundary of the tiny $u^*$-disc $D$ in a single point, that we denote by $z_j$. Sine the paths in $\hat \qset'$ may not use the edges of $A'_i$, we are guaranteed that each such point $z_j$ may not lie on the segment $\sigma_i$ (the segment containing the points $p_{i,1},\ldots,p_{i,\hat q_i}$; point $p_{i,j'}$ is the intersection point of the image of edge $a'_{i,j'}$ and the boundary of $D$, see <Ref>).
For convenience, we re-index the points in set $\set{z_j}_{1\leq j\leq \hat q_i}$, so that points $z_1,z_2,\ldots,z_{\hat q_i},p_{i,\hat q_i},\ldots,p_{i,1}$ appear on the boundary of $D$ in this order. For each $1\leq j\leq \hat q_i$, we denote by $\ell(j)$ the unique index such that curve $\hat \gamma_{i,j}$ contains the point $z_{\ell(j)}$.  For all $1\leq j\leq \hat q_i$, we let $\gamma'_{i,j}$ be the segment of curve $\hat \gamma_{i,j}$ from the image of vertex $\hat y_{i,j}$ to point $z_{\ell(j)}$. We then set $\Gamma'_i=\set{\gamma'_{i,j}\mid 1\leq j\leq \hat q_i}$. From the above discussion, the total number of crossings
between the images of the edges of $E(X'_i)\cup A'_i\cup \hat A_i$ in $\phi_{i-1}$ and the  curves of $\Gamma'_i$ is at most $3000\cdot\cro_i$.

the set of curves that the algorithm outuputs, where $\gamma'_{i,j}$ is the curve that originates at vertex $\hat v_{i,j}$. Note that each curve in $\Gamma'_i$ terminates at the image of vertex $u_i$, and the curves in $\Gamma'_i$ are disjoint from each other.
Since the curves in $\Gamma'_i$ are aligned with graph $\bigcup_{Q\in \qset''_i}Q$, the  total number of crossings between the curves in $\Gamma'_i$ and the edges of $X'_i$ is bounded by $100\chi_i$. Since the curves in $\Gamma_i$
that are aligned with the graph $\bigcup_{Q\in \hat Q_i}Q$, the total number of crossings between the curves of $\Gamma_i$ and the curves of $\Gamma'_i$ is bounded by $\chi_i+\cro(\hat E_i)$, where $\chi'_i$ is the number of crossings between edges of $\hat E_i$ in drawing $\phi_{i-1}$.

Since the curves in $\Gamma'_i$ are aligned with graph $\bigcup_{Q\in \qset''_i}Q$, for every edge $a'_{i,j}\in A'_i$, there is a unique curve $\gamma'_{i,j'}\in \Gamma'_i$ that contains the segment of the image of $a'_{i,j}$ that lies in the disc $\tilde D_i$. In particular, it contains point $z_{i,j}$ on the boundary of disc $\tilde D_i$. Note however that it is possible that $j\neq j'$, that is, the curve connects the image of vertex $v_{i,j'}$ to point $z_{i,j}$, where $j\neq j'$. For convenience, we will denote point $z_{i,j}$ by $s_{j'}$. For all $1\leq j\leq \hat q_i$, we then let $\hat \zeta'_{i,j}$ be obtained by concatenating the image of the edge $(\hat x_{i,j},\hat v_{i,j})$ with the segment of the curve $\gamma'_{i,j}$ connecting the image of $\hat v_{i,j}$ to point $s_j$. We then set $\hat Z'_i=\set{\hat \zeta'_{i,j}\mid 1\leq j\leq \hat q_i}$.

Set $\Gamma^*_i$ of Auxiliary curves.
We need to define another set of curves, that we will use in Stage 3. Recall that we have defined a set of points $z_1,z_2,\ldots,z_{\hat q_i},p_{i,\hat q_i},\ldots,p_{i,1}$ that appear on the boundary of disc $D$ in this order. We can consider two orderings of elements of $\set{1,\ldots,\hat q_i}$: the first ordering is their natural ordering, while the second ordering is $\ell(1),\ell(2),\ldots,\ell(\hat q_i)$ – ordering that is defined by the curves in $\Gamma'_i$. In Stage 3 of our algorithm, we will need to show that the distance between these two orderings is small, in order to combine different segments of the drawings of the edges of $A_i$ to complete their drawing. The set $\Gamma^*_i$ of curves, that we define in the next observation, will be used in order to do so.

There is an efficient algorithm to construct a collection $\Gamma^*_i=\set{\gamma^*_{i,j}\mid 1\leq j\leq \hat q_i}$ of curves, such that, for all $1\leq j\leq \hat q_i$, curve $\gamma^*_{i,j}$ connects point $p_{i,j}$ on the boundary of disc $D$ to point $z_{\ell(j)}$, and it is internally disjoint from disc $D$. Moreover, the total number of crossings between the curves of $\Gamma^*_i$ is $O(\cro_i)$.

Consider an index $1\leq j\leq \hat q_i$. Recall that we have defined a curve $\hat \zeta_{i,j}$, which is a sub-curve of some curve of $\Gamma_i$, connecting point $p_{i,j}$ to the image of vertex $\hat y_{i,j}$ in $\phi_{i-1}$. We concatenate this curve with curve $\gamma'_{i,j}\in \Gamma'_i$, connecting the image of vertex $\hat y_{i,j}$ to point $z_{\ell(j)}$, obtaining the curve $\gamma^*_{i,j}$, that connects $p_{i,j}$ to $z_{\ell(j)}$. From the construction of curves in $\Gamma_i$ and $\Gamma'_i$, and the alignemnt properties of each such curve, we are guaranteed that each resulting curve is internally disjoint from disc $D$.

In order to bound the number of crossings between the curves of $\Gamma^*$, recall that the total number of crossings
between the images of the edges of $E(X'_i)\cup A'_i\cup \hat A_i$ in $\phi_{i-1}$ and the  curves of $\Gamma'_i$ is at most $3000\cro_i$. Since the curves of $\Gamma_i$ are aligned with graph $\bigcup_{Q\in \hat \qset_i}Q$, and the paths of $\qset_i$ are edge-disjoint and contained in $X'_i\cup A'_i\cup \hat A_i$, we get that the total number of crossings between the curves of $\Gamma^*_i$ is $O(\cro_i)$.

Partial drawing of edges of $\hat A_i$.
Next, we define a collection $\hat Z_i'=\set{\hat \zeta'_{i,j}\mid 1\leq j\leq \hat q_i}$, of curves, that we will use in order to obtain partial drawing of the edges of $\hat A_i$. For all $1\leq j\leq \hat q_i$, curve $\hat \zeta'_{i,j}$ will connect the image of vertex $\hat x_{i,j}$ (the endpoint of edge $\hat a_{i,j}$ lying in $X'_i$) to a point on the boundary of the tiny $u_i$-disc in $\phi_{i-1}$. We will then view curve $\hat \zeta'_{i,j}$ as the second segment in the drawing of edge $\hat a_{i,j}$, and we will add all such curves to the drawing $\psi_i$ that we compute in this stage.

In order to compute the set $\hat Z_i'$ of curves, we will utilize the cuves of $\Gamma'_i$, the images of the edges of $\hat A_i\cup A'_i$ in drawing $\phi_{i-1}$, and another set of curves that we define next.

Recall that we have defined a set $z_1,z_2,\ldots,z_{\hat q_i},p_{i,\hat q_i},\ldots,p_{i,1}$ of points on the boundary of disc $D$, that appear on the boundary of $D$ in this order. We define, for all $1\leq j\leq \hat q_i$ a curve $\rho_j$, connecting $z_j$ to $p_{i,j}$, such that all curves in $\set{\rho_1,\ldots,\rho_{\hat q_i}}$ are contained in disc $D$ and are disjoint from each other (see <Ref>).

An illustration of curves $\rho_1,\ldots,\rho_{\hat q_i}$ in disc $D$.

We denote by $\tilde D_i=D_{\phi_{i-1}}(u_i)$ the tiny $u_i$-disc in $\phi_{i-1}$. Consider the images of the edges in set $A'_i=\set{a'_{i,j}\mid 1\leq j\leq \hat q_i}$ in drawing $\phi_{i-1}$ (these are the parallel edges connecting $u^*$ to $u_i$). From our definition, for all $1\leq j\leq \hat q_i$, point $p_{i,j}$ is the unique point on the boundary of disc $D$ that lies on the image of edge $a'_{i,j}$. We denote the unique point of the image of $a'_{i,j}$ lying on the boundary of disc $\tilde D_i$ by $z'_{j}$. Recall that, from our assumptions, points $p_{i,1},\ldots,p_{i,\hat q_i},z_{\hat q_i},\ldots,z_1$ appear in this order on the boundary of $D$, as we traverse it so that the interior of the disc lies to our left (see <Ref>). If $u_i$ is synchronized with $u^*$, then, from the definition of the rotation $\oset'_{u_i}\in \Sigma'$, points $z'_{1},\ldots,z'_{\hat q_i}$ appear in this order on the boundary of disc $\tilde D_i$, as we traverse it so that the interior of the disc lies to our right; if $u_i$ is not synchronized with $u^*$, then this order is reversed (see  <Ref>).

Schematic view of images of edges of $A'_i$ and $A_i$ and relevant points on the boundary of $D$ and $\tilde D_i$. Images of edges of $A_i$ are shown in red. Image of each edge $a_{i,j}\in A_i$ is shown in purple, with segments $\zeta_{i,j}$ dotted.

We are now ready to define the curves of $\hat Z_i'$. Consider some index $1\leq j\leq \hat q_i$. Curve $\hat \zeta'_{i,j}$ is the concatenation of four curves: (i) the image of the edge $\hat a_i=(\hat x_{i,j},\hat y_{i,j})$ in $\phi_{i-1}$; (ii) curve $\gamma'_{i,j}\in \Gamma'_i$ (that connects the image of $\hat y_{i,j}$ to point $z_\ell(j)$ on the boundary of $D$); (iii) curve $\rho_j$ (that connects $z_\ell(j)$ to $p_{i,j}$ and is contained in $D$); and (iv) a segment of the image of the edge $a'_{i,j}$ in $\phi_{i-1}$, from point $p_{i,j}$ on the boundary of disc $D$, to point $z'_{\ell'(j)}$ on the boundary of disc $\tilde D_i$, where $1\leq \ell'(j)\leq \hat q_i$. Note that, if $u_i$ is synchronized with $u^*$, then $\ell'(j)=\ell(j)$ must hold, while otherwise $\ell'(j)=\hat q_i-\ell(j) +1$. We refer to the resulting curve $\hat \zeta'_{i,j}$ as the second segment in the drawing of edge $\hat a_{i,j}$, and we denote $\hat Z_i'=\set{\hat \zeta'_{i,j}\mid 1\leq j\leq \hat q_i}$.

We need the following simple observation.

There exists a set $\qset''_i$ of paths in graph $G_{i-1}$, routing the vertices of $\set{\hat v_{i,j}\mid 1\leq j\leq \hat q_i}$ to vertex $u_i$, so that the paths are internally disjoint from $X_i'$, and cause congestion at most $100$. Moreover, every edge of $A'_i$ appears as the last edge on exactly one path in $\qset''_i$.

this proof is not perfect, should be improved for clarity
Since petal $X_i$ is routable in graph $G$, there is a set $\qset'_i$ of paths routing the edges of $\hat E_i$ to vertex $u^*$ in graph $G$, such that the paths in $\qset'_i$ are internally disjoint from $X_i$, and cause congestion at most $100$.
Consider any path $Q=Q(\hat e_{i,j})\in \qset'_i$, whose first edge is $\hat e_{i,j}$. We replace the first edge on this path with the edge $(\hat v_{i,j},\hat y_{i,j})$. Assume now that the last edge on $Q$ is $e_{i',j}\in E_{i'}$, for some $i'\neq i$. If $i'>i$, then, by replacing edge $e_{i',j}$ with the corresponding edge $a_{i',j}$, we obtain a new path $Q'$ in graph $G_{i-1}$, whose first endpoint is $\hat v_{i,j}$, and last vertex is $u_{i'}$. If $i'<i$, then we set $Q'=Q$. Let $\qset''_i=\set{Q'\mid Q\in \qset'_i}$ be the resulting set of paths in graph $G_{i-1}$. Consider now any vertex $u_{i'}$, for $i< i'\leq k$. Every path $Q'\in \qset''_i$ that terminates at $u_{i'}$ must contain an edge of $A'_{i'}$. Therefore, the number of paths in $\qset''_i$ terminating at $u_{i'}$ is bounded by $100\hat q_{i'}$. Since, for all $1\leq i''\leq k$, $|\hat E_{i''}|=\hat q_{i''}$, we can then extend all such paths, using the edges of $A'_{i'}\cup \hat A_{i}$, to ensure that they terminate at vertex $u_i$. Moreover, since $|\qset''_i|=|\hat q_i|=|A_i'|$, we can extend all paths in $\qset''_i$ as described above so that each of them terminates at $u_i$, and all such paths cause congestion at most $100$ in $G_{i-1}$, and every edge of $A'_i$ appears as the last edge on exactly one path in $\qset''_i$.

To conclude, we have established that there exists a collection $\qset''_i$ of paths in graph $G'$, routing the vertices of $\set{\hat v_{i,j}\mid 1\leq j\leq \hat q_i}$ to vertex $u_i$, so that the paths are internally disjoint from $X_i'$, and cause congestion at most $100$.

Consider a graph $G'$, that is obtained from graph $G_{i-1}$ as follows: for every edge $e\in E(G_{i-1})\setminus E(X'_i)$, we include $\cong_{G_{i-1}}(\qset''_i,e)$ copies of the edge $e$. If an edge
$e\in E(G_{i-1})\setminus E(X'_i)$ does not participate in any paths in $\qset''_i$, then it is deleted from $G'$. We also delete all isolated vertices from $G'$. Note that drawing $\phi_{i-1}$ of $G_{i-1}$ naturally defines a drawing $\phi'$ of graph $G'$, where for each edge $e\in E(G_{i-1})\setminus E(X'_i)$, we draw the copies of $e$ along the original image of edge $e$ in $\phi_{i-1}$.
We can now modify the set $\qset''_i$ of paths so that every edge of $G'$ i used by a distinct path in $\qset''_i$, that is, the paths become edge-disjoint.
We use the algorithm from <Ref> in order to compute a type-2 uncrossing of the paths in $\pset''_i$. Specifically, the algorithm is applied to graph $G'$, its drawing $\phi'$, with $C=X'_i$, and the set $\qset''_i$, which is now a set of edge-disjoint paths in graph $G'$. We denote by $\Gamma'_i=\set{\gamma'_{i,j}\mid 1\leq j\leq \hat q_i}$ the set of curves that the algorithm outuputs, where $\gamma'_{i,j}$ is the curve that originates at vertex $\hat v_{i,j}$. Note that each curve in $\Gamma'_i$ terminates at the image of vertex $u_i$, and the curves in $\Gamma'_i$ are disjoint from each other.
Since the curves in $\Gamma'_i$ are aligned with graph $\bigcup_{Q\in \qset''_i}Q$, the  total number of crossings between the curves in $\Gamma'_i$ and the edges of $X'_i$ is bounded by $100\chi_i$. Since the curves in $\Gamma_i$
that are aligned with the graph $\bigcup_{Q\in \hat Q_i}Q$, the total number of crossings between the curves of $\Gamma_i$ and the curves of $\Gamma'_i$ is bounded by $\chi_i+\cro(\hat E_i)$, where $\chi'_i$ is the number of crossings between edges of $\hat E_i$ in drawing $\phi_{i-1}$.

Since the curves in $\Gamma'_i$ are aligned with graph $\bigcup_{Q\in \qset''_i}Q$, for every edge $a'_{i,j}\in A'_i$, there is a unique curve $\gamma'_{i,j'}\in \Gamma'_i$ that contains the segment of the image of $a'_{i,j}$ that lies in the disc $\tilde D_i$. In particular, it contains point $z_{i,j}$ on the boundary of disc $\tilde D_i$. Note however that it is possible that $j\neq j'$, that is, the curve connects the image of vertex $v_{i,j'}$ to point $z_{i,j}$, where $j\neq j'$. For convenience, we will denote point $z_{i,j}$ by $s_{j'}$. For all $1\leq j\leq \hat q_i$, we then let $\hat \zeta'_{i,j}$ be obtained by concatenating the image of the edge $(\hat x_{i,j},\hat v_{i,j})$ with the segment of the curve $\gamma'_{i,j}$ connecting the image of $\hat v_{i,j}$ to point $s_j$. We then set $\hat Z'_i=\set{\hat \zeta'_{i,j}\mid 1\leq j\leq \hat q_i}$.

Computing the drawing $\psi_i$.
Consider the current drawing $\phi_{i-1}$ of graph $G_{i-1}$. We slightly modify this drawing in order to obtain a drawing $\psi_i$ of graph $X_i$, and, for each edge $e\in \delta_{G_i}(X_i)\setminus \delta_{G_i}(u^*)$, a drawing of a segment of $e$ that is incident to its endpoint that lies in $X_i$.

In order to do so, we start with the drawing $\phi_{i-1}$ of graph $G_{i-1}$, and we delete from it the images of all edges and vertices, except for those lying in $X'_i$. We will also make use of the disc $\tilde D_{i-1}$ that we have defined. Next, for all $1\leq j\leq q_i$, we consider the image of edge $a_{i,j}$ in the current drawing. Recall that this image intersects the boundary of $\tilde D_i$ at a single point, that we denote by $p''_{i,j}$. From the definition of the rotation $\oset'_{u_i}\in \Sigma'$, points $z'_{1},\ldots,z'_{\hat q_i},p''_{i,q_i},\ldots,p''_{i,2},p''_{i,1}$ appear on the boundary of disc $\tilde D_i$ in this order, and, if $u_i$ is synchronized with  $u^*$, then they are encountered in this order as we traverse the boundary of $\tilde D_i$ so its interior lies on our right; see <Ref>.

Consider now some edge $a_{i,j}\in A_i$, for $1\leq j\leq q_i$, and assume that $a_{i,j}=(u_i,x_{i,j})$, where $x_{i,j}\in V(X_i)$. We denote by $\zeta'_{i,j}$ the segment of the image of edge $a_{i,j}$ from the image of $x_{i,j}$ to point $p''_{i,j}$ (see <Ref>), and we refer to $\zeta'_{i,j}$ the second segment in the drawing of edge $e_{i,j}$. We delete, from the current drawing, the portion of the image of $a_{i,j}$ lying in the interior of the disc $\tilde D_i$; in other words, we replace the image of $a_{i,j}$ with the curve $\zeta'_{i,j}$.

Lastly, we add the curves in set $\hat Z'_i=\set{\hat \zeta'_{i,j}\mid 1\leq j\leq \hat q_i}$ to the current drawing. Recall that, for each
$1\leq j\leq \hat q$, curve $\hat \zeta'_{i,j}$ connects the image of vertex $\hat x_{i,j}$ (the endpoint of edge $\hat a_{i,j}\in \hat E_i$ that lies in $X_i$) to point $z'_{\ell'(j)}$ on the boundary of $\tilde D_i$, where $1\leq \ell'(j)\leq \hat q_i$.

This completes the drawing $\psi_i$.
We now bound the number of crossings in this drawing.
In order to bound the number of crossings, recall that every curve $\zeta'_{i,j}\in Z'_{i,j}$ is a segment of the image of edge $a_{i,j}\in A_{i,j}$, and every curve $\hat \zeta'_{i,j}\in \hat Z'_i$ is a concatenation of four curves: the image of the edge $\hat a_{i,j}\in \hat A_i$; the curve $\gamma'_{i,j}\in \Gamma'_i$; the curve $\rho_j$, and the image of the edge $a'_{i,\ell(j)}\in A'_i$. Since the curves in $\Gamma'_i$ are disjoint from each other, and the curves $\rho_1,\ldots,\rho_{\hat q_i}$ are disjoint from each other and are contained in disc $D$, the total number of crossings in $\psi_i$ is bounded by (i) the number of crossings between pairs of edges in $E(X'_i)\cup \hat A_i\cup A'_i$ (which is bounded by $\cro_i$ by definition); and (ii) the number of crossings between edges of $E(X'_i)\cup \hat A_i\cup A'_i$ and curves of $\Gamma'_i$ (which is bounded by $O(\cro_i)$ from the discussion above. We conclude that drawing $\psi_i$ has $O(\cro_i)$ crossings.

We will view the interior of the disc $\tilde D_i$ as the “outer face” of the drawing $\psi_i$.  If we denote by $\tilde D'_i$ the disc in the sphere whose boundary is the same as the boundary of $\tilde D_i$, but its interior is disjoint from the interior of $\tilde D_i$, then the current drawing $\psi_i$ is contained in $\tilde D'_i$. To summarize, drawing $\psi_i$ consists of: (i) the drawing of all edges and vertices of $X_i\setminus\set{u^*}$; (ii) for every edge $a_{i,j}=(x_{i,j},u^*)\in E_i$, a curve $\zeta'_{i,j}$, connecting the image of $x_{i,j}$ to point $p''_{i,j}$ on the boundary of $\tilde D'_i$; and (iii) for every edge $\hat a_{i,j}=(\hat x_{i,j},\hat y_{i,j})\in \hat A_i$ with $\hat x_{i,j}\in X_i$, a curve $\hat \zeta'_{i,j}$, connecting the image of $\hat x_{i,j}$ to point $z'_{\ell'(j)}$ on the boundary of $\tilde D_i'$, where $1\leq \ell'(j)\leq \hat q_i$. Note that the points $p''_{i,1},\ldots,p''_{i,q_i},z'_{\hat q_i},\ldots,z'_{2},z'_{1}$ appear on the bounary of disc $\tilde D_i'$ in this order, and, if $u_i$ is synchronized with  $u^*$, then they are encountered in this order as we traverse the boundary of $\tilde D'_i$ so its interior lies to our right.

§.§.§ Stage 3: Computing the Drawing $\phi_i$ of $G_i$

We start with the drawing $\phi_{i-1}'$ that we computed in Stage 1.
We consider two cases. The first case is when vertex $u_i$ is synchronized with vertex $u^*$. In this case, we place the drawing $\psi_i$ that we computed in Stage 2 of the algorithm inside the disc $D'_i$, so that the discs $D'_i$ and $\tilde D'_i$ coincide. In the second case, vertex $u_i$ is not synchronized with vertex $u^*$. In this case, we place a mirror image of the drawing $\phi_i$ inside the disc $D'_i$, so that the boundaries of the discs $D'_i$ and (the mirror image of) disc $\tilde D'_i$ coincide (see <Ref>). In either case, we obtain two disjoint segments on the boundary of $D'_i$: segment $\tilde \sigma_i$, containing the points $p''_{i,1},\ldots,p''_{i,q_i}$, and segment $\tilde  \sigma'_i$, containing the points $z'_1,\ldots,z'_{\hat q_i}$. Moreover, we are now guaranteed that points $p''_{i,1},\ldots,p''_{i,q_i},z'_{\hat q_i},\ldots,z'_{2},z'_{1}$  are encountered in this order as we traverse the boundary of $D_i'$, so that the interior of $D_i'$ lies to our
right (see <Ref>).
Recall that we have defined a collection of points $\set{p'_{i,1}, p'_{i,2},\ldots,p'_{i, q_i},p_{i,\hat q_i},p_{i,\hat q_i-1},\ldots,  p_{i,1}}$ on the boundary of $D_i$, that appear in this order on the boundary of $D_i$, as we traverse it so that the interior of $D_i$ lies to our right (see Figures <ref> and <ref>). Consider now some edge $e_{i,j}=(u^*,x_{i,j})\in E_i$, for $1\leq i\leq q_i$. Recall that we have already defined a curve $\zeta_{i,j}$, that serves as the first segment of the drawing of $e_{i,j}$, and connects the image of $u^*$ to point $p'_{i,j}$ on the boundary of $D_i$, such that curve $\zeta_{i,j}$ is internally disjoint from $D_i$. We have also defined a curve $\zeta'_{i,j}$ inside the disc $D'_i$, that connects the image of vertex $x_{i,j}$ to point $p''_{i,j}$ on the boundary of $D'_{i,j}$.

Planting disc $\tilde D'_i$ inside $D'_i$.