Pair crossing number, cutwidth, and good drawings on arbitrary point sets

Let $G=(V,E)$ be as in the theorem. We restrict ourselves to the case in which $G$ has no isolated vertex.

First, we show that $G$ contains an $r$-edge-balanced separator of size $O_{r}(\sqrt{m})$. Consider a collection of curves realizing $G$, we may assume that no three curves go through the same point. Let $t$ be a fixed positive integer, to be specified later. We construct an auxiliary string in order to apply Theorem 2.1. For each pair of adjacent curves, choose an arbitrary common point between them and add $t$ pairwise disjoint auxiliary curves around it that cross both of the original curves but intersect no other curve. Let $H\supset G$ be the string graph that corresponds to this new family of curves, then $H$ has $\lvert V\rvert+tm$ vertices and $(t+1)m$ edges. There is clearly a $\frac{2}{3}$-balanced separator for $H$ of minimal size which contains none of the auxiliary curves and, by Theorem 2.1, it has no more than $c_{t}\sqrt{m}$ vertices for some $c_{t}$ that depends only on $t$. Let $S_{H}$ be such a separator and consider the partition $V_{H,1}\cup V_{H,2}\cup S_{H}$ induced by $S_{H}$; we have that $\lvert V_{H,1}\rvert,\lvert V_{H,2}\rvert\leq\frac{2}{3}(\lvert V\rvert+tm)\leq\frac{2}{3}(t+2)m$. Notice that $S_{H}$ is also a separator in $G$ and that the two induced subgraphs $G[V_{H,1}\cap V]$ and $G[V_{H,2}\cap V]$ have at most $\lvert V_{H,1}\rvert/t$ and $\lvert V_{H,2}\rvert/t$ edges, respectively (each edge in the induced subgraphs corresponds to $t$ auxiliary curves). Since both of these quantities are at most $\frac{2}{3}\frac{t+2}{t}m$, taking $t$ large enough yields the result.

For the second part, we follow the proof of Lemma 5 in [7]. Let $S\subset V$ be a $\frac{2}{3}$-balanced separator of minimal size and $V=V_{1}\cup V_{2}\cup S$ be the partition induced by $S$, so that $G[V_{1}]$ has at most as many edges as $G[V_{2}]$. If $G[V_{2}]$ contains no more than $r\lvert E\rvert$ edges, then $S$ is the desired separator. Otherwise, take a small $\epsilon>0$ (to be specified later) and, within $G[V_{2}]$, consider a $\left(\frac{2}{3}+\epsilon\right)$-edge-balanced separator $S^{\prime}\subset V_{2}$ of minimal size and the partition $V_{2}=V_{3}\cup V_{4}\cup S^{\prime}$ induced by it; suppose that $\lvert V_{3}\rvert\leq\lvert V_{4}\rvert$. If $\lvert V_{4}\rvert\geq\frac{1}{3}\lvert V\rvert$, then we are done by taking the separator $S\cup S^{\prime}$ and the partition $V=(V_{1}\cup V_{3})\cup(V_{4})\cup(S\cup S^{\prime})$. Suppose that $\lvert V_{4}\rvert<\frac{1}{3}\lvert V\rvert$ and let $S^{\prime\prime}$ be a $\frac{2}{3}$-balanced separator of minimal size for $G[V_{1}]$ and $V_{1}=V_{5}\cup V_{6}\cup S^{\prime\prime}$ be the partition induced by it; assume that $\lvert V_{5}\rvert\leq\lvert V_{6}\rvert$. We claim that (if $\epsilon$ is small enough) the separator $Z=S\cup S^{\prime}\cup S^{\prime\prime}$ and the partition $V=(V_{3}\cup V_{6})\cup(V_{4}\cup V_{5})\cup Z$ have the required properties.

For starters, both $G[V_{3}\cup S\cup S^{\prime\prime}]$ and $G[V_{4}\cup S\cup S^{\prime\prime}]$ contain at least $r\lvert E\rvert\left(\frac{1}{3}-\epsilon\right)$ edges. Since $r>\frac{3}{4}$, for small enough $\epsilon$ this quantity will be larger than $(1-r)\lvert E\rvert$. It follows that both $G[V_{3}\cup V_{6}]$ and $G[V_{4}\cup V_{5}]$ have at most $r\lvert E\rvert$ edges, so $Z$ is an $r$-edge-balanced separator.

Now we prove that $Z$ is a $\frac{2}{3}$-balanced separator. We have that

and

The result follows. ∎

