Complexity of Anchored Crossing Number and Crossing Number of Almost Planar Graphs

The hardness proof in [3] importantly builds on the concept of anchored crossing number, which has already been, often just implicitly, used in numerous research works in the area. The anchored crossing number $\mathrm{cr}{}_{\mathrm{a}}{}^{}(H)$ of an anchored graph $H$ is defined the same way as the ordinary crossing number, with an additional restriction that allowed drawings of $H$ (called anchored drawings) must be contained in a disk such that prescribed vertices of $H$ (the anchors) are placed (“anchored”) in prescribed distinct points on the disk boundary. See Figure 1 a). A graph $H$ is anchored planar if the anchored crossing number of $H$ is $0$ (note that a planar graph may not be anchored planar for some/all selections of the anchor vertices).

The hard instances $H$ in Theorem 1.1 have an additional property (cf. [3, Corollary 2.7]), which will be important later: Each of the two disjoint anchored planar subgraphs forming $H$ has a unique anchored planar drawing (essentially), and every optimal solution to the anchored crossing number of $H$ is a union of these unique anchored planar drawings.

The hardness construction in [3] had used an unbounded number of anchor vertices, but Hliněný and Salazar noted in [9], as a corollary of related research, that the conclusion of Theorem 1.1 remains true if the graph $H$ moreover has a bounded number (namely at most $16$) anchor vertices.¹¹1This result of Hliněný and Salazar was never explicitly published, and it was simply based on taking the “square frame” of [9, Fig. 4,5] and realizing it (turned inside out) with $8+8=16$ anchors – see [9, p. 613]. We now discuss further details in this direction.

Let the anchored graph $H$ from Theorem 1.1 be written as a disjoint union $H=H_1\cup H_2$, where each $H_i$, $i=1,2$, is anchored planar with $a_i>0$ anchors. Observe that if $\min \{a_1,a_2\}=1$, or the anchors of $H_1$ are placed consecutively within all anchors on the disk boundary, then, trivially, $H$ is anchored planar as well. If $\min \{a_1,a_2\}=2=a_1$ (up to symmetry) and the anchors of $H_1$ are not consecutive, then we can efficiently compute the smallest edge cut between the two anchors of $H_1$, and multiply it by the smallest edge cut in $H_2$ between the corresponding two groups (as separated by the anchors of $H_1$) of the anchors of $H_2$. This product equals, again quite trivially, the anchored crossing number of $H$. See Figure 1 b). This leaves $a_1=a_2=3$ as the simplest possibly nontrivial case of the special anchored crossing number problem.

We show that the latter case is already hard in our main result:

Note that parallel edges do not play any essential role in the traditional crossing-number context, since they can be subdivided to make the graph simple, or modelled by integer-weighted simple edges as we do here later from Section 2.

Theorem 1.2 is proved later in the paper, and we remark that its proof is based on some implicit ideas of the proof in [9], which are highly refined with a new overall approach.

The special conditions on hard instances formulated in Theorem 1.2 have an interesting consequence which we informally outline next. We first recall a trick introduced in [3]: Having an instance $H=H_1\cup H_2$ of the anchored crossing number problem as in Theorem 1.2, we can construct a planar graph $G_0:=H\cup C^{+}$ where $C^{+}$ is a (multi)cycle on the $6$ anchor vertices of $H$ in the natural cyclic order, with “sufficiently many” parallel edges between consecutive pairs of the vertices of $C^{+}$. See Figure 2. Now we choose vertices $v_i\in V(H_i)\setminus V(C^{+})$, $i=1,2$, and add a new edge $f=v_1{v}_2$ to $G_0$. Then any optimal solution to the (now ordinary) crossing number of $G_0+f$ must leave $C^{+}$ uncrossed, and so it is actually an anchored drawing of $G_0+f$ with the anchors $V(C^{+})$.

Assuming we choose in the previous $v_1$ and $v_2$ such that the anchored crossing number of $G_0+v_1{v}_2$ equals that of $H$ (which is quite easy under the assumption of given drawings ${𝒟}_1$ and ${𝒟}_2$ in Theorem 1.2), we continue as in Figure 2 c). We modify the graph $G_0$ into ${\overline{G}}_0$ by blowing up every vertex of $V(H_1)$ and every vertex of $V(H_2)\setminus V(C^{+})$ into a “sufficiently large” cubic grid (also known as a wall). Then every vertex of ${\overline{G}}_0$, except the three anchor vertices of $H_2$, is of degree at most $3$, and ${\overline{G}}_0$ is still planar (since flexibility of the anchors of $H_2$ – the reason why these anchors are not blown up as other vertices, allows to flip the modified $H_2$ “inside out” within ${\overline{G}}_0$). Furthermore, the crossing number of ${\overline{G}}_0+v_1{v}_2$ equals the anchored crossing number of $H$.

Hence, in contrast to the efficiently computable case of the crossing number $\mathrm{cr}(G+e)$ where $G$ is planar of maximum degree $3$ [2], we prove the following:

Corollary 1.3 brings a natural question of whether we can efficiently compute the exact crossing number $\mathrm{cr}(G+e)$ of almost planar graphs $G+e$ where $G$ has one or two vertices of degree greater than $3$, and we discuss this in Section 4.

