From Local Pair-Crossing Number to Local Crossing Number

Let $G$ be a graph on $n$ vertices and $m$ edges, $e_1,\mathrm{\dots },e_m\in E(G)$, and let $𝒟(G)$ be a drawing of $G$ in the plane such that each edge in $G$ crosses at most $k$ other edges. Let $ℛ$ be the rotation system of the drawing $𝒟(G)$. If $G$ is not connected, we can pull apart the drawing $𝒟(G)$ so that the connected components do not interact with one another. So, we may assume without loss of generality that $G$ is a connected graph, and let $T$ be a spanning tree of $G$. Furthermore, let us assume that $T=\{e_1,\mathrm{\dots },e_{n-1}\}$, and for each $i\in [n-1]$, the edges $e_1,\mathrm{\dots },e_i$ form an edge-induced connected subgraph of $G$. We will need the following lemma.

For each $i\in [n-1]$, we will greedily construct the subcurves ${\alpha }_1,\mathrm{\dots },{\alpha }_i$ with the properties described above, such that for ${𝒯}_i={\bigcup }_{j=1}^i{\alpha }_j$, ${𝒯}_i$ is simply connected and contains all of the endpoints of the edges $e_1,\mathrm{\dots },e_i$.

We start with ${\alpha }_1=e_1$. Having defined ${\alpha }_1,\mathrm{\dots },{\alpha }_{i-1}$ with the desired properties, we obtain ${\alpha }_i$ as follows. Consider edge $e_i\in T$. Since the edges $e_1,\mathrm{\dots },e_{i-1}$ form an edge-induced connected subgraph of $G$, and the drawing ${𝒯}_{i-1}={\bigcup }_{j=1}^{i-1}{\alpha }_j$ contains the endpoints of $e_1,\mathrm{\dots },e_{i-1}$, exactly one of the endpoints of $e_i$ lies in ${𝒯}_{i-1}$. Let $u$ be the endpoint of $e_i$ that does lie in ${𝒯}_{i-1}$ and $v$ be the other endpoint that does not lie in ${𝒯}_{i-1}$. Then we define ${\alpha }_i$ by starting at vertex $v$ and tracing along the curve $e_i$ until we reach a point on ${𝒯}_{i-1}$, which is either a crossing point or a vertex. Clearly, ${𝒯}_i={𝒯}_{i-1}\cup {\alpha }_i$ is simply connected and contains the endpoints of the edges $e_1,\mathrm{\dots },e_i$. $◀$

Let ${\alpha }_i\subset e_i$, $1\le i\le n-1$, be the subcurves from Lemma 4, and let $𝒯={\bigcup }_{i=1}^{n-1}{\alpha }_i$. We then define $\gamma$ to be a simple closed curve drawn very close to $𝒯$, such that $𝒯$ lies inside of $\gamma$, that is, $𝒯$ lies in the closed connected component of ${ℝ}^2\setminus \gamma$. Moreover, $\gamma$ will not contain any crossing points in our drawing $𝒟(G)$, and apart from the crossing points on $𝒯$, all other crossing points will lie outside of $\gamma$. For each subcurve ${\alpha }_i\in 𝒯$, let ${\beta }_i$ be a simple closed curve drawn very close to ${\alpha }_i$, such that ${\beta }_i$ lies inside of $\gamma$, the endpoints of ${\alpha }_i$ lie on ${\beta }_i$, and all crossing points along ${\alpha }_i$ lie inside of ${\beta }_i$. Moreover, for $j\ne i$, the crossing points along the curve ${\alpha }_j$ lie outside of ${\beta }_i$. Hence, either ${\beta }_i$ and ${\beta }_j$ are disjoint, or they are tangent if ${\alpha }_i$ and ${\alpha }_j$ have a common endpoint, or ${\beta }_i$ and ${\beta }_j$ have two points in common if an endpoint of ${\alpha }_i$ lies in the interior of ${\alpha }_j$ (or vice versa).

By construction, for each subcurve ${\alpha }_i$, there are $t\le k$ edges $e_{j_1},\mathrm{\dots },e_{j_t}\in E(G)$ that cross ${\alpha }_i$. Inside of ${\beta }_i$, we can redraw each edge $e_{j_1},\mathrm{\dots },e_{j_t}$ so that it intersects the curve ${\alpha }_i$ at most once as follows. By starting at one of the endpoints of $e_{j_r}$, we trace along $e_{j_r}$ until it intersects ${\beta }_i$ for the first time, which is right before it would intersect ${\alpha }_i$. We denote this subcurve as $f_{j_r}$ (the first part of $e_{j_r}$). Likewise, by starting at the other endpoint of $e_{j_r}$, we again trace along $e_{j_r}$ until it intersects ${\beta }_i$ for the first time, and denote this subcurve as ${\mathrm{\ell }}_{j_r}$ (the last part of $e_{j_r}$). We then delete the part of $e_{j_r}$ between $f_{j_r}$ and ${\mathrm{\ell }}_{j_r}$ (the middle part of $e_{j_r})$, and then connect $f_{j_r}$ and ${\mathrm{\ell }}_{j_r}$ by drawing a curve inside of ${\beta }_i$ from the endpoint of $f_{j_r}$ on ${\beta }_i$ to the endpoint of ${\mathrm{\ell }}_{j_r}$ on ${\beta }_i$. Clearly, this can be done so that this new drawing of $e_{j_r}$ crosses ${\alpha }_i$ at most once. We can perform this redrawing procedure to each $e_{j_1},\mathrm{\dots },e_{j_t}$ such that afterwards, each pair of edges $e_{j_r}$, $e_{j_w}\in \{e_{j_1},\mathrm{\dots },e_{j_t}\}$ will have at most one crossing point between them inside of ${\beta }_i$, and each such edge $e_{j_r}$ crosses ${\alpha }_i$ at most once. See Figure 1. After applying this redrawing procedure for each ${\alpha }_i$, let ${𝒟}^{\prime }(G)$ denote the new drawing of $G$ in the plane. Hence, no additional crossings were created outside of $\gamma$ in ${𝒟}^{\prime }(G)$, and the rotation system $ℛ$ in the new drawing has not changed.