Consider a drawing $D$ of $G$ which exhibits $\mathop{\mathrm{pcr}}(G)$. For each pair of edges which cross and share an endpoint we draw a small auxiliary curve that intersects only one of them and no other edge. Consider the string graph $H$ induced by the closures of the resulting collections of curves (this way, any two edges sharing an endpoint correspond to adjacent vertices of $H$). Notice that each edge in this string graph corresponds, in a way, to either a pair of crossing edges of $G$ or a pair of edges of $G$ with a common endpoint. By Theorem 2.2, $H$ admits a $\frac{3}{4}$-edge-balanced separator of size $O\big{(}\sqrt{\mathop{\mathrm{pcr}}(G)+\mathop{\mathrm{bds}}(G)}\big{)}$. It is not hard to see that, after removing from it all of the auxiliary curves, this separator does the job. ∎

Let $c$ be the hidden constant in Lemma 2.3 and consider a set of at most $c\sqrt{\mathop{\mathrm{pcr}}(G)+\mathop{\mathrm{bds}}(G)}$ edges whose removal disconnects the graph into subgraphs $G_{1}$ and $G_{2}$, as in said corollary. By placing all vertices of $G_{1}$ before those of $G_{2}$ in the linear order and adding back in the deleted edges, we get that

which, due to the bounds given by Lemma 2.3, solves to

as desired. ∎

Notice that $a_{i+1}-a_{i}<20$ for all $1\leq i\leq 1000$.

Consider a set of edges as in Lemma 2.3 and let $H_{1}^{\prime}$ and $H_{2}^{\prime}$ be the two subgraphs that are obtained after the removal of said edges. Assume, w.lo.g., that the number of vertices of $H_{1}^{\prime}$, which we denote by $r$, is at most $n/2$ and satisfies $a_{j}\leq r<a_{j+1}$. If $r=a_{j}$ then the set of edges has all the required properties. Otherwise, we will round the partition by moving $a_{j+1}-r$ vertices from $H_{2}^{\prime}$ to $H_{1}^{\prime}$.

Apply Theorem 1.2 to $H_{2}^{\prime}$ to get a linear ordering of its vertices. By cutting the $a_{j+1}-r$ vertices vertices on either extreme of this ordering and adjoining them to $H_{1}^{\prime}$, we get a partition which still has no more than $O\big{(}\sqrt{\mathop{\mathrm{pcr}}(G)+\mathop{\mathrm{bds}}(G)}\big{)}$ edges running between the two parts; this could cause $\mathop{\mathrm{pcr}}(H_{1})+\mathop{\mathrm{bds}}(H_{1})$ to grow too large, however. In order to fix this issue, we observe that the proof of Theorem 1.2 actually provides us with a way of constructing many linear orderings which attain small cutwidth (indeed, at every step of the recursive process we get to choose which of the two subgraphs is placed on the left side and which one is placed on the right side). Since $H_{2}^{\prime}$ contains at least $5000$ vertices and $a_{j+1}-r<a_{j+1}-a_{i}<20$, we can find several ($8$ is enough for our purposes) linear orderings which attain the desired cutwidth and such that no vertex of the graph appears amongst the first $a_{j+1}-r$ elements in more than one order. At least one of these pairwise disjoint sets of $a_{j+1}-r$ vertices will be such that moving its elements from $H_{2}^{\prime}$ to $H_{1}^{\prime}$ we get two graphs $H_{1}$ and $H_{2}$ that satisfy the required properties, or else we would be able to move all of the vertices in these sets to $H_{1}^{\prime}$ simultaneously to obtain a subgraph $H$ of $G$ with $\mathop{\mathrm{pcr}}(H)+\mathop{\mathrm{bds}}(H)>\mathop{\mathrm{pcr}}(G)+\mathop{\mathrm{bds}}(G)$, which is clearly not possible. ∎

Note that $l\leq 2k$. We prove the lemma by induction on $k$. Construct a string graph $H$ from the crossing edges of $\mathcal{D}$ (two vertices of $H$ are adjacent if and only if the corresponding edges cross each other). Let $S$ be a $\frac{3}{4}$-edge-balanced separator of size $O(\sqrt{k})$ for the graph $H$ and consider the vertex disjoint subgraphs $H_{1}$ and $H_{2}$ induced by it. Let $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ be the drawings formed by the edges of $H_{1}$ of and $H_{2}$, respectively, and denote by $k_{1}$ and $k_{2}$ the number of pairs of crossing edges in each of them. W.l.o.g., $k_{1}\geq k_{2}$. By the inductive hypothesis, these drawings can be modified so that they contain no more than $ck_{1}^{3/2}$ and $ck_{2}^{3/2}$ crossings, respectively, and the edges are drawn in a small neighborhood of the original edges. Color the edges in $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ blue and those in $S$ red, and let $BB$, $BR$ and $RR$ denote the number of crossings of each of the three possible kinds. As in [29], a simple procedure allows us to redraw the edges so that the triple $(BB,BR,RR)$ is not lexicographically larger than it was at the start, and any pair of edges crosses at most once. This results in a drawing with no more than