Consequences of Theorem 1.2 are not restricted only to the crossing number of almost planar graphs, but include, for instance, also the following problem [9] of the joint crossing number in a surface: Given are two disjoint graphs $G_1$ and $G_2$, each one embedded on a fixed surface $𝒮$, and the task is to find a drawing (called simultaneous or joint) of $G_1\cup G_2$ in $𝒮$ which preserves each of the given embeddings of $G_1$ and $G_2$, and the number of crossings between $E(G_1)$ and $E(G_2)$ is minimized. While Hliněný and Salazar [9] proved that this problem is hard for the orientable surface with $6$ handles, we easily improve the result to:

We leave formal proofs of the   * -marked statements for the full preprint.

A drawing $𝒢$ of a graph $G$ in the Euclidean plane ${ℝ}^2$ is a function that maps each vertex $v\in V(G)$ to a distinct point $𝒢(v)\in {ℝ}^2$ and each edge $e=uv\in E(G)$ to a simple open curve $𝒢(e)\subset {ℝ}^2$ with the ends $𝒢(u)$ and $𝒢(v)$. We require that $𝒢(e)$ is disjoint from $𝒢(w)$ for all $w\in V(G)\setminus \{u,v\}$. In a slight abuse of notation we often identify a vertex $v$ with its image $𝒢(v)$ and an edge $e$ with $𝒢(e)$. Throughout the paper we will moreover assume that: there are finitely many points which are in an intersection of two edges, no more than two edges intersect in any single point other than a vertex, and whenever two edges intersect in a point, they do so transversely (i.e., not tangentially).

The intersection (a point) of two edges is called a crossing of these edges. A drawing $𝒢$ is planar (or a plane graph) if $𝒢$ has no crossings, and a graph is planar if it has a planar drawing. The number of crossings in a drawing $𝒢$ is denoted by $\mathrm{cr}(𝒢)$. The crossing number $\mathrm{cr}(G)$ of $G$ is defined as the minimum of $\mathrm{cr}(𝒢)$ over all drawings $𝒢$ of $G$.

The following is a useful artifice in crossing numbers research. In a weighted graph, each edge is assigned a positive number (the weight or thickness of the edge, usually an integer). Now the weighted crossing number is defined as the ordinary crossing number, but a crossing between edges $e_1$ and $e_2$, say of weights $t_1$ and $t_2$, contributes the product $t_1\cdot t_2$ to the weighted crossing number. For the purpose of computing the crossing number, an edge of integer weight $t$ can be equivalently replaced by a bunch of $t$ parallel edges of weights $1$; this is since we can easily redraw every edge of the bunch tightly along the “cheapest” edge of the bunch. Hence, from now on, we will use weighted edges instead of parallel edges, and shortly say crossing number to the weighted crossing number. (Note, though, that when we say a graph $G+e$ is almost planar, then we strictly mean that the added edge $e$ is of weight $1$.)

Assume now a closed disk $D\subseteq {ℝ}^2$. An anchored graph [3] is a pair $(H,A)$ where $A\subseteq V(H)$ is a cyclic permutation of some of its vertices; the vertices in $A$ are called the anchors of $H$. An anchored drawing of $(H,A)$ is a drawing $\mathscr{H}$ of $H$ such that $\mathscr{H}\subseteq D$ and $\mathscr{H}$ intersects the boundary of $D$ exactly in the vertices of $A$ in the prescribed cyclic order. The anchored crossing number of $(H,A)$, denoted by $\mathrm{cr}{}_{\mathrm{a}}{}^{}(H,A)$, equals the minimum of $\mathrm{cr}(\mathscr{H})$ over all anchored drawings $\mathscr{H}$ of $(H,A)$. An anchored graph $(H,A)$ is anchored planar if $\mathrm{cr}{}_{\mathrm{a}}{}^{}(H,A)=0$.

We shall study the following special case of an anchored graph $(H,A)$, which we call an anchored pair of planar graphs, or shortly a PP anchored graph: It is the case of $H=H_1\cup H_2$ such that $(H_1,A_1)$ and $(H_2,A_2)$ are vertex-disjoint anchored planar graphs, where $A_i$, $i=1,2$, is the restriction of the permutation $A$ to the anchor set of $H_i$. (Note that we often see instances in which the anchors of $A_1$ alternate with those of $A_2$, but this is not a requirement of our definition.)

From the fine details of [3] one can derive the following refined statement. In view of weighted graphs representing parallel edges (as mentioned above), we say that a graph $G$ contains a path $P\subseteq G$ of weight $t$ if every edge of $P$ in $G$ is of weight at least $t$.

Our proof of Theorem 1.2 is a bit complex, and we first informally explain what we want to achieve. In a nutshell, we are going to “embed” the gadget $(H,A)$ of Theorem 2.1 as an ordinary subgraph within a special “frame” PP anchored graph $F_k$, parameterized by the gadget size, such that $F_k$ forces the vertices of $A$ to be placed as expected in $(H,A)$. By the informal word “forces” we mean that any (other) drawing of $F_k$ violating the placement of the former anchors $A$ would require increasing the number of crossings of $F_k$ higher than what is the difference between the best-case and the worst-case scenarios in Theorem 2.1.

