Towards Better Approximation of Graph Crossing Number
Julia ChuzhoyToyota Technological Institute at Chicago. Email<EMAIL_ADDRESS>Supported in part by NSF grant CCF-1616584.   Sepideh MahabadiToyota Technological Institute at Chicago. Email<EMAIL_ADDRESS>Zihan TanComputer Science Department, University of Chicago. Email<EMAIL_ADDRESS>Supported in part by NSF grant CCF-1616584.

Graph Crossing Number is a fundamental and extensively studied problem with wide ranging applications. In this problem, the goal is to draw an input graph $G$ in the plane so as to minimize the number of crossings between the images of its edges. The problem is notoriously difficult, and despite extensive work, non-trivial approximation algorithms are only known for bounded-degree graphs. Even for this special case, the best current algorithm
achieves a $\tilde O(\sqrt n)$-approximation, while the best current negative results do not rule out constant-factor approximation.
All current approximation algorithms for the problem build on the same paradigm, which is also used in practice: compute a set $E'$ of edges (called a planarizing set) such that $G\setminus E'$ is planar; compute a planar drawing of $G\setminus E'$; then add the drawings of the edges of $E'$ to the resulting drawing. Unfortunately, there are examples of graphs $G$, in which any implementation of this method must incur $\Omega  (\opt^2 )$ crossings, where $\opt$ is the value of the optimal solution.
This barrier seems to doom the only currently known approach to designing approximation algorithms for the problem, and to prevent it from yielding a better than $O(\sqrt n)$-approximation.

In this paper we propose a new paradigm that allows us to overcome this barrier.
We show an algorithm, that, given a bounded-degree graph $G$ and a planarizing set $E'$ of its edges, computes another planarizing edge set $E''$ with $E'\subseteq E''$, such that $|E''|$ is relatively small,
and there exists a near-optimal drawing of $G$ in which no edges of $G\setminus E''$ participate in crossings. This allows us to reduce the Crossing Number problem to Crossing Number with Rotation System – a variant of the Crossing Number problem, in which the ordering of the edges incident to every vertex is fixed as part of input. In our reduction, we obtain an instance $G'$ of this problem, where $|E(G')|$ is roughly bounded by the crossing number of the original graph $G$. We show a randomized algorithm for this new problem, that allows us to obtain  an $O(n^{1/2-\eps})$-approximation for Graph Crossing Number on bounded-degree graphs, for some constant $\eps>0$.

alternative and heavily summarized third paragraph:

In this paper we propose a new paradigm that allows us to overcome this barrier.
Specifically, we show an algorithm, that, given a bounded-degree graph $G$ and a planarizing set $E'$ of its edges, computes another planarizing edge set $E''$ with $E'\subseteq E''$, such that $|E''|$ is relatively small compared to $|E'|$ and the crossing number of $G$, and there exists a near-optimal drawing of $G$ in which no edges of $G\setminus E''$ participate in crossings. This allows us to reduce the crossing number problem in bounded-degree graphs $G$ to crossing number with rotation system, in which the input is a graph $G'$ with arbitrary vertex degrees, and for every vertex of $G'$, a circular ordering of its incident edges is given which should be respected in the solution. By getting an approximate algorithm for this problem we achieve an $O(n^{1/2-\eps})$-approximation for Graph Crossing Number on bounded-degree graphs, for $\eps=1/22$. While this is a rather modest improvement in the approximation factor, it demonstrates the viability of our new method and breaks the barrier that the previously known methods could not overcome.

§ INTRODUCTION

Given a graph $G=(V,E)$, a drawing of $G$ is an embedding of the graph into the plane, that maps every vertex to a point in the plane, and every edge to a continuous curve connecting the images of its endpoints. We require that the image of an edge may not contain images of vertices of $G$ other than its two endpoints, and no three curves representing drawings of edges of $G$ may intersect at a single point, unless that point is the image of their shared endpoint. We say that two edges cross in a given drawing of $G$ iff their images share a point other than the image of their common endpoint.
In the problem, the goal is to compute a drawing of the input $n$-vertex graph $G$ with minimum number of crossings. We denote the value of the optimal solution to this problem, also called the crossing number of $G$, by $\optcro(G)$.

The problem naturally arises in several areas of Computer Science and Mathematics. The problem was initially introduced by Turán [33], who considered the question of computing the crossing number of complete bipartite graphs, and since then it has been a subject of extensive studies (see, e.g., [33, 9, 12, 8, 13, 21, 22], and also [31, 29, 26, 34] for surveys on this topic).  The problem is known to be NP-hard [16], and it remains NP-hard, and APX-hard on cubic graphs [19, 7]. The problem appears to be notoriously difficult from the approximation perspective. All currently known algorithms achieve approximation factors that depend polynomially on $\Delta$ – the maximum vertex degree of the input graph, and, to the best of our knowlgedge, no non-trivial approximation algorithms are known for graphs with arbitrary vertex degrees. We note that the famous Crossing Number Inequality [1, 23] shows that, for every graph $G$ with $|E(G)|\geq 4n$, the crossing number of $G$ is  $\Omega(|E(G)|^3/n^2)$. Since the problem is most interesting when the crossing number of the input graph is low, and since our understanding of the problem is still extremely poor, it is reasonable to focus on designing algorithms for low-degree graphs. Throughout, we denote by $\Delta$ the maximum vertex degree of the input graph. While we do not make this assumption explicitly, it may be convenient to think of $\Delta$ as being bounded by a constant or by $\poly\log n$.

The first non-trivial algorithm for , due to Leighton and Rao [24], combined their algorithm for balanced separators with the framework of [6], to compute a drawing of input graph $G$ with $O((n+\optcro(G)) \cdot \Delta^{O(1)}\cdot \log^4n)$ crossings. This bound was later improved to $O((n+\optcro(G)) \cdot \Delta^{O(1)}\cdot \log^3n)$ by [15], and then to $O((n+\optcro(G)) \cdot \Delta^{O(1)}\cdot \log^2n)$   as a consequence of the improved algorithm of [3] for Balanced Cut. All these results provide an $O(n\poly(\Delta \log n))$-approximation for (but perform much better when $\optcro(G)$ is high). For a long time, this remained the  best approximation algorithm for , while the best inapproximability result, to this day, only rules out the existence of a PTAS, unless NP has randomized subexponential time algorithms [16, 2]. We note that it is highly unusual that achieving an $O(n)$-approximation for an unweighted graph optimization problem is so challenging. However, unlike many other unweighted graph optimization problems, the value of the optimal solution to may be as large[This can be seen by applying the Crossing Number Inequality to the complete $n$-vertex graph.] as $\Omega(n^4)$.

A sequence of papers [12, 9] was the first to break the barrier of $\tilde \Theta(n)$-approximation, providing a $\tilde O \left (n^{9/10}\cdot \Delta^{O(1)}\right )$-approximation algorithm. Recently, a breakthrough sequence of works [21, 22] has led to an improved  $\tilde O\left(\sqrt{n}\cdot \Delta^{O(1)}\right )$-approximation for .
All the above-mentioned algorithms exploit the same algorithmic paradigm, that builds on  the connection of  to the   problem, that we discuss next.