crossings. For any large enough $c$ the right hand side will be at most $clk^{1/2}$, and this concludes the proof. We refer the reader to [29] or [14] for details about the redrawing step used above. ∎

Consider a drawing of $G$ which attains $\mathop{\mathrm{pcr}}(G)$. By Lemma 3.1, $G$ can be redrawn so that it has no more than $c\cdot 2\mathop{\mathrm{pcr}}(G)\cdot\mathop{\mathrm{pcr}}(G)^{1/2}=O(\mathop{\mathrm{pcr}}(G)^{3/2})$ crossings. The result follows. ∎

We shall construct a drawing of $G$ with $O(\log n(\mathop{\mathrm{pcr}}(G)+\mathop{\mathrm{ssqd}}(G)))$ crossings. In order to achieve this, we build a linear ordering of $V$ as was done in the proof of Theorem 1.2 and then use it to embed the vertices on a circle arc in the natural way; the edges will simply be drawn as segments between the corresponding endpoints. We count the number of crossings in this drawing by looking at the partition tree that was already implicit in the proof of Theorem 1.2, this step is a bit trickier than one might expect. We move on to the actual proof.

Lemma 2.3 provides us with a partition of $G$ into subgraphs $G_{1}$ and $G_{2}$. We split the circle arc in half and recursively embed $G$ by placing the vertices of $G_{1}$ on one of the two smaller arcs and those of $G_{2}$ on the other one, and then adding back the edges of the separator.

Let $T$ denote the rooted binary tree representing the recursive partitioning of $G$ used above. That is, the root corresponds to $V$ and every other vertex represents a proper subset of $V$, such that the two children of a non-leaf vertex $t\in T$ associated to a set $V_{t}$ correspond to the two sets constituting the partition of $V_{t}$ provided by Lemma 2.3. We denote the induced subgraph of $G$ with vertex set $V_{t}$ by $G_{t}$, notice that this is the graph that gets split at vertex $t$.

The endpoints of each edge of $G$ are separated at some step of the partitioning process; this gives a natural way of assigning to each edge $e$ of $G$ a vertex $t(e)$ of $T$. It is not hard to see that if two edges $e$ and $e^{\prime}$ cross in our drawing of $G$, then either $t(e)$ is an ancestor of $t(e^{\prime})$ or $t(e^{\prime})$ or vice versa. We charge a crossing between $e$ and $e^{\prime}$ to $e$ if $t(e)$ is an ancestor of $t(e^{\prime})$, and we charge it to $e^{\prime}$ otherwise. For each non-leaf vertex $t$ of $T$, denote by $E(t)$ the set of edges of $G$ that are assigned to $t$ (i.e., the set of edges which have an endpoint in each of the two sets represented by the children of $t$). For any two distinct vertices $u$ and $v$ of $G$, let $P(u,v)$ be the path in $T$ that connects the leafs representing $\{u\}$ and $\{v\}$. Even et al. [7] made the simple observation that for any edge $e=(u,v)$, summing $\lvert E(t)\rvert$ over all of the vertices in $P(u,v)$ yields an upper bound on the number of crossings that are charged to $e(t)$. Thus, the bounds provided by Theorem 2.3 imply that the number of crossings that are charged to $e$ is at most

where the equality follows from the exponential decay guaranteed by Theorem 2.3.

At the partition step corresponding to a vertex $t$ of $T$, the number of edges that were removed is $O\big{(}\sqrt{\mathop{\mathrm{pcr}}(G_{t})+\mathop{\mathrm{bds}}(G_{t})}\big{)}$. Whence, the total number of crossings charged to these edges is $O(\mathop{\mathrm{pcr}}(G_{t})+\mathop{\mathrm{bds}}(G_{t}))$. Each level of $T$ corresponds to a partition of the vertex set of $G$. Thus, summing over all vertices at a fixed level of $T$, we get no more than $O(\mathop{\mathrm{pcr}}(G)+\mathop{\mathrm{bds}}(G))$ crossings (see Observation 3.2 below). Since $T$ has depth $O(\log n)$, the total number of crossings in the drawing is at most

as desired. ∎

We may and will assume that $s\geq 1000$. At a high level, the proof consists of repeatedly applying Lemma 2.4 until every subgraph has the desired number of vertices.