We adopt the following “colour coding”; the subgraph $H_1$ in Theorem 2.1 will be called red and the subgraph $H_2$ blue, and these colours will be correspondingly used also within the frame $F_k$ which will include some of the vertices and edges of $H$ (precisely, the special paths of $H$ claimed by Theorem 2.1(a, b)).

For the sole purpose of this informal outline, it is enough to “define” the frame PP anchored graph $(F_k,B)$ via a detailed sketch in Figure 4. The key feature of $(F_k,B)$ is the use of “heavy-weight” edges, whose weight is of the form ${\omega }^t$ where $t$ is specified at each edge in the picture and $\omega$ is now seen as a variable base. Later, $\omega$ is chosen as a “sufficiently large” integer such that for every $t$, ${\omega }^{t+1}$ is always larger than the sum of a collection of crossings of weight at most ${\omega }^t$ in the reduction (with a slight abuse of traditional notation, ${\omega }^{t+1}>\mathrm{\Theta }({\omega }^t)$), and that all weights are integers.

Briefly, the blue graph of $F_k$ has $3$ anchors $B_2=\{b_0,b_4,d_1\}\subseteq B$, and consists of the vertices lying on two horizontal paths $P_1$ from $b_0$ to $b_4$ of length $4k+4$ and $P_2$ from $c_0$ to $c_4$ of length $4k+2$, four special vertices $d_0,d_1,d_2,d_4$, and the vertices of a vertical path $R$ from $c_2$ to $d_2$ of weight exactly ${\omega }^{48}$ (cf. Theorem 2.1(b) with $w={\omega }^4$). Additional edges exist in $F_k$ between the specified blue vertices as sketched in Figure 4 and detailed in the full definition. The red graph of $F_k$ has again $3$ anchors $B_1=\{r_0,r_2,r_4\}\subseteq B$, and consists of the vertices lying on a cycle $C_0$ of length $4k+3$ passing through $r_2$, the vertices on a horizontal path $P_0$ from $r_0$ to $r_4$ of length $4k+3$, and (the vertices of) a collection $𝒬$ of $k+2k=3k$ edge-disjoint paths of weight ${\omega }^4-1$ or ${\omega }^4$ (as in Theorem 2.1(a) with $w={\omega }^4$) which connect pairs of vertices of $P_0$. Again, further edges exist in $F_k$ between vertices of the red path $P_0$ and the red cycle $C_0$, as sketched in Figure 4 and detailed later. Moreover, all end-edges of the paths in $𝒬$ (i.e., those incident to $P_0$) are of weight ${\omega }^4$, and the second condition of Theorem 2.1(d) is met by the paths in $𝒬$.

Note that we do not require to exactly specify the paths of $𝒬$, in particular they share their internal vertices in an unspecified way (and so, we rather construct a family of frame graphs $F_k$ for each $k$ than single $F_k$), but we do require the properties stated in Theorem 2.1 to hold for them. With respect to the drawing in Figure 4, we call the gadget region of $(F_k,B)$ the region bounded by the blue horizontal path from $c_0$ to $c_4$ and the path $(c_0,d_0,d_2,d_4,c_4)$. Summarizing, our coming proof proceeds in the following points:

• $\mathrm{■}$

  (Lemma 3.1) Let ${\gamma }_{\omega }(k)$ denote the number of crossings in the drawing of $(F_k,B)$ as in Figure 4 (see Lemma 3.1 for an exact formula). In the setting of weighted edges (cf. Section 2), we claim roughly the following; any drawing of $(F_k,B)$ which is “different” from the one in Figure 4 or, specially, in which not all internal vertices of the edges of $𝒬$ lie in the gadget region, has at least ${\gamma }_{\omega }(k)+{\omega }^{34}-{\omega }^{30}$ crossings.

• $\mathrm{■}$

  (Theorem 1.2) Based on the previous point, we can use the internal vertices of the red path $P_0$ and of the blue path $P_2$ and the vertex $d_2$ as “firmly glued” emulated anchors $A$ for the gadget anchored graph $(H,A)$ of Theorem 2.1  –  if these emulated anchors $A$ were not placed as required, then the increase in the number of crossings (${\omega }^{34}-{\omega }^{30}$) of the frame $(F_k,B)$ would be strictly larger than the number of crossings used to draw $(H,A)$ itself (on top of the crossings existing in the subdrawing of $(F_k,B)$). We thus reduce the problem of determining the anchored crossing number of $(H,A)$ to that of $(F_k\cup H,B)$.

As previously sketched in Figure 4, a PP anchored graph $(F_k,B)$ is called a frame graph of the parameter $k$ and weight $\omega$ if the following holds: $(F_k,B)$ is constructed as a disjoint union $F_k=F_k^1\cup F_k^2$ and $B=B_1\cup B_2$, where the component $F_k^1$ is coded as red and $F_k^2$ as blue. In red $F_k^1$, we have the anchors $B_1=\{r_0,r_2,r_4\}$, a cycle $C_0$ passing through $r_2$, a path $P_0$ from $r_0$ to $r_4$, and:

• $\mathrm{■}$

  The vertices of $P_0$ are in order $V(P_0)=(r_0,r_0^1,\mathrm{\dots },r_0^{2k},r_1,r_3,r_0^{2k+1},\mathrm{\dots },r_0^{4k},r_4)$. The weights of its edges are ${\omega }^{41}+𝒪(k{\omega }^{30})$ and are exactly specified below in the proof of Lemma 3.1. A collection of (red) paths $𝒬$ satisfies the assumptions of Theorem 2.1, their ends are identified with vertices of $P_0$ as $a_i=r_0^i$ for $i=1,\mathrm{\dots },4k$, and their weights are set according to (the gadget $(H,A)$ of) Theorem 2.1 and $w:={\omega }^4$.

• $\mathrm{■}$

  The vertices of $C_0$ are in cyclic order $V(C_0)=(r_2,s_0^1,\mathrm{\dots },s_0^{2k},r_1^{\prime },r_3^{\prime },s_0^{2k+1},\mathrm{\dots },$ $s_0^{4k},r_2)$. The edges of $C_0$ are all of weight ${\omega }^{49}$, and there are additional two edges $r_1^{\prime }{r}_1$ and $r_3^{\prime }{r}_3$ of weight ${\omega }^{41}-{\omega }^{40}$ and $4k$ edges $r_0^i{s}_0^i$ of weight ${\omega }^{30}$ for $i=1,\mathrm{\dots },4k$.

In blue $F_k^2$, we have the anchors $B_2=\{b_0,d_1,b_4\}$, a path $P_1$ from $b_0$ to $b_4$, a path $P_2$ from $c_0$ to $c_4$, a path $R$ from $c_2$ to $d_2$, three vertices $d_0,d_1,d_4$, and:

• $\mathrm{■}$

  The vertices of $P_1$ are in order $V(P_1)=(b_0,b_0^1,\mathrm{\dots },b_0^k,b_1,b_0^{k+1},\mathrm{\dots },b_0^{2k},b_2,b_0^{2k+1},\mathrm{\dots },b_0^{3k},$ $b_3,b_0^{3k+1},\mathrm{\dots },b_0^{4k},b_4)$. The vertices of $P_2$ are in order $V(P_2)=(c_0=c_0^1,\mathrm{\dots },c_0^k,c_1,$ $c_0^{k+1},\mathrm{\dots },c_0^{2k},c_2,c_0^{2k+1},\mathrm{\dots },c_0^{3k},c_3,c_0^{3k+1},\mathrm{\dots },c_0^{4k}=c_4)$. The edges of $P_1$ are of weight ${\omega }^{49}+𝒪(k{\omega }^{30})$ between $b_1$ and $b_3$ and of weight ${\omega }^{49}+𝒪(k{\omega }^{34})+𝒪(k{\omega }^{30})$ elsewhere, and are exactly specified below in the proof. The edges of $P_2$ are of weight ${\omega }^{38}$ between $c_1$ and $c_3$ and ${\omega }^{38}+\frac{4}{5}{\omega }^{35}$ elsewhere.

• $\mathrm{■}$

  There is an edge $b_2{c}_2$ of weight ${\omega }^{48}+2{\omega }^{38}-{\omega }^{34}$, two edges $b_1{c}_1$ and $b_3{c}_3$ of weight ${\omega }^{35}$, and $4k$ edges $b_0^i{c}_0^i$ of weight ${\omega }^{30}$ for $i=1,\mathrm{\dots },4k$.

• $\mathrm{■}$

  There is a path $R$, as specified in Theorem 2.1(b), from $c_2$ to $d_2$ of weight ${\omega }^{48}$. There are seven additional edges $c_0{d}_0$, $d_0{d}_1$, $d_0{d}_2$, $d_1{d}_4$, $d_2{d}_4$, $d_4{c}_4$, each of weight ${\omega }^{49}$.

One can easily check from Figure 4 that each of $(F_k^1,B_1)$ and $(F_k^2,B_2)$ is anchored planar.

We have the following claim.

As for the first part of the statement, we organize arguments leading to each term of the formula for ${\gamma }_{\omega }(k)$ stepwise from higher to lower order terms of edge weights. The proof steps, with details of (2) and (4) skipped till later parts of the proof, are as follows:

1. (1)

   The blue path $P_1$ of weight $\ge {\omega }^{49}$ must not cross the red path $P_0$ of weight $\ge {\omega }^{41}$ since that would result in crossings of weight at least $2{\omega }^{90}>{\gamma }_{\omega }^{+}(k)$, and likewise with $P_1$ and $C_0$. So, by the Jordan curve theorem, the two red edges $r_1{r}_1^{\prime }$ and $r_3{r}_3^{\prime }$ of weight ${\omega }^{41}-{\omega }^{40}$ must cross $P_1$, contributing crossing weight at least $2{\omega }^{90}-2{\omega }^{89}$. The $4k$ red edges of weight ${\omega }^{30}$ from $P_0$ to $C_0$ similarly make $4k{\omega }^{79}$ crossings with $P_1$. Further, there are edge-disjoint paths from $b_2$ to $d_1$ of combined weight ${\omega }^{48}+2{\omega }^{38}$; these are formed by the path $b_2{c}_2+R$ of weight ${\omega }^{48}$, by a path from $b_2$ through $c_2$, $c_0$ and $d_0$ of weight ${\omega }^{38}$, by a path from $b_2$ through $c_2$, $c_4$ and $d_4$ of weight ${\omega }^{38}-{\omega }^{34}$, and by a path from $b_2$ through $b_3$, $c_3$ and $c_4$ of weight ${\omega }^{34}$. These contribute weight ${\omega }^{89}+2{\omega }^{79}$ of crossings with $P_0$. Summing up, we have so far accounted for at least $2{\omega }^{90}-{\omega }^{89}+(4k+2){\omega }^{79}>{\gamma }_{\omega }(k)-2{\omega }^{76}+{\omega }^{75}$ enforced crossings.

2. (2)

   The next step is to prove that $P_2$ is drawn disjoint from $P_0$ and drawn above it, and all $c_1{b}_1$, $c_2{b}_2$, $c_3{b}_3$ cross $P_0$. If, for an illustration, $P_0$ was crossed by both $b_1{c}_1$ and $b_3{c}_3$, but not by $b_2{c}_2$, the lower bound from (1) would rise (thanks to full weight of $b_1{c}_1$ and $b_3{c}_3$) to $2{\omega }^{90}-{\omega }^{89}+(4k+2){\omega }^{79}+2{\omega }^{76}\ge {\gamma }_{\omega }(k)+{\omega }^{75}-{\omega }^{72}>{\gamma }_{\omega }^{+}(k)$, which is impossible. If neither of $b_1{c}_1$, $b_3{c}_3$ crosses $P_0$, then we (briefly) get subpaths of $P_1$ and $P_2$ of combined weight $2⁤\frac{2}{5}{\omega }^{35}+2⁤\frac{4}{5}{\omega }^{35}=(2+\frac{2}{5}){\omega }^{35}$ which cross the path $P_0$ or edges $r_1{r}_1^{\prime }$, $r_3{r}_3^{\prime }$, and this contributes an additional weight $(2+\frac{2}{5})({\omega }^{76}-{\omega }^{75})$ of crossings, again exceeding ${\gamma }_{\omega }^{+}(k)$. We leave the fine details and subcases for a later part of the proof.

3. (3)

   Using (2), we may count crossings of $P_0$ with the edges $c_1{b}_1$, $c_2{b}_2$, $c_3{b}_3$ and the $4k$ blue edges of weight ${\omega }^{30}$ between $P_1$ and $P_2$. At this point, our lower bound gets to $2{\omega }^{90}-{\omega }^{89}+(4k+2){\omega }^{79}+2{\omega }^{76}-{\omega }^{75}+4k{\omega }^{71}>{\gamma }_{\omega }^{+}(k)-{\omega }^{66}$.

4. (4)

   Next comes the crucial step of the reduction – at cost of additional $c_1(k){\omega }^{65}+c_2(k){\omega }^{60}$ weight of crossings, we “order” the vertical blue edges which stretch between the paths $P_1$ and $P_2$ as alternating with the internal vertices of the red path $P_0$. This rather long technical step is detailed at the end of the proof, and here we only outline its core idea which is based on simple calculus as follows. Consider an arbitrary quadratic polynomial $p(x)$ which is increasing on ${ℝ}^{+}$. Then, for any $a>0$, the minimum of the function $p(x)+p(y)$ conditioned by $x+y=a$ is attained at $x=y$, that is when $x=a/2$. A slight adjustment (suitable for integer values of $x$) of this idea is used to determine fine weights of the edges of the paths $P_0$ and $P_1$ where, essentially, $x$ means the index of an edge of $P_0$ and $y$ that of an edge of $P_1$. Such fine weights then enforce precise mutual positions of the edges of $P_0$ and $P_1$, and in turn the desired alternating ordering of the vertical red and blue edges incident to $P_0$ and $P_1$. A closer idea of this principle can be obtained by looking at an example of concrete edge weights in Figure 5.

5. (5)

   Points (1)–(4) together imply that the weight of the crossings in $(F_k,B)$ is at least ${\gamma }_{\omega }(k)-3k{\omega }^{52}$. So, none of the paths of $𝒬$ may cross $P_1$ since that would add ${\omega }^{49+4}={\omega }^{53}$. Then each of the paths of $𝒬$ crosses the blue edge $c_2{b}_2$ of weight ${\omega }^{48}+2{\omega }^{38}-{\omega }^{34}$, or the path $R$ plus two sections of the path $P_2$ of combined weight ${\omega }^{48}+2{\omega }^{38}$. Since $2k$ of the paths of $𝒬$ are of weight ${\omega }^4$ and $k$ of them of weight ${\omega }^4-1$, by Theorem 2.1(a), we have at least $({\omega }^{48}+2{\omega }^{38}-{\omega }^{34})(3k{\omega }^4-k)\ge 3k{\omega }^{52}-k{\omega }^{48}+6k{\omega }^{42}-5k{\omega }^{38}$ more crossings from that. Moreover, each of the paths of $𝒬$ crosses sections of $P_2$ between $c_0$–$c_1$ and $c_3$–$c_4$ of weight $\frac{4}{5}{\omega }^{35}$ (plus the edges $b_1{c}_1$ and $b_3{c}_3$), contributing another $\frac{4}{5}{\omega }^{35}(3k{\omega }^4-k)=\frac{12}{5}k{\omega }^{39}-\frac{4}{5}k{\omega }^{35}$. All these together raise the lower bound to at least ${\gamma }_{\omega }(k)-5k{\omega }^{38}-\frac{4}{5}k{\omega }^{35}\ge {\gamma }_{\omega }^{+}(k)-(5k+1){\omega }^{38}$.