Given ${𝒟}^{\prime }(G)$, we now redraw the edges of $G$ outside of $\gamma$ as follows. First notice that for each edge $e_i\in E(G)$, $e_i$ will cross $\gamma$ at most $2k+2$ times in ${𝒟}^{\prime }(G)$. Indeed, starting at one of the endpoints of $e_i$, we move along $e_i$ and first cross $\gamma$ without crossing $𝒯$. Continuing along $e_i$, since $e_i$ will cross at most $k$ subcurves ${\alpha }_i$, we have another possible $2k$ crossing points on $\gamma$. Finally, as we approach the other endpoint of $e_i$, we cross $\gamma$ one last time for a total of at most $2k+2$ crossing points along $\gamma$. Hence, outside of $\gamma$, each edge $e_i$ will give rise to at most $k+1$ pairwise disjoint outer arcs, with end points on $\gamma$. See Figure 2. Hence, all of the edges in $G$ will give rise to at most $(k+1)|E(G)|$ outer arcs outside of $\gamma$. Given the circular structure of the endpoints of these outer arcs by $\gamma$, we can redraw all of the outer arcs outside of $\gamma$ such that any two outer arcs cross at most once, and the endpoints of each outer arc remain the same. Moreover, if edges $e_i$ and $e_j$ did not cross outside of $\gamma$, then they still do not cross outside of $\gamma$ in the new drawing. After we redraw the outer arcs as described above, let ${𝒟}^{\prime \prime }(G)$ be the new and final drawing of $G$ in the plane, and notice that the rotation system of ${𝒟}^{\prime \prime }(G)$ is the same as the rotation system of $𝒟(G)$. Also notice that since each edge consists of at most $k+1$ outer arcs, two edges $e_i$ and $e_j$ will create at most ${(k+1)}^2$ crossing points outside of $\gamma$ in ${𝒟}^{\prime \prime }(G)$.

Finally, we show that each edge $e_i$ in the final drawing ${𝒟}^{\prime \prime }(G)$ has at most $k(k+1)(k+2)$ crossing points. By the above, the number of crossing points on $e_i$ outside of $\gamma$ is at most $k{(k+1)}^2$, since $e_i$ crosses at most $k$ other edges, and any two will create at most ${(k+1)}^2$ crossing points outside of $\gamma$. In order to bound the number of crossing points on $e_i$ inside of $\gamma$, let us consider the following two cases.

Suppose that $e_i\notin T$. Recall that there are at most $k$ subcurves ${\alpha }_j$ that cross $e_i$, and for each subcurve ${\alpha }_j$, there are at most $k-1$ other edges that cross ${\alpha }_j$. Hence, $e_i$ will have at most $k$ crossing points inside of ${\beta }_j$, giving us a total of at most $k^2$ crossing points on $e_i$ inside of $\gamma$.

Suppose $e_i\in T$. Again, there are at most $k$ subcurves ${\alpha }_j$ that cross $e_i$, and for each subcurve ${\alpha }_j$ with $j\ne i$, there are at most $k-1$ other edges that cross ${\alpha }_j$. Moreover, $e_i$ could have an additional $k$ crossing points along ${\alpha }_i$ inside of ${\beta }_i$. Hence, $e_i$ will have at most $k^2+k$ crossing points inside of $\gamma$.

Putting everything together, each edge in ${𝒟}^{\prime \prime }(G)$ has at most $k{(k+1)}^2+k^2+k=k(k+1)(k+2)$ crossings. $◀$

Suppose $G$ has local pair-crossing number at most $k$. If there is an edge with more than $2^k$ crossings on it, then by applying Lemma 9.2 in [17], we can simplify the drawing without creating any new pair of crossing edges (that is, the local pair-crossing number remains at most $k$), and without increasing the number of crossings along any edge. Repeating this step for each edge of $G$, we end up with a drawing of $G$ having local crossing number at most $2^k$.

In the forthcoming journal version of this note, we show that it is possible to improve the bound in Theorem 2 to $\text{loc-cr}(G)\le \text{loc-pair-cr}{(G)}^{2.5+o(1)}$ by a more involved argument.

Using the redrawing technique used in the proof of Theorem 2, one can show that for any multigraph $G$, $\text{cr}(G)=O(\text{pair-cr}{(G)}^{5/3})$. Although this is weaker than the result stated in the introduction due to Solé Pi, we plan to include the proof in the forthcoming journal version for the interested reader.