Minimum Planarization.
In the  problem, the input is an $n$-vertex graph $G=(V,E)$, and the goal is to compute a minimum-cardinality subset $E^*$ of its edges (called a planarizing set), such that graph $G\setminus E^*$ is planar. This problem and its close variant  (where we need to compute a minimum-cardinality subset $V'$ of vertices such that $G\setminus V'$ is planar) are of independent interest and have been studied extensively (see, e.g., [12, 21, 22]).
It is immediate to see that, for every graph $G$, $\opt_{\mvp}(G) \leq \opt_{\mep}(G)\leq \optcro(G)$, where $\opt_{\mvp}(G)$ and $\opt_{\mep}(G)$ are the optimal solution values of the and the problems on $G$, respectively.
A simple application of the Planar Separator Theorem of [25] was shown to give an  $O(\sqrt{n\log n}\cdot \Delta)$-approximation algorithm for both problems [12].
Further, [13] provided an $O(k^{15}\cdot \poly(\Delta\log n)$-approximation algorithm for  and ,  where $k$ is the value of the optimal solution.
The more recent breakthrough result of Kawarabayashi and Sidiropoulus [21, 22] provides an $O(\Delta^3\cdot \log^{3.5}n)$-approximation algorithm for , and an $O(\Delta^4\cdot \log^{3.5}n)$-approximation algorithm for .

Returning to the problem, all currently known approximation algorithms for the problem rely on the same paradigm, which is also used in heuristics (see, e.g. [4]). For convenience of notation, we call it Paradigm $\Pi$.

Paradigm $\Pi$

* compute a planarizing set $E'$ of edges for $G$;

* compute a planar drawing of $G\setminus E'$;

* add the images of the edges of $E'$ to the resulting drawing.

$\ $

Paradigm $\Pi$

* compute a planarizing set $E'$ of edges for $G$;

* compute a planar drawing of $G\setminus E'$;

* add the images of the edges in $E'$ to the resulting drawing.

We note that graph $G\setminus E'$ may not be $3$-connected and thus it may have several planar drawings; there are also many ways in which the edges of $E'$ can be added to the drawing.
It is therefore important to understand the following questions:

Can this paradigm be implemented in a way that provides a near-optimal drawing of $G$? What is the best approximation factor that can be achieved when using paradigm $\Pi$?

These questions were partially answered in previous work. Specifically, [12] provided an efficient algorithm, that, given an input graph $G$, and a planarizing set $E'$ of $k$ edges for $G$, draws the graph with $O\left(\Delta^3\cdot k \cdot (\optcro(G) + k)\right)$ crossings.
Later, Chimani and Hliněnỳ [8] improved this bound via a different efficient algorithm to
$O\left(\Delta\cdot k \cdot (\optcro(G) +\log k)+k^2\right)$.
Both works can be viewed as an implementation of the above paradigm.
Combining these results with the $O(\poly(\Delta\log n))$-approximation algorithm  for of [22] in order to compute the initial planarizing edge set $E'$  with $|E'|\leq O(\optcro(G)\cdot \poly(\Delta\log n))$, yields an implementation of Paradigm $\Pi$ that produces a drawing of the input graph $G$ with $O\left ((\optcro(G))^2\cdot\poly(\Delta\log n)\right )$ crossings. Lastly, combining this with the  $O(n\poly(\Delta\log n))$-approximation algorithm of [24, 6, 15] leads to the best currently known    $O(\sqrt{n}\cdot\poly(\Delta\log n))$-approximation algorithm of [22] for .

* compute a planarizing set $E'$ of edges for $G$;

* compute a planar drawing of $G\setminus E'$;

* add the images of the edges in $E'$ to the resulting drawing, while trying to minimize the number of crossings that they introduce (see e.g. [4]).

The bottleneck in using this approach in order to obtain a better than $O(\sqrt n)$-approximation for is the bounds of [12] and [8], whose algorithms produce a drawing of the graph $G$ with $O\left(k \cdot \optcro(G) + k^2\right)$ crossings when $\Delta=O(1)$, where $k$ is the size of the given planarizing set. The quadratic dependence of this bound on $k$ and the linear dependence on $k\cdot \optcro(G)$ are unacceptable if our goal is to obtain better approximation using this technique. A natural question therefore is:

Can we obtain a stronger bound, that is linear in $(\optcro(G)+|E'|)$, using Paradigm $\Pi$?

Unfortunately, Chuzhoy, Madan and Mahabadi [11] have answered this question in the negative; see Section <ref> for details. Their results show that the bounds of [12] and [8] are almost tight, and so we cannot hope to break the $\Theta(\sqrt{n})$ approximation barrier for using the above paradigm. This seems to doom the only currently known approach for designing approximation algorithms for the problem.

In this paper, we propose a new paradigm towards overcoming this barrier, and show that it leads to a better approximation of . Specifically, we show an efficient algorithm, that, given a planarizing set $E'$ of edges, augments $E'$ in order to obtain a new planarizing set $E''$, whose cardinality is $O\left ((|E'|+\optcro(G))\poly(\Delta \log n)\right )$. Moreover, we show that there exists a drawing $\phi$ of the graph $G$, with at most $O\left ((|E'|+\optcro(G))\poly(\Delta \log n)\right )$ crossings, where the edges of $G\setminus E''$ do not participate in any crossings. In other words, the drawing $\phi$ of $G$ can be obtained by first computing a planar drawing of $G\setminus E''$, and then inserting the images of the edges of $E''$ into this drawing.
This new paradigm can be summarized as follows:

Paradigm $\Pi'$

* compute a planarizing set $E'$ of edges for $G$;

* compute an augmented planarizing edge set $E''$ with $E'\subseteq E''$ that has some additional useful properties;

* compute a planar drawing of $G\setminus E''$;

* add the images of the edges in $E''$ to the resulting drawing.

$\ $

Our result, combined with the $O(\poly(\Delta\log n))$-approximation algorithm  for of [22], provides an efficient implementation of Steps (<ref>) and (<ref>) of Paradigm $\Pi'$, such that there exists an implementation of Steps (<ref>) and (<ref>), that produces a drawing of $G$ with $O(\optcro(G)\cdot\poly(\Delta\log n))$ crossings. This still leaves open the following question:

Can we implement Steps (<ref>) and (<ref>) of Paradigm $\Pi'$ efficiently in near-optimal fashion?

One way to address this question is by designing algorithms for the following problem: given a graph $G$ and a planarizing set $E^*$ of its edges, compute a drawing of $G$, such that the corresponding induced drawing of $G\setminus E^*$ is planar, while minimizing the number of crossings; in other words, every crossing in the drawing must be between an edge of $E^*$ and another edge of $E(G)$. This problem was considered by Chimani and Hliněnỳ [8] who showed an efficient algorithm, that computes a drawing of $G$ with $\optcro^{E^*}(G)+\tilde O(k^2 )$ crossings, where $k=|E^*|$, and $\optcro^{E^*}(G)$ is the optimal solution value for this problem. Unfortunately, if our goal is to break the $\Theta(\sqrt n)$ barrier on the approximation factor for , the quadratic dependence of this bound on $k$ is prohibitive.

We propose a different approach in order to
implement Steps (<ref>) and (<ref>) of Paradigm $\Pi'$. We provide an efficient algorithm that exploits our algorithm for Steps (<ref>) and (<ref>)  in order to reduce the problem to another problem, called Minimum Crossing Number with Rotation System (). In this problem, the input is a multi-graph $G$ with arbitrary vertex degrees. Additionally, for every vertex $v$ of $G$, we are given a circular ordering $\oset_v$ of the edges that are incident to $v$ in $G$. The goal is to compute a drawing of $G$ in the plane with minimum number of crossings, that respects the orderings $\set{\oset_v}_{v\in V(G)}$ of the edges incident to each vertex (but we may choose whether the ordering is clock-wise or counter-clock-wise in the drawing). We denote by $\Sigma=\set{\oset_v}_{v\in V}$ the collection of all these orderings, and we call $\Sigma$ a rotation system for graph $G$. Given an instance $(G,\Sigma)$ of , we denote by $\optcrors(G,\Sigma)$ the value of the optimal solution for this instance.
We show a reduction, that, given an instance $G$ of with maximum vertex degree $\Delta$, produces an instance $(G',\Sigma)$ of , such that $|E(G')|\leq O\left(\optcro(G)\cdot \poly(\Delta\log n)\right)$, and moreover,  $\optcrors(G',\Sigma)\leq O\left(\optcro(G)\cdot \poly(\Delta\log n)\right )$. In particular, our reduction shows that, in order to obtain an $O(\alpha \poly(\Delta\log n))$-approximation for , it is sufficient to obtain an $\alpha$-approximation algorithm for . We also show an efficient randomized algorithm, that, given an instance $(G,\Sigma)$ of , with high probability computes a solution to the problem with at most $\tilde O\left (\left(\optcrors(G,\Sigma)+|E(G)|\right )^{2-\eps}\right )$ crossings, for $\eps=1/20$. Combining this result with our reduction, we obtain an efficient algorithm that computes a drawing of an input graph $G$ with maximum vertex degree $\Delta$, with at most $\tilde O((\optcro(G))^{2-\eps}\cdot \poly(\Delta\log n))$ crossings. We note that this algorithm can be viewed as implementing Steps (<ref>) and (<ref>) of Paradigm $\Pi'$. The resulting algorithm, in turn, leads to a $\tilde O(n^{1/2-\eps'}\poly(\Delta))$-approximation algorithm for , for some fixed constant $\eps'>0$. While this only provides a modest improvement in the approximation factor, we view this as a proof of concept that our new method can lead to improved approximation algorithms, and in particular, this result breaks the barrier that the previously known methods could not overcome.

Other related work.
There has been a large body of work on FPT algorithms for several variants and special cases of the problem (see, e.g. [17, 20, 27, 5, 18, 14]).
In particular, Grohe [17] obtained an algorithm for solving the problem exactly, in time $f(\optcro(G))\cdot n^{2}$, where function $f$ is at least doubly exponential. In his paper, he conjectures that there exists an FPT algorithm for the problem with running time $2^{O(\optcro(G))}\cdot n$. The dependency on $n$ in the algorithm of [17] was later improved by [20] from $n^2$ to $n$.

For cubic (that is, $3$-regular) graphs, the problem is equivalent to the problem.
Hliněnỳ [19] proved that is NP-hard, and Cabello [7] proved that it is APX-hard on cubic graphs.
Therefore, the problem is also APX-hard on cubic graphs.
Pelsmajer et al. [28] studied a variation of the problem, where for each vertex $v$, both the circular ordering $\oset(v)$ of its incident edges, and the orientation of this ordering (say clock-wise) are fixed. They showed that this variant of the problem is also NP-hard,  and provided an $O(n^4)$-approximation algorithm with running time $O(m^n\log m)$ for it, where $m$ is the number of edges in the graph[Note that, since the input graph $G$ in both and this variant is allowed to be a multi-graph, it is possible that $m\gg n^2$, and the optimal solution value may be much higher than $n^4$.].
They also provided additional  approximation algorithms for some special cases.

We now proceed to describe our results more formally.

§.§ Our Results

Our main technical result is summarized in the following theorem.

There is an efficient algorithm, that, given an $n$-vertex graph $G$ with maximum vertex degree $\Delta$ and a planarizing set $E'$ of its edges, computes another planarizing edge set $E''$ for $G$, with $E'\subseteq E''$, such that
$|E''|\leq O\left((|E'|+\optcro(G))\cdot\poly(\Delta\log n)\right)$, and, moreover, there is a drawing $\phi$ of $G$ with at most $O\left((|E'|+\optcro(G))\cdot\poly(\Delta\log n)\right)$ crossings, such that the edges of $G\setminus E''$ do not participate in any crossings in $\phi$.

Recall that Kawarabayashi and Sidiropoulos [22] provide an efficient $O(\poly(\Delta\log n))$-approximation algorithm for the problem. Since, for every graph $G$, there is a planarizing set $E^*$ containing at most $\optcro(G)$ edges, we can use their algorithm in order to compute, for an input graph $G$, a planarizing edge set of cardinality $O(\optcro(G)\cdot\poly(\Delta\log n))$. Combining this with Theorem <ref>, we obtain the following immediate corollary.

There is an efficient algorithm, that, given an $n$-vertex graph $G$ with maximum vertex degree $\Delta$, computes a planarizing set $E'\subseteq E(G)$ of $O(\optcro(G)\cdot \poly(\Delta\log n))$ edges, such that there is a drawing $\phi$ of $G$  with $O(\optcro(G)\cdot \poly(\Delta\log n))$ crossings, and the edges of $E(G)\setminus E'$ do not participate in any crossings in $\phi$.

The following corollary then easily follows from Corollary <ref>.

There is an algorithm, that, given an $n$-vertex graph $G$ with maximum vertex degree $\Delta$, computes a drawing of $G$ in the plane with $O(\optcro(G)\cdot \poly(\Delta\log n))$ crossings, in time  $2^{O(\cro (\log \cro) \poly(\Delta\log n))}$, where $\cro=\optcro(G)$.

The proof of Corollary <ref> appears in Section <ref> of Appendix.
Notice that, from the above corollary, it is unlikely that the problem of obtaining an $O(\poly\log n)$ approximation for in bounded-degree graphs is -hard in instances where the value of the optimal solution $\cro<n^{\eps}$ for any constant $\eps$.

Next, we show a reduction from to the problem.

There is an efficient algorithm, that, given an $n$-vertex graph $G$ with maximum vertex degree $\Delta$, computes an instance $(G',\Sigma)$ of the problem, such that the number of edges in $G'$ is at most $O\left(\optcro(G)\cdot \poly(\Delta\log n)\right)$, and   $\optcrors(G',\Sigma)\leq O\left(\optcro(G)\cdot \poly(\Delta\log n)\right )$. Moreover, there is an efficient algorithm that, given any solution to instance $(G',\Sigma)$ of of value $X$, computes a drawing of $G$ with at most  $O\left ((X+\optcro(G))\cdot \poly(\Delta\log n)\right )$ crossings.

Notice that the above theorem shows that an $\alpha$-approximation algorithm for immediately gives an $O(\alpha\poly(\Delta\log n))$-approximation algorithm for the problem. In fact, even much weaker guarantees for suffice: if there is an algorithm that, given an instance $(G,\Sigma)$ of , computes a solution of value at most $\alpha(\optcrors(G,\Sigma)+|E(G)|)$, then there is an $O(\alpha\poly(\Delta\log n))$-approximation algorithm for . Recall that [24, 15] provide an algorithm for the  problem that draws an input graph $G$ with $\tilde O((n+\optcro(G)) \cdot \Delta^{O(1)})$ crossings. While it is conceivable that this algorithm can be adapted to the problem, it only gives meaningful guarantees when the maximum vertex degree in $G$ is low, while in the instances of produced by our reduction this may not be the case, even if the initial instance of had bounded vertex degrees.
Our next result provides an algorithm for the problem.

There is
an efficient randomized algorithm, that, given an instance $(G,\Sigma)$ of , with high probability computes a solution of value at most $\tilde O\left (\left(\optcrors(G,\Sigma)+|E(G)|\right )^{2-\eps}\right )$ for this instance, for $\eps=1/20$.

By combining Theorem <ref> with  Theorem <ref>, we obtain the following immediate corollary.

There is
an efficient randomized algorithm, that, given any $n$-vertex graph $G$ with maximum vertex degree $\Delta$, with high probability computes a drawing of $G$ in the plane with at most $O\left ((\optcro(G))^{2-\epsilon}\cdot\poly(\Delta\log n)\right )$ crossings, for $\eps=1/20$.

Let $\tG$ be the input bounded-degree graph. We apply the algorithm of [22] to compute a planarizing set $\tE\subseteq E(\tG)$ with $|\tE|=\tilde O(\optcro(\tG))$.
Then we apply Theorem <ref> to $\tG$ and $\tE$ to obtain a new planarizing set $\tE'$ of edges.
We now contract each connected component of $\tG\setminus \tE'$ into a node, and denote the resulting graph by $\tG'$.
Note that the input $\tG'$ may be a multi-graph, where parallel edges and self-loops are allowed. We first preprocess the graph $\tG'$ by splitting each edge with a new vertex. Let $\tG''$ be the new graph, then it is clear that (i) $\tG''$ is a simple graph;
(ii) $|E(\tG'')|=2|E(\tG')|$;
(iii) $\sum_{v}\deg_{\tG''}(v)^2=\sum_{v}\deg_{\tG'}(v)^2+\Theta(|E(\tG')|)$; and
(iv) any drawing of $\tG''$ can be easily transformed into a drawing of $\tG'$ without creating or eliminating any crossings, and vice versa.
Then we apply Theorem <ref> to $\tG''$ and eventually obtain a drawing of $\tG$.

Lastly, by combining the algorithm from Corollary <ref> with the algorithm of Even et al. [15], we obtain the following corollary, whose proof appears in Section <ref> of Appendix.

There is an efficient $O(n^{1/2-\eps'}\cdot\poly(\Delta))$-approximation algorithm
for , for some universal constant $\eps'$.

§.§ Our Techniques

In this subsection, we provide a high-level intuitive overview of the main technical result of our paper – the proof of Theorem <ref>. As in much of previous work, we focus on the special case of , where the input graph $G$ is $3$-connected. This special case seems to capture the main difficulty of the problem, and the extension of our algorithm to the general case is somewhat standard. We use the standard graph-theoretic notion of well-linkedness: we say that a set $\Gamma$ of vertices of $G$ is well-linked in $G$ iff for every pair $\Gamma',\Gamma''$ of disjoint equal-cardinality subsets of $\Gamma$, there is a collection of $|\Gamma'|$ paths in $G$, connecting every vertex of $\Gamma'$ to a distinct vertex of $\Gamma''$, such that every edge of $G$ participates in at most $\poly\log n$ such paths. Given a sub-graph $C$ of $G$, we let $\Gamma(C)$ be the set of its boundary vertices: all vertices of $C$ that are incident to edges of $E(G)\setminus E(C)$. The following observation can be shown to follow from arguments in [9]: Suppose we are given a collection $\cset=\set{C_1,\ldots,C_r}$  of disjoint sub-graphs of $G$, such that each subgraph $C_i$ has the following properties:

* 3-Connectivity: graph $C_i$ is $3$-connected;

* Well-Linkedness: the vertex set $\Gamma(C_i)$ is well-linked in $C_i$; and

* Strong Planarity: graph $C_i$ is planar, and the vertices of $\Gamma(C_i)$ lie on the boundary of a single face in the unique planar drawing of $C_i$.

Arguments from [9] can then be used to show that there is a near-optimal drawing of $G$, in which the edges of $\bigcup_{i=1}^rE(C_i)$ do not participate in any crossings. Therefore, in order to prove Theorem <ref>, it is enough to show that there is a small planarizing set $E''$ of edges in $G$, with $E'\subseteq E''$, such that every connected component $C$ of $G\setminus E''$ has the above three properties. We note that the Well-Linkedness property is easy to achieve: there are standard algorithms (usually referred to as “well-linked decomposition”), that allow us to compute a set $E''$ of $O(|E'|)$ edges with $E'\subseteq E''$, such that every connected component of $G\setminus E''$ has the Well-Linkedness property.
Typically, such an algorithms starts with $E''=E'$, and then iterates, as long as some connected component $C$ of the current graph $G\setminus E''$ does not have the Well-Linkedness property. The algorithm then computes a cut $(X,Y)$ of $C$ that is sparse with respect to the set $\Gamma(C)$ of vertices, adds the edges of $E(X,Y)$ to the set $E''$ and continues to the next iteration. One can show, using standard arguments, that, once the algorithm terminates, $|E''|\leq O(|E'|)$ holds.

The remaining two properties, however, seem impossible to achieve, if we insist that the set $E''$ of edges is relatively small. For example, consider a cylindrical grid $C$, that consists of a large number $N$ of disjoint cycles, and a number of additional paths that intersect each cycle in a way that forms a cylindrical grid (see Figure <ref>). Consider two additional graphs $X$ and $X'$. Let $G$ be a graph obtained from the union of $C,X,X'$, by adding two sets of edges: set $E_1$, connecting some vertices of $X$ to some vertices of the innermost cycle of $C$ (the set of endpoints of these edges that lie in $C$ is denoted by $\Gamma_1$), and set $E_2$, connecting some vertices of $X'$ to some vertices of the outermost cycle of $C$ (the set of endpoints of these edges that lie in $C$ is denoted by $\Gamma_2$). Assume that the given  planarizing set of edges for $G$ is $E'=E_1\cup E_2$, so that $\Gamma(C)=\Gamma_1\cup \Gamma_2$. Then, in order to achieve the strong planarity property for the graph $C$, we are forced to add $N$ edges to set $E''$: one edge from every cycle of the cylindrical grid, in order to ensure that the vertices of $\Gamma_1\cup \Gamma_2$ lie on the boundary of a single face (see Figure <ref>).

[Bad example for the Strong Planarity property. The vertices of $\Gamma_1\cup \Gamma_2$ and the edges of $E_1\cup E_2$ are shown in red.]0.4

[Deleting the blue edges in this figure ensures that all vertices of $\Gamma_1\cup \Gamma_2$ lie on the boundary a single face. Note that this deletion may cause $C$ to violate the $3$-connectivity property.]

Obtaining  the Strong Planarity property

In order to overcome this difficulty, we weaken the Strong Planarity requirement, as follows. Informally, given a graph $G$ and a sub-graph $C$ of $G$, a bridge for $C$ is a connected component of $G\setminus C$. If $R$ is a bridge for $C$, then we let $L(R)$ be the set of legs of this bridge, that contains all vertices of $C$ that have a neighbor in $R$. We replace the Strong Planarity requirement with the following weaker property:

* Bridge Property: for every bridge $R$ for $C_i$, all vertices of $L(R)$ lie on the boundary of a single face in the unique planar drawing of $C_i$.

We illustrate the intuition for why this weaker property is sufficient on the example from Figure <ref>. Let $G_1=C\cup E_1\cup X$, and let $G_2=C\cup E_2\cup X'$. Notice that $C$ has the strong planarity property in both $G_1$ and $G_2$. Therefore, from the results of [9], there is a drawing $\phi_1$ of $G_1$, and a drawing $\phi_2$ of $G_2$, such that the edges of $C$ do not participate in any crossings in either drawing. In particular, the drawings of the graph $C$ induced by $\phi_1$ and $\phi_2$ must be identical to the unique planar drawing of $C$, and hence to each other.
Moreover, in drawing $\phi_1$ of $G_1$, all edges and vertices of $X$ must be drawn inside a disc whose boundary is the innermost cycle of $C$, and in the drawing $\phi_2$ of $G_2$, all edges and vertices of $X'$ must be drawn outside of the disc whose boundary is the outermost cycle of $C$.
Therefore, we can “glue” the drawings $\phi_1$ and $\phi_2$ to each other via the drawing of $C$ in order to obtain the final drawing $\phi$ of $G$, such that the edges of $C$ do not participate in crossings in $\phi$.

Assume now that the Bridge Property does not hold for $C$ (for example, assume that $X$ and $X'$ are connected by an edge). Then we can show that in any drawing of $G$, at least $\Omega(N)$ edges of $C$ must participate in crossings. We can then add $N$ edges of $C$ to $E''$ – one edge per cycle, as shown in Figure <ref>, in order to ensure that all vertices of $\Gamma_1\cup \Gamma_2$ lie on the boundary of a single face of the resulting drawing. This increase in the cardinality of $E''$ can be charged to the crossings of the optimal drawing of $G$ in which the edges of $C$ participate.

Intuitively, if our goal were to only ensure the Well-Linkedness and the Bridge properties, we could start with $E''=E'$, and then gradually add edges to $E''$, until every connected component of $G\setminus E''$ has the bridge property, using reasonings that are similar to the ones above. After that we could employ the well-linked decomposition in order to ensure the Well-Linkedness property of the resulting clusters. One can show that, once the Bridge Property is achieved, it continues to hold over the course of the algorithm that computes the well-linked decomposition.

Unfortunately, it is also critical that we ensure the $3$-connectivity property. Assume that a connected component $C$ of $G\setminus E''$ is $3$-connected, let $\psi$ be its unique planar drawing, and let $\phi^*$ be the optimal drawing of $G$. Then one can show that drawing $\psi$ of $C$ is “close” to the drawing $\phi^*_C$ of $C$ induced by $\phi^*$. We measure the “closeness” between two drawings using the notion of irregular vertices and edges, that was introduced in [12]. A vertex $v$ of $C$ is irregular, if the ordering of the edges incident to $v$, as they enter $v$, is different in the drawings $\psi$ and $\phi^*_C$ (ignoring the orientation). The notion of irregular edges is somewhat more technical and, since we do not need it, we will not define it here. It was shown in [12], that, if $C$ is $3$-connected, then the total number of irregular vertices and edges of $C$ is roughly bounded by the number of crossings in which the edges of $C$ participate in $\phi^*$. Therefore, if we think of the number of crossings in $\phi^*$ as being low, then the two drawings $\psi$ and $\phi^*_C$ are close to each other. However, if graph $C$ is not $3$-connected, and, for example, is only $2$-connected, then the number of irregular vertices in $C$ may be much higher. Let $S_2(C)$ denote the set of all vertices of $C$ that participate in $2$-separators, that is, a vertex $v$ belongs to $S_2(C)$ iff there is another vertex $v'\in V(C)$, such that graph $C\setminus\set{v,v'}$ is not connected.
It is easy to see that, even if the drawing $\phi^*_C$ is planar, it is possible that there are as many as $|S_2(C)|$ irregular vertices in $C$. Since we do not know what the optimal drawing $\phi^*$ looks like, it seems impossible to fix a planar drawing of $C$ that is close to $\phi^*_C$.

Ensuring the $3$-connectivity property for the connected components of $G\setminus E''$, however, seems a daunting task. As edges are added to $E''$, some components $C$ may no longer be $3$-connected. Even if we somehow manage to decompose them into $3$-connected subgraphs, while only adding few edges to $E''$, the addition of these new edges may cause the well-linkedness property to be violated. Then we need to perform the well-linked decomposition from scratch, which in turn can lead to the violation of the 3-connectivity property, and it is not clear that this process will terminate while $|E''|$ is still sufficiently small.

In order to get around this problem, we slightly weaken the $3$-connectivity property. We first observe that, even if graph $C$ is not $3$-connected, and is instead $2$-connected, but the number of vertices participating in $2$-separators (vertices in set $S_2(C)$) is low, then this is sufficient for us. Intuitively, the reason is that,
the results of  [12] show that the number of irregular vertices in such a graph $C$ is roughly bounded by $|S_2(C)|$ plus the number of crossings in $\phi^*$ in which the edges of $C$ participate. Another intuitive explanation is that, when $|S_2(C)|$ is low, there are fewer possible planar drawings of $C$, so we may think of all of them as being “close” to $\phi^*_C$. Unfortunately, even this weaker property is challenging to achieve, since we need to ensure that it holds simultaneously with the Well-Linkedness and the Bridge properties, for all connected components of $G\setminus E''$. In order to overcome this obstacle, we allow ourselves to add a small set $A$ of “fake” edges to the graph $G$, whose addition ensures that each component of $(G\setminus E'')\cup A$ is a $2$-connected graph with few $2$-separators, for which the Well-Linkedness and the Bridge properties hold. Intuitively, we show that the fake edges of $A$ can be embedded into the graph $G$, so that, in a sense, we can augment the optimal drawing $\phi^*$ of $G$ by adding the images of the edges of $A$ to it, without increasing the number of crossings (though we note that this is an over-simplification that is only intended to provide intuition). The proof of Theorem <ref> can then be thought of as consisting of two parts. In the first part, we present an efficient algorithm that computes the set $E''$ of edges of $G$ with $E'\subseteq E''$, and the collection $A$ of fake edges, such that, for every connected component $C$ of graph $(G\setminus E'')\cup A$, one of the following holds: either $|\Gamma(C)|\leq \poly(\Delta \log n)$, or $C$ has the Well-Linkedness and the Bridge properties, together with  the weakened $3$-Connectivity property. We also compute an embedding of the fake edges in $A$ into $G$ in this part. In the second part, we show that there exists a near-optimal drawing of $G$ in which the edges of $G\setminus E''$ do not participate in crossings. The latter part formalizes and significantly generalizes ideas presented in [9].

§.§ Related Work

We start with some basic definitions and notation in Section <ref>. We then present a high-level overview of the proofs of all our results in Section <ref>, with most details deferred to subsequent sections.
Section <ref> contains definitions and general results regarding block decompositions of graphs (mostly from previous work). The proof of Theorem <ref> is completed in Sections <ref>–<ref>, and Section <ref> completes the proof of Theorem <ref>.

@@Then in Section <ref> we show how to compute a decomposition of a graph into acceptable clusters.
Section <ref> and Section <ref> are devoted to computing the drawings of these types of acceptable clusters.
Section <ref> shows the generalization of these results to non $3$-connected graphs.
Lastly in Section <ref>, an algorithm is given for , proving Theorem <ref>.

§.§ Known Results

* $\eg(G)$: euler genus of $G$;

* $\cro(G)$: crossing number of $G$;

* $\mvp(G)$: minimum size of a vertex planarizating set of $G$;

* $\mep(G)$: minimum size of an edge planarizating set of $G$;

* $\Delta$: maximum degree of $G$;

§.§.§ What is trivial

* For each $G$, $\mep(G)\le 2\cdot \cro(G)$ (let $E'$ be the set of edges that is incident to some crossing);

* For each $G$, $\eg(G)\le \mep(G)$
(for each edge in the edge planarizing set, we create a handle to link its endpoints);

* For each $G$, $\eg(G)\le 2\cdot \cro(G)$ (corollary of $1$ and $2$).

In this note we only consider bounded-degree graphs, so $\Delta=O(1)$ and $\mvp(G)=\Theta(\mep(G))$.

§.§.§ What is known

24: Given any $G$, we can find a drawing of $G$ with $\tilde{O}(n+\cro(G))$ crossings;

12: Given an edge-planarizing set $E'\subseteq E$ of a $G$, we can find a drawing of $G$ with $O(|E'|^2+|E'|\cdot\cro(G))$ crossings;

9: Given any $G$, we can find an edge-planarization set $E'\subseteq E$, such that $|E'|=\tilde{O}(\cro^5(G))$. As a corollary (of $2$ and $3$), given a $G$, we can find a drawing of $G$ with $\tilde{O}(\cro^{10}(G))$ drawings.

8: Given an edge-planarizing set $E'\subseteq E$ of a $G$, we can find a drawing of $G$ with $\cro_{E'}(G)+O(|E'|^2)$ crossings, where $\cro_{E'}(G)$ is the smallest number of crossings among all drawings of $G$ whose restriction on the subgraph $G\setminus E'$ is planar (note that there can be more than one planar drawings of $G\setminus E'$);

22 (as a corollary of approximating euler genus): Given any $G$, we can find a drawing of $G$ with $\tilde{O}(\cro^2(G))$ crossings. As a corollary (of $1$ and $5$), given a $G$, we can find a drawing of $G$ with $O(n^{1/2} \poly\log n)\cdot \cro(G)$ crossings.

22 (finding edge-planarization set): Given any $G$, we can find a vertex planarizing set $X\subseteq V(G)$ such that $|X|=\tilde{O}(\eg(G))$. In a $G$, this is equivalent to finding an edge-planarizing set $E'\subseteq E(G)$ such that $|E'|=\tilde{O}(\eg(G))$. As a corollary (of 6 and 2 in previous section), given any $G$, we can find an edge planarizing set $E'\subseteq E(G)$ such that $|E'|=\tilde{O}(\cro(G))$.

§.§ High Level Overview of Our Approach

Let $G$ be a on $n$ vertices. The goal is to efficiently compute a drawing $\phi$ of $G$, such that $\cro(\phi)=\tilde{O}(\cro(G))$.

A classical way of finding a drawing of $G$ with small number of crossings is to first find a planarizing set $E'$ (whose size needs to be reasonably small, for example $\tilde{O}(\cro(G))$), then find a planar drawing of $G\setminus E'$, and finally add edges of $E'$ back to the drawing. Let $E'$ be a planarizing set of edges in $G$. Let $\Phi_{E'}(G)$ be the set of all drawings of $G$, in which the induced drawing of $G\setminus E'$ is planar.
Note that, the classical way first finds a set $E'$ and eventually output a drawing $\phi$ of $G$ from $\Phi_{E'}(G)$.
We denote by $\cro_{E'}(G)$ the smallest number of crossings in a drawing of  $\Phi_{E'}(G)$.
Namely, $\cro_{E'}(G)=\min\{\cro(\phi)\mid \phi\in \Phi_{E'}(G)\}$.

Unfortunately, there is an example of a graph $G$ and a planarizing set $E'$ of $k$ edges of $G$, such that $\cro(G)=O(k)$, while $\cro_{E'}(G)=\Omega(k^2)$.
This means that simply requiring that $|E'|$ is small is not enough. We not only need $|E'|$ to be small, but also need $G\setminus E'$ to have some structure, so that $\cro_{E'}(G)$ is provably close to $\cro(G)$.

Our goal is to prove the following theorem.

There is an efficient algorithm, that, given a bounded-degree graph $G$ and an edge planarizing set $E'$ in $G$, computes another set $E''$ of edges with $E'\subseteq E''$ (so $E''$ is also planarizing), such that:

* $|E''|=\tilde O(|E'|+\cro(G))$; and

* $\cro_{E''}(G)=\tilde O(|E'|+\cro(G))$.

It seems from the above theorem that we do not need $|E''|$ to be small. But in fact we do. Since eventually, we will also want to construct an algorithm that finds a drawing in $\Phi_{E''}(G)$ that has small number of crossings.
Note that, although the theorem says that $\cro_{E''}(G)=\tilde O(\cro(G))$, there is no guarantee that we can efficiently find a drawing $\phi\in \Phi_{E''}(G)$ such that $\cro(\phi)=\tilde O(\cro(G))$.
In fact, we will be dealing with $1$-connected or $2$-connected components, and may use charging scheme to bound their cost by $|E''|$, so eventually we aim at finding a drawing in $\Phi_{E''}(G)$ with $\tilde O(|E''|+\cro(G))$ crossings.

But that is for the future.

The plan for now is to start with an initial planarizing set $E'$, and to augment it gradually, by adding edges to it over several steps. Throughout, every vertex that has an edge in $E'$ incident to it is called a terminal. The set of terminals is denoted by $T$.
Throughout, we also denote $H=G\setminus E'$. As edges are added to $E'$, graph $H$ evolves.

Consider some connected component $C$ of $H$,

we assume that it is $3$-connected. Consider the unique drawing of $C$, and let $F$ be some face in this drawing containing some terminals. We say that $F$ is a bad face, if graph $G\setminus C$ contains a path connecting a vertex of $F$ to a terminal of $C$ that does not lie on $F$. Otherwise, $F$ is a good face.

We say that a connected component $C$ of $H$ is , if:

* $C$ is $3$-connected;

* $C$ has no bad faces; and

* All terminals in $C$ are $(1/\poly\log n)$-well-linked in $C$.

For a graph $G$, we say that a subset $E''$ of its edges is an  edge-planarizing set if (i) $G\setminus E''$ is planar; and (ii) each connected component of the graph $G\setminus E''$ is .

We would like to prove the following theorem:

There is an efficient algorithm, that, given a $G$, and a planarizing set $E'$ of its edges, computes an  edge-planarizing set $E''$ of edges
of $G$, with $E'\subseteq E''$, such that $|E''|\leq\tilde O(|E'|+\cro(G))$.

Then we would like to complement the above theorem with this theorem:

Given a $G$, and let $E''$ be an  edge-planarizing set. Then there is a canonical drawing of $G$ in $\Phi_{E''}(G)$ that has at most $\tilde O(\cro(G))$ crossings.

It seems conceivable that we can extend the results that we have already to the proof of Theorem <ref>, if we take care of the issue with induced sub-graphs.

Sketch of Proof of Theorem <ref>
For now this proof ignores the issue of $3$-connectedness of the components. Our first step is to perform a well-linked decomposition, to ensure that for every connected component $C$ of $H$, all terminals lying in $T$ are well linked in $C$. This step will add some edges to $E'$ and some terminals to $T$.

In the second step, we consider every connected component $C$ of $H$ one-by-one. We will delete some edges from $C$ (adding them to $E'$) so that the resulting component contains no bad faces.

Let us now consider some component $C$ of $H$, and let $\fset$ be its collection of bad faces

For every bad face $F\in \fset$, we compute a face $N(F)\in \fset$ of $C$ that is closest to $F$ in the dual graph. If the distance between $F$ and $N(F)$ is $d(F)$, then there is a set $\cset(F)$ of $d(F)$ disjoint cycles around $F$ that separate $F$ from $N(F)$. Moreover, since face $F$ is bad, there are $\Omega(d(F))$ crossings in which the cycles of $\cset(F)$ participate in the optimal drawing. We let $\cset'(F)$ be the set of $d(F)/3$ innermost cycles. It is easy to verify that, if $F\neq F'$, then the cycles in $\cset'(F)$ and $\cset'(F')$ are disjoint. Therefore, the edges of $C$ participate in at least $\Omega(\sum_{F\in \fset}d(F))$ crossings. For every face $F$, we now cut through the cycles in $\cset(F)$ so that $F$ and $N(F)$ merge. This ensures that, by adding a small number of edges to $E'$, we decrease $\fset$ by at least factor $2$. The number of edges added to $E'$ is bounded by the number of crossings in which the edges of $C$ participate in the optimal drawing.

Once we finish this process, for every connected component $C$ of $H$, there is no bad face for $C$. However, we have lost the well-linkedness property.
In order to achieve the well-linkedness property, we consider terminals lying on a single face, and do a well-linked decomposition with respect to them. It is easy to verify that this will not create bad faces. We process every good face of the resulting components one by one until the desired well-linkedness property is achieved.

§ PRELIMINARIES

To be used later for locally non-interfering/non-interfering paths (for this the definition should be adapted). We may also keep it in prelims as a definition of crossing paths. Maybe we should also define a drawing of a path as a concatenation of images of its edges. We use it quite a bit.

Let $\gamma,\gamma'$ be two curves in the plane or on the sphere. We say that $\gamma$ and $\gamma'$ cross,  iff there is a disc $D$, whose boundary is a simple closed curve that we denote by $\beta$, such that:

* $\gamma\cap D$ is a simple open curve, whose endpoints we denote by $a$ and $b$;

* $\gamma'\cap D$ is a simple open curve, whose endpoints we denote by $a'$ and $b'$; and

* $a,a',b,b'\in \beta$, and they appear on $\beta$ in this circular order.

Given a graph $G$ embedded in the plane or on the sphere, we say that two paths $P,P'$ in $G$ cross iff their images cross. Similarly, we say that a path $P$ crosses a curve $\gamma$ iff the image of $P$ crosses $\gamma$.

By default, all logarithms are to the base of $2$. All graphs are finite, simple and undirected. Graphs with parallel edges are explicitly referred to as multi-graphs.

We follow standard graph-theoretic notation. Assume that we are given a graph $G=(V,E)$.

For a vertex $v\in V$, we denote by $\delta_G(v)$ the set of all  edges of $G$ that are incident to $v$.
For two disjoint subsets $A,B$ of vertices of $G$, we denote by $E_G(A,B)$ the set of all edges with one endpoint in $A$ and another in $B$.
For a subset $S\subseteq V$ of vertices, we denote by $E_G(S)$ the set of all edges with both endpoints in $S$, and we denote by $\out_G(S)$ the subset of edges of $E$ with exactly one endpoint in $S$, namely $\out_G(S)=E_G(S, V\!\setminus\! S)$.
We denote by $G[S]$ the subgraph of $G$ induced by $S$.
We sometimes omit the subscript $G$ if it is clear from the context.

We say that a graph $G$ is $\ell$-connected for some integer $\ell>0$, if there are $\ell$ vertex-disjoint paths between every pair of vertices in $G$.

Given a graph $G=(V,E)$, a drawing  $\phi$ of $G$ is an embedding of the graph into the plane, that maps every vertex to a point and every edge to a continuous curve that connects the images of its endpoints. We require that the interiors of the curves representing the edges do not contain the images of any of the vertices. We say that two edges cross at a point $p$, if the images of both edges contain $p$, and $p$ is not the image of a shared endpoint of these edges. We require that no three edges cross at the same point in a drawing of $\phi$.
We say that $\phi$ is a planar drawing of $G$ iff no pair of edges of $G$ crosses in $\phi$.
For a vertex $v\in V(G)$, we denote by $\phi(v)$ the image of $v$, and for an edge $e\in E(G)$, we denote by $\phi(e)$ the image of $e$ in $\phi$. For any subgraph $C$ of $G$, we denote by $\phi(C)$ the union of images of all vertices and edges of $C$ in $\phi$. For a path $P\subseteq G$, we sometimes refer to $\phi(P)$ as the image of $P$ in $\phi$. Note that a drawing of $G$ in the plane naturally defines a drawing of $G$ on the sphere and vice versa; we use both types of drawings.
Given a graph $G$ and a drawing $\phi$ of $G$ in the plane, we use $\cro(\phi)$ to denote the number of crossings in $\phi$. Let $\phi'$ be the drawing of $G$ that is a mirror image of $\phi$. We say that $\phi$ and $\phi'$ are identical drawings of $G$, and that their orientations are different. We sometime say that $\phi'$ is obtained by flipping the drawing $\phi$. If $\gamma$ is a simple closed curve in $\phi$ that intersects $G$ at vertices only, and $S$ is the set of vertices of $G$ whose images lie on $\gamma$, with $|S|\geq 3$, then we say that the circular orderings of the vertices of $S$ along $\gamma$ in $\phi$ and $\phi'$ are identical, but the orientations of the two orderings are different, or opposite.

Whitney [35] proved that every $3$-connected planar graph has a unique planar drawing.
Throughout, for a $3$-connected planar graph $G$, we denote by $\rho_G$ the unique planar drawing of $G$.

Problem Definitions.
The goal of the  problem is to compute a drawing of the input graph $G$ in the plane with smallest number of crossings.
The value of the optimal solution, also called the crossing number of $G$, is denoted by $\optcro(G)$.

We also consider a closely related problem called Crossing Number with Rotation System (). In this problem, we are given a multi-graph $G$, and, for every vertex $v\in V(G)$, a circular ordering $\oset_v$ of its incident edges. We denote by $\Sigma=\set{\oset_v}_{v\in V(G)}$ the collection of all such orderings, and we refer to $\Sigma$ as a rotation system for graph $G$.  We say that a drawing $\phi$ of $G$ respects the rotation system $\Sigma$ if the following holds: For every vertex $v\in V(G)$, let $\eta(v)$ be an arbitrarily small disc around $v$ in $\phi$. Then the images of the edges of $\delta_G(v)$ in $\phi$ must intersect the boundary of $\eta(v)$ in a circular order that is identical to $\oset_v$ (but the orientation of this ordering may be arbitrary). In the problem, the input is a multi-graph $G$ with a rotation system $\Sigma$, and the goal is to compute a drawing of $G$ in the plane that respects $\Sigma$ and minimizes the number of crossings.

is this needed?
If a crossing is caused by the intersection of the images of a pair of edges $e,e'$ (namely $\phi(e)$ and $\phi(e')$), then we say that the edges $e$ and $e'$ participate in the crossing, or the pair of edges $e$ and $e'$ cross.
We also say that an edge $e$ is crossed in a drawing $\phi$ if the edge $e$ participates in at least one crossing of $\phi$.
For any pair $E_1, E_2 \subseteq E$ of subsets of edges, we denote by $\cro_{\phi}(E_1, E_2)$ the number of crossings in $\phi$ in which the images of edges of $E_1$ intersect the images of edges of $E_2$.

Clearly, for each subset $E' \subseteq E$, $\cro(\phi)=\cro_{\phi}(E',E')+\cro_{\phi}(E',E\setminus E')+\cro_{\phi}(E\setminus E',E\setminus E')$.
Since at most two edges participate in a crossing, for disjoint subsets $E_1,\ldots,E_r$ of $E$, $\sum_{1\le i\le r}\cro_{\phi}(E,E_i)\le 2\cdot\cro(\phi)$.
For a subgraph $C$ of $G$, we denote $\cro_{\phi}(C)=\cro_{\phi}(E(C),E(C))$, or equivalently $\cro_{\phi}(C)=\cro(\phi(C))$. Similarly, for two subgraphs $C,C'$, we denote $\cro_{\phi}(C,C')=\cro_{\phi}(E(C),E(C'))$.

Faces and Face Boundaries.
Suppose we are given a planar graph $G$ and a drawing $\phi$ of $G$ in the plane. The set of faces of $\phi$ is the set of all connected regions of $\mathbb{R}^2\setminus \phi(G)$. We designate a single face of $\phi$ as the “outer”, or the “infinite” face.
The boundary $\delta(F)$ of a face $F$ is a subgraph of $G$ consisting of all vertices and edges of $G$ whose image is incident to $F$. Notice that, if graph $G$ is not connected, then boundary of a face may also be not connected. Unless $\phi$ has a single face, the boundary $\delta(F)$ of every face $F$ of $\phi$ must contain a simple cycle $\delta'(F)$ that separates $F$ from the outer face. We sometimes refer to graph $\delta(F)\setminus\delta'(F)$ as the inner boundary of $F$. Lastly, observe that, if $G$ is $2$-connected, then the boundary of every face of $\phi$ is a simple cycle.

Given a graph $G$ and a planar drawing $\phi$ of $G$, the set of faces of $\phi$ are defined to be the set of connected regions in $\mathbb{R}^2\setminus \phi(G)$, and we denote it by $\fset(\phi)$. Moreover, exactly one of these faces is infinite which we refer to as the outer face.

For each face $F\in \fset(\phi)$, the boundary of the face $F$ is defined as the set of vertices and edges that are incident to the face $F$, and we denote it by $\delta(F)$.  Note that if the graph is connected, the boundary of $F$ also forms a connected graph. We may also call it the full boundary to emphasize the contrast to the inner/outer boundary defined next.

For a face that is not the outer face, we define the outer boundary $\delta^{out}(F)\subseteq \delta(F)$ to be the simple cycle that separates the face $F$ from the outer face. In other words, if $D(F)$ denotes the closed disc whose boundary is $\delta^{out}(F)$, then $D(F)$ should contain $F$.
Note that if $G$ is $2$-connected, the boundary of each face $F\in \fset(\phi)$ is a simple cycle, i.e., $\delta(F)=\delta^{out}(F)$.
Moreover, we define the inner boundary as $\delta^{in}(F)$ to be the set of edges in $\delta(F)\setminus \delta^{out}(F)$, together with their endpoint vertices.

Finally, for a connected graph, we can define for each vertex $v$ on the boundary $\delta(F)$, the point of contact of $v$ to be the vertex on the outer boundary with minimum distance to $v$.

Bridges and Extensions of Subgraphs.
Let $G$ be a graph, and let $C\subseteq G$ be a subgraph of $G$. A bridge for $C$ in graph $G$ is either (i) an edge $e=(u,v)\in E(G)$ with $u,v\in V(C)$ and $e\not \in E(C)$; or (ii) a connected component of $G\setminus V(C)$.

We denote by $\rset_G(C)$ the set of all bridges for $C$ in graph $G$. For each bridge $R\in \rset_G(C)$, we define the set of vertices $L(R)\subseteq V(C)$, called the legs of $R$,
as follows. If $R$ consists of a single edge $e$, then $L(R)$ contains the endpoints of $e$. Otherwise, $L(R)$ contains all vertices $v\in V(C) $, such that $v$ has a neighbor that belongs to $R$.

Next, we define an extension of the subgraph $C\subseteq G$, denoted by $X_G(C)$. The extension contains, for every bridge $R\in \rset_G(C)$, a tree $T_R$, that is defined as follows. If $R$ is a bridge consisting of a single edge $e$, then the corresponding tree $T_R$ only contains the edge $e$. Otherwise,
let $R'$ be the subgraph of $G$ consisting of the graph $R$, the vertices of $L(R)$, and all edges of $G$ connecting vertices of $R$ to vertices of $L(R)$.
We let $T_R\subseteq R'$ be a tree, whose leaves are precisely the vertices of $L(R)$.
Note that such a tree exists because graph $R$ is connected, and it can be found efficiently.
We let the extension of $C$ in $G$ be $X_G(C)=\set{T_R\mid R\in \rset_G(C)}$.

Sparsest Cut.
Suppose we are given a graph $G=(V,E)$, and a subset $\tset\sse V$ of $k$ vertices, called terminals.
The sparsity of a cut $(S,\nots)$ in $G$ is $\Phi(S)=\frac{|E(S,\nots)|}{\min\set{|S\cap \tset|, |\nots\cap \tset|}}$, and the value of the sparsest cut in $G$ is defined to be:
$\Phi(G)=\min_{S\subset V}\set{\Phi(S)}$.
The goal of the sparsest cut problem is to find a cut of minimum sparsity. Arora, Rao and Vazirani [3] have shown an $O(\sqrt {\log n})$-approximation algorithm for the sparsest cut problem. We denote this algorithm by , and its approximation factor by $\alphasc(n)=O(\sqrt{\log n})$.

Sparsest Cut and Well-Linkedness.

Suppose we are given a graph $G=(V,E)$, and a subset $\Gamma\sse V$ of its vertices. We say that a cut $(X,Y)$ in $G$ is a valid $\Gamma$-cut iff $X\cap \Gamma,Y\cap \Gamma\neq \emptyset$. The sparsity of a valid $\Gamma$-cut $(X,Y)$ is $\frac{|E(X,Y)|}{\min\set{|X\cap \Gamma|, |Y\cap \Gamma|}}$.

In the Sparsest Cut problem, given a graph $G$ and a subset $\Gamma$ of its vertices, the goal is to compute a valid $\Gamma$-cut of minimum sparsity. Arora, Rao and Vazirani [3] have shown an $O(\sqrt {\log n})$-approximation algorithm for the sparsest cut problem. We denote this algorithm by , and its approximation factor by $\alphasc(n)=O(\sqrt{\log n})$.

We say that a set $\Gamma$ of vertices of $G$ is $\alpha$-well-linked in $G$, iff the value of the sparsest cut in $G$ with respect to $\Gamma$ is at least $\alpha$.

Let $G$ be a graph, and let $S$ be a subset of vertices of $G$, and let $0<\alpha<1$, such that $S$ is $\alpha$-well-linked.
We now define the sparsest cut and the concurrent flow instances corresponding to $S$ as follows. For each edge in $\out(S)$, we sub-divide the edge by adding a new vertex $t_e$ to it. Let $G'$ denote the resulting graph and let $T$ denote the set of all vertices $t_e$ for $e\in \out_G(S)$. Consider the graph $H=G'[S]\cup \out_{G'}(S)$. We can naturally define an instance of the non-uniform sparsest cut problem on $H$ where the set of terminals is $T$. We then have the following well-known observation.

Let $G$, $S$, $H$ and $T$ be defined as above, and let $0<\alpha <1$, such that $S$ is $\alpha$-well-linked. Then every pair of vertices in $T$ can send one flow unit to each other in $H$, such that the maximum congestion on any edge is at most $\beta(n)|T|/\alpha$. Moreover if $M$ is any partial matching on the vertices of $T$, then we can send one flow unit between every pair $(u,v)\in M$ in graph $H$, with maximum congestion at most $2\beta(n)/\alpha$.

The following theorem shows the technique of well-linked decomposition, which has been used extensively in graph algorithms (e.g., see <cit.>).

There is an efficient algorithm, that, given any connected graph $G$ and a subset $T\subseteq V(G)$ of its vertices with $|T|=k$, computes a collection $\set{G_1,\ldots,G_r}$ of connected subgraphs of $G$, such that:

* for each $1\le i\le r$, denote $V_i=V(G_i)$, then $(V_1,\ldots,V_r)$ forms a partition of $V(G)$;

* for each $1\le i\le r$, denote $T_i=T\cap V_i$, then the subset $T_i\cup \Gamma(V_i)$ of vertices is $\Omega(\frac{1}{\log^{3/2}k\cdot\log\log k})$-well-linked in $G_i$; and

* $\sum_{1\le i\le r}|\out(V_i)|\le 0.01 k$, and $\sum_{1\le i\le r}|T_i\cup \Gamma(V_i)|\le 1.01 k$.

§ HIGH-LEVEL OVERVIEW

In this section we provide a high-level overview of the proofs of our main results, and state the main theorems from which the proofs are derived.
As in previous work, we start by considering a special case of the problem, where the input graph $G$ is $3$-connected. This special case seems to capture the main technical challenges of the whole problem, and the extension to non-$3$-connected graphs is relatively easy and follows the same framework as in previous work [12].
We start by defining several central notions that our proof uses.

§.§ Acceptable Clusters and Decomposition into Acceptable Clusters

In this section we define acceptable clusters and decomposition into acceptable clusters. These definitions are central to all our results.
Let $G$ be an input graph on $n$ vertices of maximum degree at most $\Delta$; we assume that $G$ is $3$-connected. Let $\hat E$ be any planarizing set of edges for $G$, and let $H=G\setminus \hat E$. Let $\Gamma\subseteq V(G)$ be the set of all vertices that serve as endpoints of edges in $\hat E$; we call the vertices of $\Gamma$ terminals. We will define a set $A$ of fake edges; for every fake edge $e\in A$, both endpoints of $e$ must lie in $\Gamma$. We emphasize that the edges of $A$ do not necessarily lie in $H$ or in $G$; in fact we will use these edges in order to augment the graph $H$.

We denote by $\cset$ the set of all connected components of graph $H\cup A$, and we call elements of $\cset$ clusters.  For every cluster $C\in \cset$, we denote by $\Gamma(C)=\Gamma\cap V(C)$ the set of all terminals that lie in $C$. We also denote by $A_C=A\cap C$ the set of all fake edges that lie in $C$.

We say that a cluster $C\in \cset$ is a type-1 acceptable cluster iff:

* $A_C=\emptyset$; and

* $|\Gamma(C)|\leq \mu$ for $\mu=512\Delta\alphasc(n)\log_{3/2} n=O(\Delta\log^{1.5}n)$  (recall that $\alphasc(n)=O(\sqrt{\log n})$ is the approximation factor of the algorithm $\algsc$ for the sparsest cut problem).

Consider now some cluster $C\in \cset$, and assume that it is $2$-connected. For a pair $(u,v)$ of vertices of $C$, we say that $(u,v)$ is a $2$-separator for $C$ iff the graph $C\setminus\set{u,v}$ is not connected. We denote by $S_2(C)$ the set of all vertices of $C$ that participate in $2$-separators, that is,  a vertex $v\in C$ belongs to $S_2(C)$ iff there is another vertex $u\in C$ such that $(v,u)$ is a $2$-separator for $C$.
Next, we define type-2 acceptable clusters.

We say that a cluster $C\in \cset$ is a type-2 acceptable cluster with respect to its drawing $\psi'_C$ on the sphere if the following conditions hold:

* (Connectivity): $C$ is a simple $2$-connected graph, and $|S_2(C)|\leq O(\Delta|\Gamma(C)|)$. Additionally, graph $C\setminus A_C$ is a $2$-connected graph.

* (Planarity): $C$ is a planar graph, and the drawing $\psi'_C$ is planar. We denote by  $\psi_{C\setminus A_C}$ the drawing of $C\setminus A_C$ is induced by $\psi'_C$.

* (Bridge Consistency Property): for every bridge $R\in \rset_{G}(C\setminus A_C)$, there is a face $F$ in the  drawing $\psi_{C\setminus A_C}$ of $C\setminus A_C$,
such that all vertices of $L(R)$ lie on the boundary of $F$; and

* (Well-Linkedness of Terminals): the set $\Gamma(C)$ of terminals is $\alpha$-well-linked in $C\setminus A_C$, for $\alpha=\frac{1}{128\Delta \alphasc(n)\log_{3/2} n}=\Theta \left (\frac{1}{\Delta \log^{1.5}n}\right )$.

Let $\cset_1\subseteq \cset$ denote the set of all type-1 acceptable clusters.
For a fake edge $e=(x,y)\in A$, an embedding of $e$ is a path $P(e)\subseteq G$ connecting $x$ to $y$. We will compute an embedding of all fake edges in $A$ that has additional useful properties summarized below.

A legal embedding of the set $A$ of fake edges is a collection $\pset(A)=\set{P(e)\mid e\in A}$ of paths in $G$, such that the following hold.

* For every edge $e=(x,y)\in A$, path $P(e)$ has endpoints $x$ and $y$, and moreover, there is a type-1 acceptable cluster $C(e)\in \cset_1$ such that $P(e)\setminus\set{x,y}$ is contained in $C(e)$; and

* For any pair $e,e'\in A$ of distinct edges, $C(e)\neq C(e')$;

Note that from the definition of the legal embedding, all paths in $\pset(A)$ must be mutually internally disjoint.

Finally, we define a decomposition of a graph $G$ into acceptable clusters; this definition is central for the proof of our main result.

A decomposition of a graph $G$ into acceptable clusters consists of:

* a planarizing set $\hat E\subseteq E(G)$ of edges of $G$;

* a set $A$ of fake edges (where the endpoints of each fake edge are terminals with respect to $\hat E$);

* a partition $(\cset_1,\cset_2)$ of all connected components (called clusters) of the resulting graph $(G\setminus \hat E)\cup A$ into two subsets, such that every cluster $C\in \cset_1$ is a type-1 acceptable cluster;

* for every cluster $C\in \cset_2$, a planar drawing $\psi'_C$ of $C$ on the sphere, such that $C$ is a type-2 acceptable cluster with respect to $\psi'_C$; and

* a legal embedding $\pset(A)$ of all fake edges.

We denote such a decomposition by $\dset=\left (\hat E,A,\cset_1,\cset_2,\set{\psi'_C}_{C\in \cset_2},\pset(A)\right )$.

The proof of Theorem <ref> is divided into two parts.
In the first part (Section <ref> and Section <ref>), we will show the proof of Theorem <ref>, assuming that the input $G$ is $3$-connected.
In the second part (Section <ref>), we will complete the proof of Theorem <ref> by showing how to handle non-$3$-connected graphs.
We now state the two main theorems of the first part.

Our first result is the following theorem, whose proof appears in Section <ref>, that allows us to compute a decomposition of the input graph $G$ into acceptable clusters. This result is one of the main technical contributions of our work.

There is an efficient algorithm, that, given a $3$-connected $n$-vertex graph $G$ with maximum vertex degree at most $\Delta$ and a planarizing set $E'$ of edges for $G$, computes a decomposition  $\dset=\left ( E'',A,\cset_1,\cset_2,\set{\psi'_C}_{C\in \cset_2},\pset(A)\right )$ of $G$ into acceptable clusters, such that $E'\subseteq  E''$ and $| E''|\leq O((| E'|+\optcro(G))\cdot\poly(\Delta\log n))$.

§.§ Canonical Drawings

In this subsection, we assume that we are given a $3$-connected $n$-vertex graph $G$ with maximum vertex degree at most $\Delta$, and a decomposition  $\dset=\left ( E'',A,\cset_1,\cset_2,\set{\psi'_C}_{C\in \cset_2},\pset(A)\right )$ of $G$ into acceptable clusters. Next, we define drawings of $G$ that are “canonical” with respect to the clusters in the decomposition.
For brevity of notation, we refer to type-1 and type-2 acceptable clusters as type-1 and type-2 clusters, respectively.

Intuitively, in each such canonical drawing, we require that, for every type-2  cluster $C\in \cset_2$, the edges of $C\setminus A_C$ do not participate in any crossings, and for every type-1 acceptable cluster $C\in \cset_1$, the edges of $C$ only participate in a small number of crossings (more specifically, we will define a subset $E^{**}(C)$ of edges for each cluster $C\in \cset_1$ that are allowed to participate in crossings). We then show that any drawing of $G$ can be transformed into a drawing that is canonical with respect to all clusters in $\cset_1\cup \cset_2$, while only slightly increasing the number of crossings. This is sufficient in order to complete the proof of Theorem <ref>, by adding to $E''$ the set $\bigcup_{C\in \cset_1}E^{**}(C)$ of edges. However, in order to be able to reduce the problem to the problem, as required in Theorem <ref>, we need stronger properties. We will define, for every type-1 cluster $C\in \cset_1$, a fixed drawing $\psi_C$, and we will require that, in the final drawing of $G$, the induced drawing of each such cluster $C$ is precisely $\psi_C$. For every type-2 cluster $C\in \cset_2$, we have already defined a drawing $\psi_{C\setminus A_C}$ of $C\setminus A_C$ – the drawing of $C\setminus A_C$ that is induced by the drawing $\psi'_C$ of $C$. We will require that the drawing of $C\setminus A_C$ that is induced by the final drawing of $G$ is precisely $\psi_{C\setminus A_C}$.
Additionally, for each cluster $C\in \cset_1$, and for each bridge $R\in \rset_G(C)$, we will define a disc $D(R)$ in the drawing $\psi_C$ of $C$, and we will require that all vertices and edges of $R$ are drawn inside $D(R)$ in the final drawing of $G$.
Similarly, for each type-2 acceptable cluster $C\in \cset_2$, for every bridge $R\in \rset_G(C\setminus A_C)$, we define a disc $D(R)$  in the drawing $\psi_{C\setminus A_C}$ of $C\setminus A_C$, and we will require that all vertices and edges of $R$ are drawn inside $D(R)$ in the final drawing of $G$.

This will allow us to fix the locations of the components of $\cset_1\cup \cset_2$ with respect to each other (that is, for each pair $C,C'\in \cset_1\cup \cset_2$ of clusters, we will identify a face $F$ in the drawing $\psi_{C\setminus A_C}$ of $C\setminus A_C$, and a face $F'$ in the drawing $\psi_{C'\setminus A_{C'}}$ of $C'\setminus A_{C'}$, such that, in the final drawing $\phi$ of the graph $G$, graph $C'\setminus A_{C'}$ is drawn inside the face $F$ (of the drawing of $C\setminus A$ induced by $\phi$, which is identical to $\psi_{C\setminus A_C}$), and similarly graph $C\setminus A_C$ is drawn inside the face $F'$).

Before we continue, it would be convenient for us to ensure that, for every type-1 cluster $C\in \cset_1$, the vertices of $\Gamma(C)$ have degree $1$ in $C$, and degree $2$ in $G$; it would also be convenient for us to ensure that no edge of $ E''$ connects two vertices that lie in the same cluster.
In order to ensure these properties, we subdivide some edges of $G$. Specifically, if $e=(u,v)\in E''$ is an edge with $u,v\in C$, for some cluster $C\in \cset_1\cup \cset_2$, then we subdivide the edge $(u,v)$ with two vertices, replacing it with a path $(u,u',v',v)$. The edges $(u,u')$ and $(v',v)$ are then added to set $E''$ instead of the edge $(u,v)$, and we add a new cluster to $\cset_1$, that consists of the vertices $u',v'$, and the edge $(u',v')$. This transformation ensures that no edge of $E''$ connects two vertices that lie in the same cluster.
Consider now any type-1 cluster $C\in \cset_1$. For every edge $e=(u,v)\in E''$ with $u\in V(C)$ and $v\not\in V(C)$, we subdivide the edge with a new vertex $u'$, thereby replacing the edge with the path $(u,u',v)$. Vertex $u'$ and edge $(u,u')$ are added to the cluster $C$, while edge $(u',v)$ replaces the edge $(u,v)$ in set $E''$. Note that $u'$ now becomes a terminal, and, once all edges of $E''$ that are incident to the vertices of $C$ are processed, $u$ will no longer be a terminal. Abusing the notation, the final cluster that is obtained after processing all edges of $E''$ incident to $V(C)$ is still denoted by $C$. Notice that now the number of terminals that lie in $C$ may have grown by at most a factor $\Delta$, and so $|\Gamma(C)|\leq \mu\Delta$ must hold. Abusing the notation, we will still refer to $C$ as a type-1 acceptable cluster, and we will continue to denote by $\cset_1$ the set of all such clusters in the decomposition. Observe that this transformation ensures that every vertex of $\Gamma(C)$ has degree $1$ in $C$ and degree $2$ in $G$. Once every cluster $C\in \cset_1$ is processed in this manner, we obtain the final graph $G'$. Observe that $|E''|$ may have increased by at most a constant factor.
Notice also that, for every fake edge $e=(x,y)\in A$, the endpoints of $e$ remain terminals in $\Gamma$, and the path $P(e)\in \pset$ that was used as a legal embedding of the edge $e$ can be converted into a path $P'(e)$ embedding $e$ in the new graph $G'$, by possibly subdividing the first and the last edge of $P(e)$ if needed. If $C(e)\in \cset_1$ is the type-$1$ cluster with $P(e)\setminus\set{x,y}\subseteq C(e)$, then the new vertices that (possibly) subdivide the first and the last edge of $P(e)$ lie in the new cluster $C'(e)$ corresponding to $C(e)$, so $P'(e)\setminus\set{x,y}\subseteq C'(e)$ continues to hold. The resulting path set $\pset'=\set{P'(e)\mid e\in A}$ is a legal embedding of the set of fake edges into $G'$.
Lastly, observe that any drawing of $G'$ on the sphere immediately gives a drawing of $G$ with the same number of crossings.
Therefore, to simplify the notation, we will denote the graph $G'$ by $G$ and $\pset'$ by $\pset$ and we will assume that the decomposition $\dset$ of $G$ into acceptable clusters has the following two additional properties:

* For every edge $e\in E''$, the endpoints of $e$ lie in different clusters of $\cset_1\cup \cset_2$;  and

* For every type-1 cluster $C\in \cset_1$, for every terminal $t\in \Gamma(C)$, the degree of $t$ in $C$ is $1$, and its degree in $G$ is $2$.

We now proceed to define canonical drawings of the graph $G$ with respect to the clusters of $\cset_1\cup \cset_2$.

§.§.§ Canonical Drawings for Type-2 Acceptable Clusters

Consider any type-2 cluster $C\in \cset_2$. Recall that the decomposition $\dset$ into acceptable clusters defines a planar drawing $\psi'_C$ of $C$ on the sphere, that induces a planar drawing $\psi_{C\setminus A_C}$ of $C\setminus A_C$ on the sphere. Recall that the Bridge Consistency Property of  type-2 acceptable clusters ensures that, for every bridge $R\in \rset_{G}(C\setminus A_C)$, there is a face $F$ of the drawing $\psi_{C\setminus A_C}$, such that the vertices of $L(R)$ lie on the boundary of $F$ (we note that face $F$ is not uniquely defined; we break ties arbitrarily). Since graph $C\setminus A_C$ is 2-connected, the boundary of face $F$ is a simple cycle, whose image is a simple closed curve. We denote by $D(R)$ the disc corresponding to the face $F$, so the boundary of $D(R)$ is the simple closed curve that serves as the boundary of the face $F$.

Notice that the resulting set $\set{D(R)}_{R\in \rset_G(C\setminus A_C)}$ of discs has the following properties:

* If $R\neq R'$ are two distinct bridges in $\rset_G(C\setminus A_C)$, then either $D(R)=D(R')$, or $D(R)\cap D(R')$ only contains points on the boundaries of the two discs;  and

* For every bridge $R\in \rset_G(C\setminus A_C)$, the vertices of $L(R)$ lie on the boundary of $D(R)$ in the drawing $\psi_{C\setminus A_C}$.

We are now ready to define canonical drawings with respect to type-$2$ clusters.

Let $\phi$ be any drawing of the graph $G$ on the sphere. We say that the drawing $\phi$ is canonical with respect to a type-$2$  cluster $C\in \cset_2$ iff:

* the drawing of $C\setminus A_C$ induced by $\phi$ is identical to $\psi_{C\setminus A_C}$ (but its orientation may be different);

* the edges of $C\setminus A_C$ do not participate in any crossings in $\phi$; and

* for every bridge $R\in \rset_{G}(C\setminus A_C)$, all vertices and edges of $R$ are drawn in the interior of the disc $D(R)$ (that is defined with respect to the drawing $\psi_{C\setminus A_C}$ of $C\setminus A_C$).

§.§.§ Canonical Drawings for Type-1 Acceptable Clusters

For convenience, we denote $\cset_1=\set{C_1,\ldots,C_q}$.
We fix an arbitrary optimal drawing $\phi^*$ of the graph $G$. For each $1\leq i\leq q$, we denote by $\chi_i$ the set of all crossings $(e,e')$ such that either $e$ or $e'$ (or both) are edges of $E(C_i)$.
The following observation is immediate.

$\sum_{i=1}^q|\chi_i|\leq 2\cdot\cro(\phi^*)=2\cdot\optcro(G)$.

We use the following theorem in order to fix a drawing of each type-$1$ acceptable cluster $C_i$; the proof appears in Section <ref>.

There is an efficient algorithm that, given a type-$1$ cluster $C_i\in \cset_1$, computes a drawing $\psi_{C_i}$ of $C_i$ on the sphere with $ O\left((|\chi_i|+1)\cdot \poly(\Delta\log n)\right)$ crossings, together with a set $E^*(C_i)\subseteq E(C_i)$ of at most $ O\left((|\chi_i|+1)\cdot \poly(\Delta\log n)\right)$ edges, such that graph $C_i\setminus E^*(C_i)$ is connected, and the drawing of $C_i\setminus E^*(C_i)$ induced by $\psi_{C_i}$ is planar.  Additionally, the algorithm computes, for every bridge $R\in \rset_{G}(C_i)$, a closed disc $D(R)$, such that:

* the vertices of $L(R)$ are drawn on the boundary of $D(R)$ in $\psi_{C_i}$;

* the interior of $D(R)$ is disjoint from the drawing $\psi_{C_i}$; and

* for every pair $R,R'\in \rset_G(C_i)$ of bridges, either $D(R)=D(R')$, or $D(R)\cap D(R')=\emptyset$.

Consider now some cluster $C_i\in \cset_1$. Let $e_i=(x_i,y_i)\in A$ be the unique fake edge that is embedded into $C_i$;
in other words, if $P(e_i)\in \pset(A)$ is the path into which edge $e_i$ is embedded, then $P(e_i)\setminus\set{x_i,y_i}\subseteq C_i$.
If no such edge exists, $e_i$ is undefined. We set $C_i'=C_i\cup \set{e_i}$, and we let $x'_i,y'_i$ be the endpoints of the path $P(e_i)\setminus \set{x_i,y_i}$.

Recall that edge $e_i$ belongs to some type-2 acceptable cluster $C$, which is a connected graph. Therefore, $C$ must also contain a path $P'_i$ connecting $x_i$ to $y_i$.
Some edges on path $P'_i$ may be fake edges that lie in $A$. However, for each such fake edge $e\in P'_i$, its embedding $P(e)\in \pset(A)$ must be disjoint from $C_i$. By replacing each fake edge $e\in P'_i$ with its embedding $P(e)\in \pset(A)$, we obtain a path $P_i\subseteq G\setminus C_i$ connecting $x_i$ to $y_i$.

Therefore, there must be a bridge $R_i\in \rset_{G}(C_i)$ that contains the path $P_i$, with $x'_i,y'_i\in L(R_i)$.

Recall that the extension $X_{G}(C_i)$ (that is defined in Section <ref>) is a collection of trees $\set{T_R\mid R\in \rset_{G}(C_i)}$.
We denote by $C^+_i$ the graph obtained by the union of $C_i'$ and all trees in $X_{G}(C_i)$, namely $C^+_i=C_i'\cup \left(\bigcup_{R\in \rset_{G}(C_i)}T_R\right )$.
For every tree $T_R\in X_{G}(C_i)$, we denote by $\tilde E(R)$ the set of all edges of $T_R$ that are incident to the vertices of $L(R)$.  We use the following theorem in order to fix a drawing of each type-$1$ acceptable cluster $C_i$; the proof appears in Section <ref>.

There is an efficient algorithm that computes, for every cluster $C_i\in \cset_1$, a subset $E^*(C_i)$ of at most $O(|\chi_i|\cdot\poly(\mu \Delta \log n))$ edges of $C_i$, recall what $\mu$ is here? and a drawing $\psi_i$ of $C_i^+$ on the sphere with $ O\!\left(|\chi_i|\cdot \poly(\mu\Delta\log n)\right)$ crossings, such that the images of the edges in $E(C_i)\setminus E^*(C_i)$ do not participate in any crossings. Additionally, the algorithm computes, for every bridge $R\in \rset_{G}(C_i)$, a closed disc $D(R)$, such that:

* for every vertex and edge of $C_i$, its image in $\psi_i$ is disjoint from $D(R)$;

* all vertices and edges of $T_R\setminus \tilde E(R)$ are drawn in the interior of $D(R)$;

* for every edge of $\tilde E(R)$, its image intersects the boundary of the disc $D(R)$ at a single point;

* the discs in $\set{D(R)}_{R\in \rset_{G}(C_i)}$ are mutually disjoint; and

* the image of the edge $e_i$ has a non-empty intersection with the boundary of the disc $D(R_i)$, and this intersection is a contiguous curve; it does not intersect the interior of $D(R_i)$, and it does not intersect any other disc $D(R')$ for any $R'\in \rset_G(C_i)\setminus\set{R_i}$.

Note that in particular, Properties (<ref>) and (<ref>) also hold for the discs in $\set{D(R)}_{R\in \rset_G(C)}$.

For each type-1 cluster $C_i\in \cset_1$, let $E^{**}(C_i)\subseteq E(C_i)$ be the set of all edges of $C_i$ that participate in crossings in  $\psi_{C_i}$. Clearly, $|E^{**}(C_i)|\leq O(\cro(\psi_{C_i}))\leq O((|\chi_i|+1)\poly(\Delta\log n))$.
Let $E^*=\bigcup_{C_i\in \cset_1}E^{**}(C_i)$. Then, from Observation <ref> and Theorem <ref>:

\[\begin{split}
|E^*|& \leq \sum_{C_i\in \cset_1}O\!\left((|\chi_i|+1)\cdot \poly(\Delta\log n)\right)\\
&\leq O\left ((\optcro(G)+|E''|) \poly(\Delta\log n)\right )\\
&\leq O\left ((\optcro(G)+|E'|) \poly(\Delta\log n)\right ).
\end{split}
\]

We now define canonical drawings with respect to type-1 clusters.

Let $\phi$ be any drawing of the graph $G$ on the sphere, and let $C_i\in \cset_1$ be a type-$1$ cluster. We say that $\phi$ is a canonical drawing with respect to $C_i$, iff:

* the drawing of $C_i$ induced by $\phi$ is identical to $\psi_{C_i}$ (but orientation of the two drawings may be different); and

* for every bridge $R\in \rset_{G}(C_i)$, all vertices and edges of $R$ are drawn in the interior of the disc $D(R)$ (that is defined with respect to the drawing $\psi_{C_i}$ of $C_i$).

Notice that the definition implies that the only edges of $C_i$ that participate in crossings of $\phi$ are the edges of $E^{**}(C_i)$.

§.§.§ Obtaining a Canonical Drawing

Our next result shows that there exists a near-optimal drawing of the graph $G$ that is canonical with respect to all clusters.
The proof of the following theorem appears in Section <ref>.

There is an efficient algorithm, that, given, as input:

* an $n$-vertex graph $G$ of maximum vertex degree at most $\Delta$;

* an arbitrary drawing $\phi$ of $G$;

* a decomposition $\dset=\left ( E'',A,\cset_1,\cset_2,\set{\psi_{C}}_{C\in \cset_2},\pset(A)\right )$ of $G$ into acceptable clusters for which Properties (<ref>) and  (<ref>) hold;

* a drawing $\psi_{C_i}$ and an edge set $E^*(C_i)$ for each cluster $C_i\in \cset_1$ as defined above; and

* for each cluster $C\in \cset_1\cup \cset_2$,  a collection $\set{D(R)}_{R\in \rset_G(C\setminus A_C)}$ of discs on the sphere with Properties (<ref>) and (<ref>);

computes a drawing $\phi'$ of $G$ on the sphere with $O\left ((|E''|+\cro(\phi))\cdot\poly(\Delta \log n)\right)$ crossings, such that $\phi'$ is canonical with respect to every cluster $C\in \cset_1\cup \cset_2$.

We note that for our purposes, an existential variant of the above theorem, that shows that a drawing $\phi'$ with the required properties exists, is sufficient. We provide the proof of the stronger constructive result in case it may be useful for future work on the problem.

§.§ Completing the Proof of Theorem <ref> for $3$-Connected Graphs

Notice that Theorem <ref> concludes the proof of Theorem <ref> for the special case where $G$ is a $3$-connected graph. Indeed, given a $3$-connected graph $G$ and a planarizing set $E'$ of its edges, we use Theorem  <ref> to compute a decomposition  $\dset=\left ( E'',A,\cset_1,\cset_2,\{\psi_C\}_{C\in \cset_2},\pset(A)\right )$ of $G$ into acceptable clusters, such that $E'\subseteq  E''$ and $| E''|\leq O((| E'|+\optcro(G))\cdot\poly(\Delta\log n))$. Next, we apply Theorem <ref> to each type-1 cluster $C_i\in \cset_1$, to obtain the set $E^{**}(C_i)$ of edges, the drawing $\psi_{C_i}$ of $C_i$, and the discs $D(R)$ for all bridges $R\in \rset_G(C_i)$. Let $E^*=\bigcup_{C_i\in \cset_1}E^{**}(C_i)$, so $|E^*|\leq O\left ((\optcro(G)+|E'|) \poly(\Delta\log n)\right )$, as observed above. The final output of the algorithm is the set $E''\cup E^*$ of edges.
Observe that  $|E''\cup E^*|\leq O((| E'|+\optcro(G))\cdot\poly(\Delta\log n))$, as required. Moreover, by using Theorem <ref> with the optimal drawing $\phi^*$ of $G$, we conclude that there exists a drawing $\phi'$ of $G$ with $O\left ((|E'|+\optcro(G))\cdot\poly(\Delta \log n)\right )$ crossings, that is canonical with respect to all clusters in $\cset_1\cup \cset_2$. In particular, the only edges that may participate in crossings in $\phi'$ are edges of $E''\cup E^*$.

There is an efficient algorithm, that, given an $n$-vertex graph $G$, a planarizing set $E''$ of its edges, a partition $(\cset_1,\cset_2)$ of all the connected components of the resulting graph $H=G\setminus E''$ into two subsets, a legal set $A_C$ of fake edges for each component $C\in \cset_2$, together with an embedding $\pset(A_C)$ of the edges in $A_C$ into $G$, such that (i) each cluster $C\in \cset_1$ is a type-1 acceptable cluster;
(ii) For each cluster $C\in \cset_2$, $(C,A_C)$ is a type-2 acceptable cluster; and
(iii) all paths in set $\bigcup_{C\in \cset_2}\pset(A_C)$ are mutually internally disjoint, together with an optimal drawing $\phi$ of $G$, computes a drawing $\phi'$ of $G$ with $O(\optcro(G)\cdot\poly(\Delta \log n))$ crossings, such that $\phi'$ is canonical with respect to every cluster $C\in \cset_1\cup \cset_2$.

We claim that the proof of Theorem <ref> will conclude the proof of Theorem <ref>. In fact, we simply set $E'''=E''\cup(\bigcup_{C_i\in \cset_1}E^*_i)$. Since $\sum_{C_i\in \cset_1}|E^*_i|=O(\optcro(G)\cdot \poly(\mu\Delta\log n))$, we get that $|E'''|=O(\optcro(G)+|E''|)\poly(\mu\Delta\log n)$. From the definition of canonical drawing and the definition of $E^*_i$, the drawing $\phi'$ obtained from Theorem <ref> is in $\Phi_{E'''}(G)$.

There is an efficient randomized algorithm, that, given a $3$-connected graph with maximum vertex degree $\Delta$, and a decomposition $\dset=\left (E'',\cset_1,\cset_2,\bigcup_{C\in \cset_2}A_C,\bigcup_{C\in \cset_2}\pset(A_C)\right )$ of $G$ into acceptable clusters, computes a planarizing edge set $E'''\subseteq E(G)$, such that

* $E''\subseteq E'''$;

* $|E'''|\leq O((|E'|+\optcro(G))\cdot\poly(\Delta\log n))$; and

* there is a drawing of $G$ in $\Phi_{E'''}(G)$ with at most $O(\optcro(G)\cdot\poly(\Delta\log n))$ crossings.

§.§ Extension to General Graphs

In Section <ref> we show how to extend the above proof of Theorem <ref>  to general graphs, that are not necessarily $3$-connected. The extension builds on techniques that were introduced in [12]. Additionally, in Section <ref>, we prove the following theorem, that provides a black-box reduction from the problem of approximating in general graphs using paradigm $\Pi'$, to the problem of approximating in $3$-connected graphs, using the same paradigm.

Suppose there exists an efficient (possibly randomized) algorithm, that, given a $3$-connected $n$-vertex graph $G$ with maximum vertex degree $\Delta$, and a planarizing set $E'$ of its edges, computes a drawing of $G$ with at most $f(n,\Delta)\cdot(\optcro(G)+|E'|)$ crossings, for any function $f$ that is monotonously increasing in both $n$ and $\Delta$.
Then there exists an efficient (possibly randomized) algorithm that, given a (not necessarily 3-connected) graph $\hat{G}$ on $n$ vertices with maximum vertex degree $\Delta$,  and a planarizing set $\hat{E}'$ of its edges, computes a drawing of $\hat G$ with the number of crossings bounded by  $O\left( f(n,\Delta)\cdot (\optcro(\hat G)+|\hat E'|)\cdot \poly(\Delta\log n)\right)$.

§.§ Reduction to Crossing Number with Rotation System – Proof of Theorem <ref>

In this section we provide a reduction from in $3$-connected graphs to , completing the proof of Theorem <ref> in the case where the input graph $G$ is $3$-connected.
We extend this proof to general graphs in Section <ref>.
Recall that Kawarabayashi and Sidiropoulos [22] provide an efficient $O(\poly(\Delta\log n))$-approximation algorithm for the problem. Since, for every graph $G$, there is a planarizing set $E^*$ containing at most $\optcro(G)$ edges, we can use their algorithm in order to compute, for the input graph $G$, a planarizing edge set $E'$ of cardinality $O(\optcro(G)\cdot\poly(\Delta\log n))$. We then use Theorems <ref> and <ref> to compute another  planarizing edge set $E''$ of cardinality $O(\optcro(G)\cdot\poly(\Delta\log n))$ for $G$, the collection $\cset=\cset_1\cup \cset_2$ of clusters, together with their drawings $\psi_C$, and we use families $\set{D(R)}_{R\in \rset_G(C)}$ of discs for all $C\in \cset$ that we have computed. We will not need fake edges anymore, so for every type-2 cluster $C\in \cset_2$, we let $C'=C\setminus A_C$, and we let $\psi_{C'}$ be the planar drawing of $C'$ that was used in the definition of the canonical drawing. For a type-1 cluster $C\in \cset_1$, consider the drawing $\psi_C$ of $C$ given by Theorem <ref>. We let $C'$ be a graph obtained from $C$, by placing a vertex on every crossing of a pair of edges in $\psi_C$. Therefore, graph $C'$ is planar, and we denote by $\psi_{C'}$ its planar drawing that is induced by $\psi_C$. We still denote by $\Gamma(C')$ the set of all vertices of $C'$ that serve as endpoints of the edges of $E''$. Consider the graph $G'$, that is obtained by taking the union of all clusters in $\set{C'\mid C\in \cset}$ and the edges in $E''$. Suppose we compute a drawing $\phi$ of $G'$ with $z$ crossings, such that the only edges that participate in the crossings are the edges of $E''$, and for every cluster $C\in \cset$, the drawing of $C'$ induced by $\phi$ is identical to $\psi_{C'}$. Then we can immediately obtain a drawing $\phi'$ of $G$ with $O(z+\optcro(G)\poly(\Delta \log n))$ crossings, where the additional crossings arise because we replace, for every type-1 cluster $C\in \cset_1$, the planar drawing $\psi_{C'}$ of $C'$ with the (possibly non-planar) drawing $\psi_C$ of $C$.
Let $\cset_1'=\set{C'\mid C\in \cset_1}$, $\cset_2'=\set{C'\mid C\in \cset_2}$, and $\cset'=\cset_1'\cup \cset_2'$. Since we do not use the original clusters in $\cset$ in the remainder of this subsection, for simplicity of notation, we denote $\cset_1',\cset_2'$ and $\cset'$ by $\cset_1,\cset_2$ and $\cset$, and we will use notation $C\in \cset$ instead of $C'$. Recall that for every cluster $C\in \cset$ we are now given a fixed planar drawing $\psi_C$. In order to reduce the problem to , we use the problem, that we define next, as an intermediate problem.

Cluster Placement Problem.
In the problem, we are given a collection $\hcset$ of disjoint connected planar graphs (that we call clusters). For every cluster $\hC\in \hcset$, we are also given a planar drawing  $\psi_{\hC}$ of $\hC$ on the sphere. We denote by $\fset_{\hC}$ the set of all faces of this drawing. Additionally, for every ordered pair $(\hC_1,\hC_2)\in \hcset$ of clusters, we are given a face $F_{\hC_1}(\hC_2)\in \fset_{\hC_1}$. The goal is to compute a planar drawing $\phi$ of $\bigcup_{\hC\in \hcset}\hC$ on the sphere such that, for every cluster $\hC_1\in \hcset$, the drawing of $\hC_1$ induced by $\phi$ is identical to $\psi_{\hC_1}$, and moreover, for every cluster $\hC_2\in \hcset\setminus\set{\hC_1}$, the drawing of $\hC_2$ in $\phi$ is contained in the face $F_{\hC_1}(\hC_2)$ of the drawing of $\hC_1$ in $\phi$.

The proof of the following simple theorem is deferred to Section <ref> of Appendix.

There is an efficient algorithm, that, given an instance of the problem, finds a feasible solution for the problem, if such a solution exists.

We note that the current collection $\cset=\cset_1\cup \cset_2$ of clusters that we obtained for the instance $G$ of the problem naturally defines an instance of the problem. For every cluster $C\in \cset$, we have already defined a fixed planar drawing $\psi_C$ of $C$ on the sphere.
Consider now some ordered pair $(C_1,C_2)\in \cset$ of clusters. Then there must be some bridge $R\in \rset_{G'}(C_1)$, such that $C_2\subseteq R$. Recall that we have defined a disc $D(R)$ corresponding to the bridge $R$ in the drawing $\psi_{C_1}$ of $C_1$, and that the images of the edges and vertices of $C_1$ in $\psi_{C_1}$ are disjoint from the interior of the disc $D(R)$. Therefore, there is some face $F$ in the drawing $\psi_{C_1}$ of $C_1$ with $D(R)\subseteq F$. We then set $F_{C_1}(C_2)$ to be this face $F$. This defines a valid instance of the problem. Moreover, since Theorem <ref> guarantees the existence of a canonical drawing of the graph $G$, this problem has a feasible solution.
In fact Theorem <ref> provides the following stronger guarantees:

There is a drawing $\phi$ of graph $G'$ with $O(\optcro(G)\poly(\Delta\log n))$ crossings, such that for every cluster $C\in \cset$, the edges of $C$ do not participate in any crossings, and the drawing of $C$ induced by $\phi$ is identical to $\psi_C$ (but the orientation may be arbitrary). Moreover, for any ordered pair $(C_1,C_2)\in \cset$ of clusters, the image of $C_2$ in $\phi$ is contained in the interior of the face $F_{C_1}(C_2)$ of the drawing of $C_1$ in $\phi$.

We use the algorithm from Theorem <ref> in order to compute a feasible solution to this instance of the problem, obtaining a drawing $\tilde \phi$ of $\bigcup_{C\in \cset}C$ on the sphere.

In order to compute a final drawing of $G'$ (and hence of $G$), it is enough to add the drawings of the edges of $E''$ into $\tilde \phi$. We do so by defining an instance of the problem.

Defining Instances of .
Let $\fset$ be the set of all faces in the drawing $\tilde \phi$ of the graph $\bigcup_{C\in\cset}C$. For every face $F\in \fset$, let $\hset(F)\subseteq \cset$ be the set of all clusters $C\in \cset$, such that at least one terminal of $\Gamma(C)$ (that is, endpoint of an edge of $E''$ that lies in $C$) lies on the boundary of the face $F$.

We associate, with each face $F\in \fset$, an instance $(G^F,\Sigma^F)$ of the problem, as follows.
Let $E^F\subseteq E''$ be the set of all edges whose both endpoints lie on the boundary of the face $F$ in $\tilde \phi$.
In order to construct the graph $G^F$, we start with the union of the clusters $C\in \hset(F)$, and add the edges of $E^F$ to the resulting graph. Then we contract every cluster $C\in \hset(F)$ into a vertex $v(C)$, keeping parallel edges and deleting self-loops. This concludes the definition of the graph $G^F$. We now define a rotation system for $G^F$. Consider any vertex $v=v(C)\in V(G^F)$, and let $\delta(v)$ be the set of all edges that are incident to $v(C)$ in $G^F$. If $C\in \cset_1$, then $|\delta(v)|\leq |\Gamma(C)|\leq \poly(\Delta\log n)$. We define $\oset_v$ to be an arbitrary ordering of the edges in $\delta(v)$. Assume now that $C\in \cset_2$. Recall that graph $C$ must be $2$-connected, so the intersection of the boundary of $F$ with $C$ is a simple cycle, that we denote by $K^F(C)$.
We denote by $\Gamma^F(C)$ the set of all vertices of $\Gamma(C)$ that lie on the cycle $K^F(C)$.
From Observation <ref>,  the vertices of $\Gamma(C)$ that serve as endpoints of the edges of $\delta(v)$ must belong to $\Gamma^F(C)$. We let $\tilde \oset^F(C)$ denote the circular ordering of the vertices of $\Gamma^F(C)$ along the cycle $K^F(C)$. The ordering $\oset_v$ of the edges of $\delta(v)$ is determined by the ordering of their endpoints in $\tilde \oset^F(C)$: edges that are incident to the same vertex of $K^F(C)$ appear consecutively in $\oset_v$ in an arbitrary order. The ordering of the edges that are incident to different vertices of $\Gamma^F(C)$ follows the ordering $\tilde \oset^F(C)$. We then let $\Sigma^F=\set{\oset_v}_{v\in V(G^F)}$.

This completes the definition of instance $(G^F,\Sigma^F)$ of . Since Theorem  <ref> calls for a single instance of , we let $G''$ be the disjoint union of the graphs in $\set{G^F}_{F\in \fset}$, and we let $\Sigma=\bigcup_{F\in \fset}\Sigma^F$. This defines the
final instance $(G'',\Sigma)$ of the problem. Notice that $E(G'')\subseteq E''$ and so $|E(G'')|\leq O(\optcro(G)\poly(\Delta\log n))$. We need the following observation.

$E''=\bigcup_{F\in \fset}E^F$.

From the definition of edge sets $E^F$, $\bigcup_{F\in \fset}E^F\subseteq E''$, so it is enough to show that $E''\subseteq \bigcup_{F\in \fset}E^F$. Assume for contradiction that this is not the case. Then there is some edge $e=(u,v)\in E''$, such that no face of $\fset$ contains both $u$ and $v$ on its boundary.
Let $C'$ be the cluster containing $u$ and $C''$ the cluster containing $v$; recall that $C'\neq C''$ must hold.
Then there must be some cluster $C$ and a cycle $K$ in $C$, such that $u,v\not \in K$, and the image of $K$ in $\tilde \phi$ separates the images of $u$ and $v$. If $C=C'$, then we let $F_1$ be any face in the drawing of $C$ that is incident to $u$; otherwise, we let $F_1=F_C(C')$. Similarly, if $C=C''$, then  we let $F_2$ be any face in the drawing of $C$ that is incident to $v$; otherwise, we let $F_2=F_C(C')$. Notice that $F_1\neq F_2$, and moreover, since $K$ separates $u$ from $v$, if $C=C'$ then $u$ does not lie on the boundary of $F_2$ (and similarly, if $C=C''$, then $v$ does not lie on the boundary of $F_1$). But that means that, in the drawing $\phi$ of graph $G'$ that is given by Observation <ref>, there is some cycle $K'\subseteq C$ that separates the image of $u$ from the image of $v$ in $\phi$. But then the image of edge $e$ must cross the image of some edge of $C$ in $\phi$, which is impossible.

Next, we show that the final instance $(G',\Sigma)$ of has a sufficiently cheap solution. The proof of the next lemma appears in Section <ref> of Appendix.

There is a solution to instance $(G'',\Sigma)$ of of value $O(\optcro(G)\cdot \poly(\Delta\log n))$.

Lastly, in order to complete the proof of Theorem <ref>, it is enough to show an efficient algorithm, that, given  any solution to instance $(G'',\Sigma)$ of of value $X$, computes a drawing of $G'$ with $O\left ((X+\optcro(G))\cdot \poly(\Delta\log n)\right)$ crossings.

Obtaining the Final Drawing of $G'$.
We assume that we are given a solution $\hat \phi$ to instance $(G'',\Sigma)$ of , whose value is denoted by $X$. Since graph $G''$ is the disjoint union of graphs $\set{G^F}_{F\in \fset}$, we can use $\hat \phi$ to obtain, for each face $F\in \fset$, a solution $\hat \phi^F$ to instance $(G^F,\Sigma^F)$ of , of value $X^F$, such that $\sum_{F\in \fset}X^F\leq X$. Intuitively, ideally, we would like to start with the drawing $\tilde \phi$ of $\bigcup_{C\in \cset}C$ given by the solution to the problem, and then consider the faces $F\in \fset$ one-by-one. For each such face, we would like to use the drawing $\hat \phi^F$ of graph $G^F$ in order to insert the images of the edges of $E^F$ into the face $F$. Since, from Observation <ref>, $E''=\bigcup_{F\in \fset}E^F$, once every face of $\fset$ is processed, all the edges of $E''$ are inserted into the drawing, and we obtain a valid drawing of graph $G'$. There is one difficulty with using this approach. Recall that, a solution $\hat \phi^F$ to instance $(G^F,\Sigma^F)$ guarantees that for every vertex $v\in V(G^F)$, the images of the edges of $\delta(v)$ enter $v$ in an ordering identical to $\oset_v$. However, the orientation of this ordering may be arbitrary. In other words, in order to insert the edges of $E^F$ into the face $F$ of the drawing of $\phi'$, by copying their drawings in $\hat \phi^F$, we may need to flip the drawings of some clusters $C\in \hset(F)$. Since each cluster may belong to several sets $\hset(F)$, we need to do this carefully.

Consider the drawing $\tilde \phi$ of $\bigcup_{C\in \cset}C$.
Consider any cluster $C\in \cset$ and any face $F\in \fset$, such that $C\in \hset(F)$.
As before, we let $\Gamma^F(C)\subseteq \Gamma(C)$ be the set of terminals that belong to $C$ and lie on the boundary of the face $F$. Next, we define a disc $D^F(C)$, as follows. If $C\in \cset_1$, then let $\gamma^F(C)$ be a simple closed curve that contains every terminal in $\Gamma^F(C)$, and separates the drawing of $C\setminus \Gamma^F(C)$ from the drawing of every cluster $C'\in \hset(F)\setminus\set{C}$. If $C\in \cset_2$, then we let $\gamma^F(C)$
be the image of the cycle $K^F(C)$ in $\tilde \phi$. We then let $D^F(C)$ be a disc, whose boundary is $\gamma^F(C)$, that contains the drawing of $C$ in $\tilde \phi$. Notice that for every cluster  $C'\in \hset(F)\setminus\set{C}$, the drawing of $C'$ in $\tilde \phi$ is disjoint from $D^F(C)$. Notice also that, if $C\in \cset_2$, then the ordering of the terminals in $\Gamma^F(C)$ on the boundary of $D^F(C)$ is identical to $\tilde \oset^F(C)$.

We now proceed as follows. First, we describe a procedure , that, intuitively, will allow us to insert, for a given face $F\in \fset$, all edges of $E^F$ into the drawing; this may require flipping drawings in some discs $D^F(C)$, for $C\in \hset(F)$. We then show an algorithm that builds on this procedure in order to compute a drawing of $G'$.

Procedure .
The input to procedure is a face $F\in \fset$, and a collection $\set{D^F(C)}_{C\in \hset(F)}$ of disjoint discs (intuitively, disc $D^F(C)$ already contains a drawing of some parts of the graph $G$, as defined above, but in this procedure we do not modify parts of the graph drawn inside the disc, and consider these parts as being fixed; we may however flip the drawing that is contained in $D(C)$). Additionally, for every cluster $C\in \hset(F)$, we are given a drawing of the terminals in $\Gamma^F(C)$ on the boundary of the disc $D^F(C)$. We require that, if $C\in \cset_2$, then the circular ordering of the terminals in $\Gamma^F(C)$ on the boundary of the disc $D^F(C)$ is identical to $\tilde \oset^F(C)$. We are also given a cluster $C^*\in \hset(F)$, whose orientation is fixed (that is, we are not allowed to flip the disc $D^F(C^*)$). The procedure inserts the edges of $E^F$ into this drawing, while possibly flipping some discs $D^F(C)$.

In order to execute the procedure, we start with the solution $\hat \phi^F$ to instance $(G^F, \Sigma^F)$. For every vertex $v\in V(G^F)$, we consider a small disc $\eta(v)$ around the drawing of $v$ in $\hat \phi^F$. We also define a smaller disc $\eta'(v)\subseteq \eta(v)$ that is contained in the interior of $\eta(v)$ and contains the image of $v$. For every edge $e=(v,v')$, we truncate the image of $e$, so that it originates at some point $p_v(e)$ on the boundary of $\eta(v)$ and terminates at some point $p_{v'}(e)$  on the boundary of $\eta(v')$.

Consider now some vertex $v(C)\in V(G^F)$, whose corresponding cluster $C$ lies in $\cset_2$. Recall that for every terminal $t\in \Gamma^F(C)$,
there must be a contiguous segment $\sigma(t)$ on the boundary of $\eta(v)$ that contains all points $\set{p_{v(C)}(e)}$, where $e\in \delta(v)$ is an edge that is incident to $t$, so that all resulting segments in $\set{\sigma_t\mid t\in \Gamma^F(C)}$ are disjoint. The circular ordering of these segments along the boundary of $\eta(v)$ is identical to $\tilde \oset^F(C)$. We place images of the terminals in $\Gamma^F(C)$ on the boundary of $\eta'(v)$, in the circular order that is identical to $\tilde \oset^F(C)$, whose orientation is the same as the orientation of the ordering of the segments in $\set{\sigma_t\mid t\in \Gamma^F(C)}$. If the orientation of this ordering is identical to the orientation of the ordering of terminals of $ \Gamma^F(C)$ on the boundary of the disc $D^F(C)$, then we say that cluster $C$ agrees with the orientation of $\hat \phi^F$, and otherwise we say that it disagrees with it. We can assume without loss of generality that, if cluster $C^*\in \cset_2$, then it agrees with the orientation of $\hat \phi^F$, since otherwise we can flip the drawing $\hat \phi^F$.

In order to insert the edges of $E^F$ into the current drawing, we will do the opposite: we will “insert” the discs $D^F(C)$ into the discs $\eta'(v(C))$ in the drawing $\hat \phi^F$. Specifically, for every cluster $C\in \cset$, if $C$ agrees with the orientation of $\hat \phi^F$, then we insert the disc $D^F(C)$ into the disc $\eta'(v(C))$  in the current drawing $\hat \phi^F$, so that the images of the terminals of $\Gamma^F(C)$ coincide (it may be convenient to think of the disc $D^F(C)$ as containing a drawing of $C$ and maybe some additional subgraphs of $G'$). If $C$ disagrees  with the orientation of $\hat \phi^F$, then we first create a mirror image of the disc $D^F(C)$ (that will result in flipping whatever drawing currently appears in $D^F(C)$), and then insert the resulting disc into the disc $\eta(v(C))$ in the current drawing $\hat \phi^F$, so that the images of the terminals of $\Gamma^F(C)$ coincide.
In either case, we can extend the drawings of the edges of $\delta(v(C))$ inside $\eta(v(C))\setminus\eta'(v(C))$, so that for every terminal $t\in \Gamma^F(C)$, the drawing of every edge $e$ that is incident to $t$ terminates at the image of $t$, without introducing any crossings.
Lastly, if $C\in \cset_1$, then we simply insert the disc $D^F(C)$ into the disc $\eta'(C)$.  We extend the drawings of the edges of $\delta(v(C))$ inside $\eta(v(C))\setminus\eta'(v(C))$, so that for every terminal $t\in \Gamma^F(C)$, the drawing of every edge $e$ that is incident to $t$ terminates at the image of $t$, while introducing at most $|\Gamma^F(C)|^2$ new crossings. This completes the description of Procedure .

We are now ready to complete the drawing of the graph $G'$. Our algorithm performs a number of iterations. In each iteration $i$ we will fix an orientation of some subset $\cset^i\subseteq \cset$ of clusters.
We maintain the invariant that for every cluster $C\in \cset^i$, if $F\in \fset$ is any face with $C\in \hset(F)$ that has not been processed yet, then no cluster of $(\cset^1\cup \cset^2\cup\cdots\cup \cset^i)\setminus\set{C}$ lies in $\hset(F)$.
We let $\cset^0$ consist of a single arbitrary cluster $C_0\in \cset$.

In order to execute the first iteration, we let $F\in \fset$ be any face with $C_0\in \hset(F)$. We run Procedure on face $F$, with cluster $C^*=C_0$. Notice that the outcome of this procedure can be used in order to insert the edges of $E^F$ into the current drawing $\tilde \phi$ of $\bigcup_{C\in \cset}C$, after possibly flipping the images inside some discs in $\set{D(C)}_{C\in \hset(F)\setminus\set{C_0}}$. We then let $\cset^1$ contain all clusters in $\hset(F)$. Notice that the invariant holds for this definition of set $\cset^1$. For each  cluster $C\in \cset^1$, its orientation is fixed from now on, and the drawing of $C$ will never be modified again.

In order to execute the $i$th iteration, we start with $\cset^i=\emptyset$. We consider each cluster $C\in \cset_{i-1}$, one-by-one. For each such cluster $C$, for every face $F\in \fset$ with $C\in \hset(F)$, that has not been processed yet, we apply Procedure to face $F$, with $C=C^*$. As before, this procedure can be used in order to insert all edges of $E^F$ into the current drawing, after, possibly, flipping the images contained in some discs $D^F(C')$, for $C'\in \hset(F)\setminus\set{C}$. Notice, however, that from our invariant, none of the clusters corresponding to these discs may belong to $\cset^1\cup \cdots\cup \cset^{i-1}$. We then add, to set $\cset^i$, all clusters of $\hset(F)\setminus\set{C}$. It is easy to verify that the invariant continues to hold. Once every face in $\fset$ is processed, we have inserted all edges of $E''$ into $\phi'$, and obtain a final drawing $\phi''$ of the graph $G'$.

We now bound the number of crossings in $G'$. In addition to the crossings that were present in the drawings $\hat \phi^F$, for $F\in \fset$, we may have added, for every cluster $C\in \cset_1$, at most $O(\Delta^2 |\Gamma(C)|^2)$ new crossings of edges that are incident to the terminals of $C$ (this bound follows the same reasonings as those in the proof of Lemma <ref>). Since, for every cluster $C\in \cset_1$, $|\Gamma(C)|\leq O(\poly(\Delta\log n))$, we get that the total number of crossings in the drawing $\phi''$ of $G'$ is at most:

\[
\begin{split}
X+O\Big(\sum_{C\in \cset_1} \Delta |\Gamma(C)|^2\Big)& \leq  X+O(|\Gamma|\poly(\Delta\log n)) \\
&\leq X+O(|E''|\poly(\Delta\log n))\\
&\leq X+O(\optcro(G) \poly(\Delta\log n)).
\end{split}\]

Note that drawing $\phi''$ of $G'$ immediately induces a drawing of the original graph $G$, where the number of crossings is bounded by $\cro(\phi'')$ plus the sum, over all original type-1 clusters $C\in \cset_1$, of the number of crossings in the original drawing $\psi_C$ of $C$ (recall that we have replaced all such crossings with vertices in $G'$). However, the total number of all such additional crossings, as shown already, is bounded by $O(\optcro(G) \poly(\Delta\log n))$, and so overall, the total number of crossings in the final drawing of $G$ is bounded by
$X+O(\optcro(G) \poly(\Delta\log n))$. This completes the proof of Theorem <ref> for the special case where the input graph $G$ is $3$-connected. We extend the proof to general graphs in Section <ref>.

In Section <ref> we provide an algorithm for the problem,  proving Theorem <ref>.

§ BLOCK DECOMPOSITIONS AND EMBEDDING OF FAKE EDGES

Let $G$ be a $2$-connected graph. A $2$-separator for $G$ is a pair $(u,v)$ of vertices, such that graph $G\setminus\set{u,v}$ is not connected.
Most of the definitions in this section are from [12].

Let $G=(V,E)$ be a $2$-connected graph.
A subgraph $B=(V',E')$ of $G$ is called a block iff:

* $V\setminus V'\neq\emptyset$ and $|V'|\geq 3$;

* There are two distinct vertices $u,v\in V'$, called block end-points and denoted by $I(B)=(u,v)$, such that there are no edges from $V\setminus V'$ to $V'\setminus\set{u,v}$ in $G$. All other vertices of $B$ are called inner vertices;

* $B$ is the subgraph of $G$ induced by $V'$, except that it does not contain the edge $(u,v)$ even if it is present in $G$.

Notice that, if $G$ is a $2$-connected graph, then every $2$-separator $(u,v)$ of $G$ defines at least two internally disjoint blocks $B',B''$ with $I(B'),I(B'')=(u,v)$.
If $B$ is a block with endpoints $u$ and $v$, then the complement of $B$, denoted by $B^c$, is the sub-graph of $G$ induced by the vertices of $(V(G)\setminus V(B))\cup \set{u,v}$. Notice that $B^c$ is itself a block, unless edge $e=(u,v)$ belongs to $B^c$; in the latter case, $B^c\setminus\set{e}$ is a block.

§.§ Block Decomposition of $2$-Connected Graphs.

Let $\lset$ be a collection of sub-graphs of $G$. We say that $\lset$ is laminar iff for every pair $H,H'\in \lset$ of subgraphs, either $H\cap H'=\emptyset$, or $H\subseteq H'$, or $H'\subseteq H$ hold. Given a laminar collection $\lset$ of subgraphs of $G$ with $G\in \lset$, we can associate a tree $\tau=\tau(\lset)$ with it, called a decomposition tree, as follows. For every graph $H\in \lset$, there is a vertex $v(H)$ in $ \tau$. The tree is rooted at the vertex $v(G)$. For every pair $H,H'\in \lset$ of subgraphs, such that $H\subsetneq H'$, and there is no other graph $H''\in \lset\setminus\set{H,H'}$ with $H\subsetneq H''\subsetneq H'$, there is an edge $(v(H),v(H'))$ in the tree, and $v(H')$ is the parent of $v(H)$ in $\tau$.

Let $G$ be a $2$-connected graph, and
assume that we are given a laminar family of sub-graphs of $G$ with $G\in \lset$. Let $\tau=\tau(\lset)$ be the decomposition tree associated with $\lset$. Assume further that every graph  $B\in \lset\setminus\set{G}$ is a block. For each such graph $B\in \lset$,  we define a new graph, $\tilde {B}$; this definition is used throughout the paper. The edges of $\tilde B$ will be classified into “fake” edges and “real” edges, where every real edge of $\tilde B$ is an edge of $B$.
In order to obtain graph $\tilde B$, we start with the graph $B$. We then consider every child vertex $v(B')$ of $v(B)$ in $\tau(\lset)$ one-by-one. For each such child vertex $v(B')$, we delete all edges and vertices of $B'$ from $B$, except for the endpoints $I(B')$.

If the current graph $\tilde B$ does not contain an edge connecting the endpoints of $B'$, then we add such an edge as a fake edge. Consider now the graph $\tilde B$ obtained after processing every child vertex of $v(B)$ in tree $\tau(\lset)$. If $B\neq G$, then we add a fake edge connecting endpoints of $B$ to $\tilde B$ (notice that, from the definition of a block, $\tilde B$ may not contain a real edge connecting the endpoints of $B$). This completes the definition of the graph $\tilde B$. Observe that by our construction, $\tilde B$ has no parallel edges.
The definition of $\tilde B$ depends on the family $\lset$, so when using it we will always fix some such family. We denote by $A_{\tB}$ the set of all fake edges in $\tilde B$. We also denote by $e^*_{\tB}$ the unique fake edge connecting the endpoints of $B$; if no such edge exists, then $e^*_{\tB}$ is undefined. We refer to $e^*_{\tB}$ as the fake parent-edge of $\tB$.

We let $\nset(B)$ be a collection of sub-graphs of $G$ that contains the graph $B^c$ – the complement of the block $B$, and additionally, for every child vertex $v(B')$ of  $v(B)$ in the tree $\tau$, the block $B'$. Observe that every fake edge $e=(u,v)$ of $\tilde B$ is associated with a distinct graph $B_e\in \nset(B)$, where $I(B_e)=(u,v)$.
We are now ready to define a block decomposition.

Let $G$ be a $2$-connected graph,
let $\lset$ be a laminar family of sub-graphs of $G$ with $G\in \lset$, and let $\tau=\tau(\lset)$ be the decomposition tree associated with $\lset$. We say that $\lset$ is a block decomposition of $G$, iff:

* every graph $B\in \lset\setminus\set{G}$ is a block;

* for each graph $B\in \lset$, either $\tilde{B}$ is $3$-connected, or $\tilde B$ is isomorphic to $K_3$ – a clique graph on $3$ vertices; and

* if a vertex $v(B)\in V(\tau)$ has exactly one child vertex  $v(B')$, then $I(B) \neq I(B')$.

For convenience, if $\lset$ is a block decomposition of $G$, then we call the elements of $\lset$ pseudo-blocks. Note that each pseudo-block is either a block of $G$, or it is $G$ itself.
The following theorem was proved in [12].

[Theorem 12 in the arxiv version of [12]]
There is an efficient algorithm, that, given a $2$-connected graph $G=(V,E)$ with $|V|\geq 3$, computes a block decomposition $\lset$ of $G$, such that, for each vertex $v\in V$ that participates in some $2$-separator $(u,v)$ of $G$, either (i)  $v$ is an endpoint of a block $B\in\lset$, or (ii) $v$ has exactly two neighbors in $G$, and there is an edge $(u',v)\in E$, such that $u'$ is an endpoint of a block $B\in \lset$.

We need the following two simple observations.

Let $G$ be a $2$-connected graph, let $\lset$ be a block decomposition of $G$, and let $B\in \lset$ be a pseudo-block in the decomposition. Consider the corresponding graph $\tilde B$. Then, for every fake edge $e\in A_{\tilde B}$, there is a path $P(e)$ in $G$, connecting its endpoints, that is internally disjoint from
$V(\tilde B)$ and is completely contained in some graph $B_e\in \nset(B)$. Moreover, if $e\neq e'$ are two distinct fake edges in $A_{\tilde B}$, then $B_e\neq B_{e'}$, and so paths $P(e)$ and $P(e')$ are internally disjoint.

Let $G$ be a $2$-connected planar graph, let $\lset$ be a block decomposition of $G$, and let $B\in \lset$ be a pseudo-block. Then $\tilde B$ is a planar graph, and it has a unique planar drawing.

We get a planar drawing of $\tilde B$ using a planar of $G$. We draw every real edge of $\tilde B$ along its drawing in $G$. Moreover, by Observation <ref>, there is a path corresponding to every fake edge of $\tilde B$ that is internally disjoint from other paths and the vertices of $\tilde B$. Therefore, we can draw the fake edge along this path without introducing any crossings. Therefore, the graph $\tilde B$ is also planar. Using the definition of block decomposition, we know that either $\tilde B$ is $3$-connected or equal to $K_3$, meaning that it has a unique planar drawing.

§.§ Block Decomposition of General Graphs

So far we have defined a block decomposition for $2$-connected graphs. We now extend this notion to general graphs, that may not even be connected, and introduce some useful notation.
Let $G$ be any graph. We denote by $\cset(G)$ the set of all connected components of $G$.
Consider now some connected component $C\in \cset(G)$. Let $\zset(C)$ denote the collection of all maximal $2$-connected sub-graphs of $C$ (that is, $Z\subseteq C$ belongs to $\zset(C)$ iff $Z$ is $2$-connected, and it is not strictly contained in any other $2$-connected subgraph of $C$).
It is easy to verify that $\zset(C)$ is uniquely defined and can be computed efficiently.
For convenience, we call the elements in $\zset(C)$ super-blocks.
We also denote by $\zset(G)=\bigcup_{C\in \cset(G)}\zset(C)$ the collection of all resulting super-blocks.

Finally, for every super-block $Z\in \zset(G)$, we let $\lset(Z)$ be the block decomposition of $Z$ given by Theorem <ref>.
Recall that $\lset(Z)$ contains the graph $Z$, and all other graphs in $\lset(Z)$ are blocks of $Z$.
We denote by $\bset(C)=\bigcup_{Z\in \zset(C)}\lset(Z)$ the collection of all pseudo-blocks in the block decompositions of the subgraphs $Z\in \zset(C)$, and we denote $\bset(G)=\bigcup_{C\in \cset(G)}\bset(C)$. We will refer to the collection $\bset(G)$ of pseudo-blocks a block decomposition of $G$. Observe that this generalizes the definition of block decompositions of $2$-connected graphs to general graphs.

Consider now some super-block $Z\in \zset(G)$, and some pseudo-block $B\in \lset(Z)$. If $B=Z$, then the complement block $B^c$ is empty. Otherwise, the complement block $B^c$ is defined exactly as before, with respect to the graph $Z$. In other words, $B^c$ is the sub-graph of $Z$ induced by the set $(V(Z)\setminus V(B))\cup I(B)$ of vertices. We define the set $\nset(B)$ of graphs as before: we add $B^c$ to $\nset(B)$, and additionally, for every child vertex $v(B')$ of $v(B)$, we add the block $B'$ to $\nset(B)$.

§.§ Embedding of Fake Edges

We will repeatedly use the following lemma, whose proof appears in Section <ref>.

Let $G$ be a graph, and let $\bset(G)$ be its block decomposition.
Denote $\tilde\bset(G)=\set{\tilde B\mid B\in \bset(G)}$, and let $\tilde \bset^*(G)\subseteq \tilde\bset(G)$ contain all graphs $\tilde B$ that are not isomorphic to $K_3$. Then we can efficiently compute, for each graph $\tilde{B}\in \tilde\bset^*(G)$, a collection $\pset_{\tilde B}=\set{P_{\tilde B}(e)\mid e\in A_{\tilde B}}$ of paths in $G$, such that:

* for each fake edge $e=(u,v)\in A_{\tilde B}$, the path $P_{\tilde B}(e)$ connects $u$ to $v$ in $G$ and it is internally disjoint from $\tilde B$;

* all paths in $\pset_{\tilde B}$ are mutually internally disjoint; and

* if we denote $\pset=\bigcup_{\tilde B\in \tilde\bset^*(G)}\left(\pset_{\tilde B}\setminus \set{P_{\tilde B}(e^*_{\tilde B})} \right)$, then every edge of $G$ participates in at most $6$ paths in $\pset$.

§.§ Monotonicity of Blocks under Edge Deletions

Intuitively, our algorithm for Theorem <ref>  starts with some planarizing set $E'$ of edges for the input graph $G$. We denote $H=G\setminus E'$, and consider the block decomposition $\bset(H)$ of $H$. As the algorithm progresses, more edges are added to $E'$, graph $H$ evolves, and its block decomposition $\bset(H)$ changes. The following lemma, whose proof is deferred to Appendix <ref>,  allows us to keep track of these changes.

Let $G$ be a graph, and let $E_1,E_2$ be two planarizing edge sets for $G$, with $E_1\subseteq E_2$. Denote $H_1=G\setminus E_1$, $H_2=G\setminus E_2$, and let $\bset_1=\bset(H_1),\bset_2=\bset(H_2)$ be block decompositions of $H_1$ and of $H_2$, respectively. Then for every pseudo-block $B_2\in \bset_2$ with $|V(\tilde B_2)|>3$, there is a pseudo-block $B_1\in \bset_1$, such that:

* $V(\tilde B_2)\subseteq V(\tilde B_1)$;

* every real edge of $\tilde B_2$ belongs to $\tilde B_1$ as a real edge, except (possibly) for an edge whose endpoints are the endpoints of $B_1$;

* for every fake edge $e=(u,v)$ in $\tilde B_2$, there is a path $P(e)$ in $\tilde B_1$ that connects $u$ to $v$ (and may contain fake edges of $\tilde B_1$), that is internally disjoint from $V(\tilde B_2)$. Moreover, if $e$ and $e'$ are distinct fake edges of $\tilde B_1$, then their corresponding paths $P(e)$ and $P(e')$ are internally disjoint; and

* if graph $\tilde B_2$ contains a real edge connecting the endpoints of $B_1$, then for every fake edge $e\in E(\tilde B_2)$, the path $P(e)$ does not contain the edge connecting the endpoints of $B_1$.

SPQR Trees.

not clear if we need these trees

SPQR Trees.
We will use the notion of SPQR-trees. Intuitively, the SPQR tree for a graph $G$ defines a decomposition of $G$.
Let $\tau$ be the SPQR-tree for the graph $G$. Each node $x$ of $\tau$ is associated with a graph $G_x=(V_x,E_x)$, where $V_x\subseteq V(G)$, and $E_x$ is the union of (i) a subset of edges in $E(G)$ (called real edges); and (ii) some additional edges (called virtual edges).

The following properties are satisfied:

* Each (real) edge in $E(G)$ belong to exactly one graph of $\set{G_x}_{x\in V(\tau)}$;

* For each edge $e=(x,y)$ of $\tau$, there is a unique virtual edge $e_x$ in $G_x$ and a unique virtual edge $e_y$ in $G_x$ associated with it, such that the endpoints of $e_x$ in $G_x$ and the endpoints of $e_y$ in $G_y$ are the copies of the same two vertices $u,v$ in $G$. Moreover, the graphs $G_x$ and $G_y$ share no other vertices;

* For each edge $e=(x,y)$ of $\tau$, let $\tau_1$, $\tau_2$ be the two connected components (subtrees) of $\tau$ after the removal of the edge $(x,y)$. Denote $V_1=\bigcup_{x\in \tau_1}V_x$ and $V_2=\bigcup_{x\in \tau_2}V_x$, then $V_1\cap V_2=\set{u,v}$ and  $V_1\cup V_2=V(G)$.

(Special Notations)
Special Notations.
Let $\tG$ be the input graph, and let $\tE$ be the input set of planarizing set. We denote $\tH=\tG\setminus \tE$, so $\tH$ is planar.
We denote by $\tphi$ to be the drawing of $\tG$ in the plane with minimum number of crossings, so $\cro(\tphi)=\cro(\tG)$.

(Flip Operation)

Let $G$ be a graph and let $\phi$ be a drawing of $G$. Let $F$ be a face of $\phi$ whose boundary is a simple cycle in $G$, and let $C$ be a connected subgraph of $G$ such that $E(C)\cap E(F)=\emptyset$. Let $\psi$ be another drawing of $G$. We say that the drawing $\psi$ is obtained by flipping the induced drawing $\phi(C)$ into $F$ in $\phi$, or  flipping $C$ into $F$ in $\phi$, if

* the induced drawings $\phi(G\setminus C)$ and $\psi(G\setminus C)$ are identical;

* the induced drawing $\psi(C)$ is the reflection of the induced drawing $\phi(C)$ with respect to the boundary of $F$(see Figure <ref>).

Note that, if $\psi$ is obtained by flipping $C$ into $F$ in $\phi$, then the induced drawing of $\psi$ on $C$ is entirely contained in the disc $D(\phi,F)$.

[Before flipping.]0.45

[After flipping.]
Flipping the induced drawing $\phi(C)$ into $F$ in $\phi$. The edges of $C$ are shown in red. The boundary edges of $F$ are shown in green.

(Paths and Confluent Paths)
Paths and Confluent Paths.
Given a set $\pset$ of paths in $G$, we denote $E(\pset)=\bigcup_{P\in\pset}E(P)$.
For each edge $e\in E(G)$, we denote by $c_{\pset}(e)$ the number of paths in $\pset$ that contain the edge $e$. We also denote $c(\pset)=\max_{e\in E(G)}\set{c_{\pset}(e)}$.

Given a set $\pset$ of paths in $G$, we say that paths of $\pset$ are confluent iff (i) there exists a vertex $u\in V(G)$ such that $u$ is an endpoint of each path of $\pset$; (ii) the intersection of every pair of paths in $\pset$ is a subpath of both paths. We will use the following lemma of confluent paths, which is actually an easy corollary of Theorem 3 (the main algorithmic result) in <cit.>.
For completeness, we provide its proof in Appendix <ref>.

There is an efficient algorithm, that, given (i) a graph $G$ on $n$ vertices, a vertex $u$ of $G$ and a set $T$ of vertices of $G$; and (ii) a set $\qset$ of paths of $G$, each connecting a distinct vertex of $T$ to $u$, computes a set $\pset$ of paths in $G$, each connecting a distinct vertex of $T$ to $u$, such that:

* the paths of $\qset$ are confluent;

* $E(\pset)\subseteq E(\qset)$; and

* $c(\pset)\le  O(\log n)\cdot c(\qset)$.

§ COMPUTING A DECOMPOSITION INTO ACCEPTABLE CLUSTERS: PROOF OF THEOREM <REF>

A note for fixing things later.

* The legs of a bridge $R\in \rset_G(\tilde B)$ for a block $B$ may not be terminals. They may be endpoints of the block.

* For every block that either contains at least one terminal, or has more than 2 fake edges, we can isolate the endpoints of all fake edges (delete all edges incident to them in $G$). This way we can define the “goodness” property w.r.t. $\tilde B$ with the fake edges, as the fake edges will be eliminated.

* For a block that contains no terminals and has 1 or 2 fake edges: if every bridge has all legs on same face we are OK as before (now the legs are the endpoints of the 2 fake edges). But if this is not the case, we need to argue that at least one edge of the block, or both fake edges participate in crossings. If we can show this, then we can again isolate the endpoints of the fake edges. But now every "terminal" lies on boundaries of 2 faces. So it's possible that every pair of terminals lies on the boundary of the same face, but for some bridge its legs don't lie on the boundary of the same face. We can't afford to delete edges incident to terminals unless we can show that some edge of the block participates in crossings.

* However, we can take the block, and the tree $T_R$, which we can compress into a star, and claim that the resulting graph is not planar, so there must be a crossing. Our problem is when the only crossing is that in which the fake parent-edge participates. We could embed all parent-edges in case of long chains of blocks each of which has 1 child only, or we could turn this chain upside down so the parent-edge stop being parent-edge. (These blocks cannot be $K_3$'s because they are not good, each has 2 fake edges. Both can be embedded without going through each other. Alternatively, we can claim that the parent-block has a crossing in which a real edge participates, because the endpoints of the fake edge have 3 paths connecting them).

This section is dedicated to the proof of Theorem <ref>.
The proof consists of two stages. In the first stage, we compute a subset $E_1$ of edges of $G$ with $E'\subseteq E_1$ and
$|E_1|\leq O\left ( (|E'|+\optcro(G))\cdot \poly(\Delta\log n)\right )$. We will ensure that for every connected component $C$ of the resulting graph $G\setminus E_1$, either $C$ contains at most $\mu$ terminals (endpoints of edges of $E_1$) and therefore can be considered a type-1 acceptable cluster, or it has another nice property that is somewhat similar to the Bridge Consistency Property. In the second part of the proof, we augment the edges in $E_1$ to another set $E''$ of edges, and complete the construction of the decomposition. Intuitively, the first stage deals with the Bridge Consistency property, while the second stage ensures the Terminal Well-Linkedness and $3$-Connectivity properties of the type-2 acceptable clusters.

We start by introducing some notation and defining the notions of good pseudo-blocks.

§.§ Good Pseudo-Blocks

Throughout this subsection, we assume that we are given some planarizing set $\hat E$ of edges for the input graph $G$, that is, $G\setminus \hat E$ is planar. We note that $\hat E$ is not necessarily the same as the original planarizing set $E'$, since, as the algorithm progresses, we may add edges to the planarizing set. The definitions in this subsection refer to any planarizing set $\hat E$ that may arise over the course of the algorithm.

Given a planarizing set $\hat E$ of edges for $G$, let $H=G\setminus \hat E$. Recall that we say that a vertex $v$ of $H$ is a terminal iff it is incident to some edge in $\hat E$, and we denote the set of terminals by $\Gamma$.

Recall that we have defined a block decomposition of a graph $H$ as follows. We denoted by $\cset=\cset(H)$ the set of all connected components of $H$, and we refer to the elements of $\cset$ as clusters. For each cluster $C\in \cset$, we have defined a collection $\zset(C)$ of super-blocks (maximal $2$-connected subgraphs) of $C$, and we denoted $\zset(H)=\bigcup_{C\in \cset}\zset(C)$. Lastly, for each superblock $Z\in \zset(H)$, we let $\lset(Z)$ be the block decomposition of $Z$ given by Theorem <ref>, and we denoted by $\bset(C)=\bigcup_{Z\in \zset(C)}\lset(Z)$ the resulting collection of pseudo-blocks for cluster $C$. The final block decomposition of $H$ is defined to be $\bset(H)=\bigcup_{C\in \cset}\bset(C)$.

Consider some pseudo-block $B\in \bset(H)$, and let $\tilde B$ be the corresponding graph that is either a $3$-connected graph or isomorphic to $K_3$.
Recall that $\tilde B$ has a unique planar drawing, that we denote by $\rho_{\tilde B}$. Throughout this section, for any pseudo-block $B$, we denote by $\tilde B'\subseteq \tilde B$ the graph obtained from $\tilde B$ by deleting all its fake edges. Note that $\tilde B'$ may be not $3$-connected, and it may not even be connected. The drawing $\rho_{\tilde B}$ of $\tilde B$ naturally induces a drawing of $\tilde B'$, that we denote by $\rho'_{\tilde B'}$.

We say that a pseudo-block $B\in \bset(H)$ is a good pseudo-block iff there is a planar drawing $\hat{\psi}_B$ of $B$, that we call the associated drawing, such that, for each bridge $R\in \rset_G(B)$, there is a face $F$ in $\hat{\psi}_B$, whose boundary contains all vertices of $L(R)$. If $B$ is not a good pseudo-block, then it is called a bad pseudo-block.