6. (6)

   Assume that some of the internal vertices of a path in $𝒬$ lie outside of the gadget region (informally, below $P_2$). That would force an additional crossing between such a path and $c_1{b}_1$ or $c_3{b}_3$ of weight $\ge (1-\frac{4}{5}){\omega }^{35+4}$ (or with e.g. $P_2$ of even higher weight), exceeding ${\gamma }_{\omega }^{+}(k)$. Therefore, every path $Q\in 𝒬$ crosses the path $P_2$ in the two end-edges of $Q$ which are of weight ${\omega }^4$ by the condition in Theorem 2.1(a), and the weights of the edges of $P_2$ crossed by $Q$ are ${\omega }^{38}$ and ${\omega }^{38}+\frac{4}{5}{\omega }^{35}$, respectively. Additionally, all paths of $𝒬$ cross the path $R$ of weight ${\omega }^{48}$ at least with their minimum edge weights ${\omega }^4-1$ or ${\omega }^4$. All this improves the estimate on the crossings carried by the paths of $𝒬$ from (5) to $\ge {\omega }^{48}(3k{\omega }^4-k)+(2{\omega }^{38}+\frac{4}{5}{\omega }^{35})\cdot 3k{\omega }^4=3k{\omega }^{52}-k{\omega }^{48}+6k{\omega }^{42}+\frac{12}{5}k{\omega }^{39}$, which raises our lower bound to the desired value ${\gamma }_{\omega }(k)$.

A drawing with ${\gamma }_{\omega }(k)$ crossings is as in Figure 4 with details as in Figure 5. Hence, we have finished a proof of $\mathrm{cr}{}_{\mathrm{a}}{}^{}(F_k,B)={\gamma }_{\omega }(k)$. Furthermore, if any of the assumptions of the previous analysis was violated, the crossing number would exceed ${\gamma }_{\omega }^{+}(k)$, and any one additional crossing not sketched in Figure 4 and not being only between paths of $𝒬$ would add weight of at least ${\omega }^{30+4}-{\omega }^{30}$, and again ${\gamma }_{\omega }(k)+{\omega }^{34}-{\omega }^{30}>{\gamma }_{\omega }^{+}(k)$, which confirms the rest of Lemma 3.1.

We continue with additional proof details of the two sketched points.

Once we prove that all three edges $c_1{b}_1$, $c_2{b}_2$, $c_3{b}_3$ cross $P_0$, we raise the lower bound from (1) to at least $2{\omega }^{90}-{\omega }^{89}+(4k+2){\omega }^{79}+2{\omega }^{76}-{\omega }^{75}>{\gamma }_{\omega }^{+}(k)-{\omega }^{72}$, and hence $P_2$ could not cross $P_0$ and had to be above it. It thus suffices to analyze all possibilities that some of $c_1{b}_1$, $c_2{b}_2$, $c_3{b}_3$ do not cross $P_0$.

1. i.

   Neither of $c_1{b}_1$, $c_3{b}_3$ cross $P_0$. Then (regardless of $c_2{b}_2$) the weight of crossings of order ${\omega }^{76}$ sums to at least $2\cdot \frac{4}{5}{\omega }^{76}$ between $P_0$ and $P_2$, precisely, with the sections of $P_2$ between $c_0$–$c_1$ and $c_3$–$c_4$. In addition to that, we have a path from $b_0$ to $b_4$, using the edges $b_1{c}_1$, $b_3{c}_3$ and the section of $P_2$ between $c_1$–$c_3$, of weight $\frac{2}{5}{\omega }^{35}$. This path must cross twice the subgraph formed by $P_0^{+}:=P_0\cup \{r_1{r}_1^{\prime },r_3{r}_3^{\prime }\}$ and, importantly, the possible crossing(s) with $P_0$ is in addition to the crossings between $P_0$ and $P_2$ counted in (1) if $b_2{c}_2$ does not cross $P_0$. So, this adds (neglecting the lower-order terms) at least $2\cdot \frac{2}{5}{\omega }^{76}$ more crossings between $P_0^{+}$ and $P_2$. Altogether, with the lower bound of (1), we get at least $2{\omega }^{90}-{\omega }^{89}+(4k+2){\omega }^{79}+\frac{12}{5}{\omega }^{76}-{\omega }^{75}>{\gamma }_{\omega }^{+}(k)$ crossings, which is impossible.