Let $m_{i}=n_{2i}+n_{2i+1}$ and partition the $m_{i}$’s into $1000$ blocks such that the ratio between the largest sum of a block and the smallest sum of a block is as little as possible; it is not hard to see that this ratio will not be larger than $2$. Denote by $S_{1},S_{2},\dots,S_{1000}$ the sums of the blocks and set $a_{k}=\sum_{i=1}^{k}S_{i}$. The $a_{i}$’s satisfy the conditions of Lemma 2.4, so we can choose $O\big{(}\sqrt{\mathop{\mathrm{pcr}}(G)+\mathop{\mathrm{bds}}(G)}\big{)}$ edges such that deleting them allows us to split $G$ into two subgraphs whose orders can be written as sums of two disjoint subcollections of the $m_{i}$’s; furthermore, each of these subcollections contains at least $1/2000$ of the $m_{i}$’s. We keep applying Lemma 2.4 to partition the subgraphs that arise until the order of each of them corresponds to the sum of at most $1000$ of the $m_{i}$’s. The following argument, which will allows us to bound the number of edges that have been removed up to this point, is similar to the one used to prove Corollary 5 in [21]. Consider the family $\mathcal{H}$ of all subgraphs of $G$ that appeared at some point during the decomposition procedure, we will assign a non negative integer to each element of $\mathcal{H}$, which we call the height of the subgraph. The subgraphs that remain at the end of the process get assigned a $0$. All other heights are obtained recursively by following the following rule: if $H\in\mathcal{H}$ got split into subgraphs $H_{1}$ and $H_{2}$ (which are also in $\mathcal{H}$), then its height is one plus the maximum amongst the heights of $H_{1}$ and $H_{2}$. Each subgraph of height $j$ corresponds to a subcollection of at least $(1+1/2000)^{j}$ of the $m_{i}$’s, and it is not hard to see that any two subgraph with the same height are vertex disjoint. Thus, by Observation 3.2, we have

Summing over all levels, we obtain that

Whence the number of edges that have been removed up to this point is $O\big{(}s^{1/2}\sqrt{\mathop{\mathrm{pcr}}(G)+\mathop{\mathrm{bds}}(G)}\big{)}$.

Next, for each subgraph $H\subset G$ that remains at the end of the process described above, we consider a linear ordering of its vertices which exhibits cutwidth $O\big{(}\sqrt{\mathop{\mathrm{pcr}}(H)+\mathop{\mathrm{bds}}(H)}\big{)}$ (recall that Theorem 1.2 guarantees the existence of such an order). Let $m_{j},m_{j+1},\dots,m_{j+t}$ denote the $m_{i}$’s that correspond to $H$ ($t<1000$) and observe that, using the aforementioned ordering, $H$ can be partitioned into subgraphs $G_{2j},G_{2j+1},\dots,G_{2(j+t)+1}$ of orders $n_{2j},n_{2j+1},\dots,n_{2(j+t)+1}$ by deleting $O\big{(}\sqrt{\mathop{\mathrm{pcr}}(H)+\mathop{\mathrm{bds}}(H)}\big{)}$ edges (the number of cuts required is bounded by a constant). Again by Observation 3.2, the total number of edges that need to be removed in this last step is also $O\big{(}s^{1/2}\sqrt{\mathop{\mathrm{pcr}}(G)+\mathop{\mathrm{bds}}(G)}\big{)}$.

The desired bound on $\mathop{\mathrm{pcr}}(G_{i})+\mathop{\mathrm{bds}}(G_{i})$ follows directly from the bounds provided by Lemma 2.4 and the fact that each $H\in\mathcal{H}$ was the result of applying said lemma $\Theta(\log s)$ times during the first part of the decomposition process. ∎

Suppose that $\lvert S\rvert\geq n^{C}$ for some $C\geq 1$ to be chosen later. Let $k\geq 3$ be an integer and assume that $n\geq k$. Apply Corollary 4.4 to $S$ and let $S_{1},S_{2},\dots,S_{k}\subset S$ be the resulting subsets. Now, we use Lemma 2.4 to find $O\big{(}k^{1/2}\sqrt{\mathop{\mathrm{pcr}}(G)+\mathop{\mathrm{bds}}(G)}\big{)}$ edges whose deletion splits $G$ into $k$ graphs $G_{1},G_{2},\dots,G_{k}$ such that the orders of any two of them differ by at most $1$ and