2. ii.

   Exactly one of $c_1{b}_1$, $c_3{b}_3$ crosses $P_0$. We reuse “one half” of the argument in (i.) plus the weight of the crossing of one of $c_1{b}_1$, $c_3{b}_3$ with $P_0$ to derive an analogous contradiction.

3. iii.

   Both of $c_1{b}_1$, $c_3{b}_3$ cross $P_0$, but $b_2{c}_2$ does not. Then the lower bound from the arguments of (1) can be slightly improved, since the path $R$ and twice the path $P_2$ cross $P_0$, and in addition to that, we count the crossings of $c_1{b}_1$ and $c_3{b}_3$ with $P_0$. So, we improve it to at least $2{\omega }^{90}-{\omega }^{89}+(4k+2){\omega }^{79}+2{\omega }^{76}>{\gamma }_{\omega }(k)+{\omega }^{75}-{\omega }^{72}>{\gamma }_{\omega }^{+}(k)$, which is again impossible.

$\mathrm{⊲}$

We first note that the graph $(F_k,B)$ is symmetric along the vertical axis, except the paths of $𝒬$. Since the paths of $𝒬$ are handled only after point (4), we can now assume full symmetry and prove the claim only for the right-hand side of $(F_k,B)$, as depicted in Figure 5, and then multiply the number of crossings by $2$.

We recapitulate where we stand with our drawing of $(F_k,B)$ after steps (1)–(3). We have got pairwise noncrossing cycle $C_0$ and paths $P_1$, $P_0$ and $P_2$ drawn in this order bottom up (Figure 4). All crossings of weight of order ${\omega }^{66}$ and higher have already been counted to equality with ${\gamma }_{\omega }(k)$. There are two edges of weight ${\omega }^{41}-{\omega }^{40}$ between $C_0$ and $P_0$ crossing $P_1$, and $4k$ such edges of weight ${\omega }^{30}$. There is an edge of weight ${\omega }^{48}+2{\omega }^{38}-{\omega }^{34}$ and two edges of weight ${\omega }^{35}$ between $P_1$ and $P_2$ crossing $P_0$, and again $4k$ such edges of weight ${\omega }^{30}$. Besides the already counted weights, these listed edges contribute crossings of weights of order only ${\omega }^{65}$ and ${\omega }^{60}$ (including their possible mutual crossings).

Our proof strategy is the following; we will show a concrete drawing, called the normal drawing, in which the above described crossings contribute exactly as expected in the formula for ${\gamma }_{\omega }(k)$ in the part $c_1(k){\omega }^{65}+c_2(k){\omega }^{60}$ (the drawing in Figure 5), and then we will argue that in any drawing in which the above listed edges (the vertical blue and red ones of weights ${\omega }^{35}$and ${\omega }^{30}$) are not as in our normal drawing, we can decrease the total crossing number by $\mathrm{\Omega }({\omega }^{60})$. This possible drop in the crossing number in turn certifies that the arbitrary considered drawing would exceed ${\gamma }_{\omega }^{+}(k)$ crossings, and hence is impossible in our claim. In this setup of a proof, it also comes for free that all crossings potentially occuring in $(F_k,B)$, which are not counted prior to this point and are not among the crossings listed above, are of weight of order strictly less than ${\omega }^{60}$.

The weights of the edges of $P_0$ and $P_1$ are precisely as follows (Figure 5):

• $\mathrm{■}$

  For $P_0$, $V(P_0)=(r_0,r_0^1,\mathrm{\dots },r_0^{2k},r_1,r_3,r_0^{2k+1},\mathrm{\dots },r_0^{4k},r_4)$, the weight of $r_1{r}_3$ is exactly ${\omega }^{41}$, the weight of $r_0^{2k}{r}_1$ and of $r_3{r}_0^{2k+1}$ is ${\omega }^{41}+\frac{2}{5k+7}{\omega }^{30}$, the weight of $r_0^{2k+i-1}{r}_0^{2k+i}$ and of $r_0^{2k-i+1}{r}_0^{2k-i}$ is ${\omega }^{41}+\frac{i(i+1)}{5k+7}{\omega }^{30}$ for $i=2,\mathrm{\dots },2k$, and the weight of $r_0{r}_0^1$ and of $r_0^{4k}{r}_4$ is ${\omega }^{41}+\frac{(2k+1)(2k+2)}{5k+7}{\omega }^{30}$.

• $\mathrm{■}$

  For $P_1$, $V(P_1)=(b_0,b_0^1,\mathrm{\dots },b_0^k,b_1,b_0^{k+1},\mathrm{\dots },b_0^{2k},b_2,b_0^{2k+1},\mathrm{\dots },b_0^{3k},b_3,b_0^{3k+1},$ $\mathrm{\dots },b_0^{4k},b_4)$, we resort to describing the weights only from $b_2$ till $b_4$. The weight of $b_2{b}_0^{2k+1}$ is exactly ${\omega }^{49}$, the weight of $b_0^{2k+i}{b}_0^{2k+i+1}$ is ${\omega }^{49}+\frac{i(i+2)}{5k+7}{\omega }^{30}$ for $i=1,\mathrm{\dots },k-1$, the weight of $b_0^{3k}{b}_3$ is ${\omega }^{49}+\frac{k(k+2)}{5k+7}{\omega }^{30}$, the weight of $b_3{b}_0^{3k+1}$ is ${\omega }^{49}+\frac{2}{5}{\omega }^{35}+\frac{(k+1)(k+3)}{5k+7}{\omega }^{30}$, the weight of $b_0^{3k+i}{b}_0^{3k+i+1}$ is ${\omega }^{49}+\frac{2}{5}{\omega }^{35}+\frac{(i+k+1)(i+k+3)}{5k+7}{\omega }^{30}$ for $i=1,\mathrm{\dots },k-1$, and the weight of $b_0^{4k}{b}_4$ is ${\omega }^{49}+\frac{2}{5}{\omega }^{35}+\frac{(2k+1)(2k+3)}{5k+7}{\omega }^{30}$.