(if $k$ is odd, we set $a_{2s}=0$). We fix a value of $k$ so that $\mathop{\mathrm{pcr}}(G_{i})+\mathop{\mathrm{bds}}(G_{i})\leq\frac{1}{5}(\mathop{\mathrm{pcr}}(G)+\mathop{\mathrm{bds}}(G))$ is guaranteed for every $i$; $k$ is independent of $G$ and $S$ and it will remain constant throughout the rest of the proof.

We shall construct a drawing which maps the vertices of $G_{i}$ to points in $S_{i}$ for every $i$; this is achieved by recursively applying the process above, narrowing the possible locations of the vertices at every step. To be precise, if at some point we have a subgraph $H\subset G$ of order at least $k$ whose vertices must be represented by points of a subset $S^{\prime}\subset S$, then we use Corollary 4.4 to find $k$ subsets of $S^{\prime}$ and Lemma 2.4 to partition $H$ into $k$ subgraphs, which get assigned to the point sets. Repeat this until every resulting subgraph has order less than $k$ and then map the vertices (injectively) to any point in the corresponding subset of $S$. For the procedure to work, all the subsets of $S$ that remain at the end must contain at least $k-1$ points, this will be the case so long as

where $c(k)$ is the constant given by Corollary 4.4. The above inequality holds if $C$ is large enough.

We bound the number of crossings in the resulting drawing as in the proof of Theorem 1.5. The partition scheme of $G$ used above can be represented by a rooted tree $T$ (the leafs of $T$ correspond to vertices of $G$); this time, $T$ has maximum degree $k$. Define $G_{t}$, $t(e)$ and $E(t)$ as before and for every vertex $t$ of $T$ let $\ell(t)$ denote the distance from $t$ to the root.

The fact that the sets produced by Corollary 4.4 have pairwise disjoint convex hulls implies that if two edges $e$ and $e^{\prime}$ cross, then either $t(e)$ is an ancestor of $t(e^{\prime})$ or $t(e^{\prime})$ is an ancestor of $t(e)$. A was done earlier, a crossing between edges $e$ and $e^{\prime}$ is charged to either $e$ or $e^{\prime}$, depending on which of $t(e)$ and $t(e^{\prime})$ is closer to the root. Let $d\geq 0$ be an integer. Consider an arbitrary edge $e$ of $G$ and write $t=t(e)$; by Observation 4.2, there are at most $2^{d}$ vertices $t^{\prime}$ of $T$ such that the following holds: $\ell(t^{\prime})=\ell(t)+d$ and $e$ crosses at least one edge of $E(t^{\prime})$. Recall that $\lvert E(t^{\prime})\rvert=O\big{(}\sqrt{\mathop{\mathrm{pcr}}(G_{t}^{\prime})+\mathop{\mathrm{bds}}(G_{t}^{\prime})}\big{)}$, hence the choice of $k$ ensures that

Summing over all possibilities for $t^{\prime}$, we get at most

thus the number of crossings charged to $e$ is bounded by $O\big{(}\sqrt{\mathop{\mathrm{pcr}}(G_{t})+\mathop{\mathrm{bds}}(G_{t})}\big{)}$, and the total number of crossings charged to edges that were split at $t$ is at most $O\big{(}\lvert E(t)\rvert\sqrt{\mathop{\mathrm{pcr}}(G_{t})+\mathop{\mathrm{bds}}(G_{t})}\big{)}=O(\mathop{\mathrm{pcr}}(G_{t})+\mathop{\mathrm{bds}}(G_{t}))$. As in the proof of Theorem 1.5, Observation 3.2 yields that the total number of crossings is no more than $O\left(\log n(\mathop{\mathrm{pcr}}(G)+\mathop{\mathrm{bds}}(G))\right)$. ∎

Hliněný and Salazar [12] provided an $O(\Delta^{2})$-approximation algorithm for the crossing number of toroidal graphs. The proof of the correctness of the approximation depends mainly on the two following facts:

First, that $\mathop{\mathrm{cr}}(C_{n}\times C_{n})=\Omega(n^{2})$. While determining the exact value of $\mathop{\mathrm{cr}}(C_{n}\times C_{n})$ is an important open problem, this bound is well known (see [13], for example). It is not hard check that this result holds for the pair crossing number as well.

Secondly, if $H$ is a minor of $G$ and $H$ has maximum degree at most $4$ then $\mathop{\mathrm{cr}}(G)=\Omega(\mathop{\mathrm{cr}}(H))$ ([10],[4]). The proof in [4] extends almost verbatim to show that, under these conditions, $\mathop{\mathrm{pcr}}(G)=\Omega(\mathop{\mathrm{pcr}}(H))$. These observations imply that the algorithm also provides an $O(\Delta^{2})$-approximation for the pair crossing number, and the theorem follows. ∎