We count the crossings in a normal drawing as in Figure 5:

• $\mathrm{■}$

  Concerning total crossings of weight of order ${\omega }^{65}$, we have $2k$ red edges of weight ${\omega }^{30}$ crossing the sections of $P_1$ between $b_0$–$b_1$ and $b_3$–$b_4$, and two blue edges of weight ${\omega }^{35}$ crossing $P_0$ in edges of weight $\frac{(k+1)(k+2)}{5k+7}$. In total

  $2k{\omega }^{30}\cdot {\displaystyle \frac{2}{5}}{\omega }^{35}+2{\omega }^{35}\cdot {\displaystyle \frac{(k+1)(k+2)}{5k+7}}{\omega }^{30}={\displaystyle \frac{2}{5(5k+7)}}(30k^2+58k+20){\omega }^{65}=c_1(k){\omega }^{65}.$

• $\mathrm{■}$

  Concerning total crossings of weight of order ${\omega }^{60}$, and considering only the right-hand side as in Figure 5, we get crossings of $2k$ red edges of weight ${\omega }^{30}$ with the edges of $P_1$ from $b_0^{2k+1}$ to $b_0^{4k}$, and crossings of $2k$ blue edges of weight ${\omega }^{30}$ with the edges of $P_0$ from $r_3$ to $r_4$ except with the edge of weight $\frac{(k+1)(k+2)}{5k+7}$ (counted in the previous point). These sum to

  	${\omega }^{30}\cdot$		${\displaystyle \sum _{i=1}^{2k}}{\displaystyle \frac{i(i+2)}{5k+7}}{\omega }^{30}+{\omega }^{30}\cdot \left[{\displaystyle \sum _{i=1}^{2k+1}}{\displaystyle \frac{i(i+1)}{5k+7}}-{\displaystyle \frac{(k+1)(k+2)}{5k+7}}\right]{\omega }^{30}$
  			$={\displaystyle \frac{1}{3(5k+7)}}(16k^3+39k^2+20k),$

  which multiplied by $2$ gives $c_2(k)$.

Now, we handle an arbitrary drawing of $(F_k,B)$ which conforms to the bounds shown in (1)–(3), but is not our normal drawing described by Figure 5. As argued above, it is enough for this purpose to consider only edges depicted in Figure 5, and know that the depicted vertical edges indeed cross the horizontal paths $P_1$ and $P_2$ somewhere. Crossings of weight of order strictly higher than ${\omega }^{65}$ are not relevant in this analysis (as they are enforced and have been counted, and so new such ones cannot even arise), and crossings of weight of order strictly less than ${\omega }^{60}$ can be ignored at this stage (by the choice of sufficiently large $\omega$).

We denote by $t_i^0=\frac{i(i+1)}{5k+7}$ and $t_i^1=\frac{i(i+2)}{5k+7}$, and refer to Figure 5. The $i$-th edge of the red path $P_0$, counted from $r_3$ towards $r_4$, is of weight ${\omega }^{41}+t_i^0{\omega }^{30}$, and the $(i+1)$-th edge of the blue path $P_1$, counted from $b_2$ towards $b_4$, is of weight ${\omega }^{49}+t_i^1{\omega }^{30}$, resp. of weight ${\omega }^{49}+\frac{2}{5}{\omega }^{35}+t_i^1{\omega }^{30}$ if $i>k$. We also denote the vertical red edges (of weight ${\omega }^{30}$) incident to the path $P_0$ by $f_1^0,\mathrm{\dots },f_{2k}^0$ such that $f_i^0$ is incident to the vertex $r_0^{2k+i}$, and the vertical blue edges (of weight again ${\omega }^{30}$) incident to the path $P_1$ by $f_1^1,\mathrm{\dots },f_{2k+1}^1$ such that $f_i^1$ is incident to the vertex $b_0^{2k+i}$ for $i\le k$,  $f_{k+1}^1$ is incident to $b_3$, and $f_i^1$ is incident to $b_0^{2k+i-1}$ for $i\ge k+2$.

One can easily check that in our normal drawing, we have, naturally, $f_i^0$ crossing $P_1$ in the edge of weight coefficient $t_i^1$,  $f_j^1$ crossing $P_0$ in the edge of weight coefficient $t_j^0$, and no $f_i^0$ is crossing any $f_j^1$. Assume that the drawing of $f_i^0$ violates some of the previous conditions.