Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

In a drawing of a graph G, vertices are represented by points and edges are represented by Jordan curves, in a plane, connecting the corresponding points. We assume that the edges do not pass through vertices, any two edges have finitely many common points, and each of them is either a common endpoint, or a proper crossing. We also assume that no three edges cross at the same point.

The crossing number cr(G) is the minimum number of edge crossings (i.e., crossing points) over all drawings of G. The pair-crossing number pair-cr(G) is the minimum number of crossing pairs of edges over all drawings of G. Clearly, for any graph G, we have

$${\rm PAIR-CR}(G) \leq {\rm CR}(G).$$

It is still an exciting open question whether cr(G) = pair-cr(G) holds for all graphs G.

Pach and Tóth [5] proved that cr(G) cannot be arbitrarily large if pair-cr(G) is bounded; namely, for any G, if pair-cr(G) = k, then cr(G) ≤ 2k 2. Valtr [9] managed to improve this bound to cr(G) ≤ 2k 2 ∕ logk. Based on the ideas of Valtr, the present author [8] improved it to cr \((G) \leq 9{k}^{2}{/\log }^{2}k\).

In this note, using a different approach, we obtain a further improvement.

Theorem.

For any graph G, if pair-cr(G) = k, then cr \((G) = O({k{}^{7/4}\log }^{3/2}k)\).

For the proof, we need some results about string graphs. These are introduced in Sect. 2. In Sect. 3, we give the short proof of the theorem. There are many other versions of the crossing number; for a survey, see [1, 6, 7].

2 String Graphs

A string graph is the intersection graph of continuous arcs in the plane. More precisely, vertices of the graph correspond to continuous curves (strings) in the plane such that two vertices are connected by an edge if and only if the corresponding strings intersect each other.

Suppose that G(V, E) is a graph of n vertices. A separator in a graph G is a subset \(S \subset V\) for which there is a partition \(V = S \cup A \cup B\), | A | , | B | ≤ 2n ∕ 3, and there is no edge between A and B. According to the Lipton–Tarjan separator theorem, [4], every planar graph has a separator of size \(O(\sqrt{n})\). This result has been generalized in several directions, for graphs drawn on a surface of bounded genus, graphs with a forbidden minor, intersection graphs of balls in the d-dimensional space, intersection graphs of Jordan regions, intersection graphs of convex sets in the plane, and, finally, for string graphs [2, 3].

Theorem A ([3]). There is a constant c such that for any string graph G with m edges, there is a separator of size at most \(c{m}^{3/4}\sqrt{\log m}\).

3 Proof of Theorem

Let c be the constant in Theorem A. In a drawing \(\mathcal{D}\) of a graph G in the plane, call those edges that participate in a crossing crossing edges, and those that do not participate in a crossing empty edges.

Lemma.

Suppose that \(\mathcal{D}\) is a drawing of a graph G in the plane with l > 0 crossing edges and k > 0 crossing pairs of edges. Then G can be redrawn such that (i) empty edges are drawn the same way as before, (ii) crossing edges are drawn in the neighborhood of the original crossing edges, and (iii) there are at most \(6c{k{}^{7/4}\log }^{3/2}l\) edge crossings.

Proof of Lemma.

The proof is by induction on l. For l = 1, the statement is trivial. Suppose that the statement has been proved for all pairs (l′, k′), where l′ < l, and consider a drawing of G with k crossing pairs of edges, such that l edges participate in a crossing. Obviously, \(\left({ l \atop 2} \right) \geq k\), and 2k ≥ l; therefore, \(2k \geq l > \sqrt{k}\).

Let V denote the vertex set of G and let E (resp., F) denote the set of empty (resp., crossing) edges of G. We define a string graph H as follows. The vertex set \(\overline{F}\) of H corresponds to the crossing edges of G. Two vertices are connected by an edge if the corresponding edges cross each other. Note that the endpoints do not count; if two edges do not cross, the corresponding vertices are not connected even if the edges have a common endpoint. The graph H is a string graph; it can be represented by the crossing edges of G, as strings, with their endpoints removed. It has l vertices and k edges. By Theorem A, H has a separator of size \(c{k}^{3/4}\sqrt{\log k}\). That is, the vertices can be decomposed into three sets, \({\overline{F}}_{0}\), \({\overline{F}}_{1}\), and \({\overline{F}}_{2}\), such that (1) \(\vert {\overline{F}}_{0}\vert \leq c{k}^{3/4}\sqrt{\log k}\), (2) \(\vert {\overline{F}}_{1}\vert, \vert {\overline{F}}_{2}\vert \leq 2l/3\), (3) there is no edge of H between \({\overline{F}}_{1}\) and \({\overline{F}}_{2}\).

This corresponds to a decomposition of the set of crossing edges F into three sets, F 0, F 1, and F 2, such that (1) \(\vert {F}_{0}\vert \leq c{k}^{3/4}\sqrt{\log k}\), (2) \(\vert {F}_{1}\vert, \vert {F}_{2}\vert \leq 2l/3\), (3) in drawing \(\mathcal{D}\), edges in F 1 and in F 2 do not cross each other.

For i = 0, 1, 2, let \(\vert {F}_{i}\vert = {l}_{i}\). Let \({G}_{1} = G(V,E \cup {F}_{1})\) and \({G}_{2} = G(V,E \cup {F}_{2})\). Then in the drawing \(\mathcal{D}\) of the graph, G i has l i crossing edges. Denote by k i the number of crossing pairs of edges of G i in drawing \(\mathcal{D}\). Then we have \({k}_{1} + {k}_{2} \leq k\), \({l}_{1},{l}_{2} \leq 2l/3\), and \({l}_{1} + {l}_{2} + {l}_{0} = l\).

For i = 1, 2, apply the induction hypothesis for G i and drawing \(\mathcal{D}\). We obtain a drawing \({\mathcal{D}}_{i}\) satisfying the conditions of the lemma: (1) Empty edges drawn the same way as before; (2) crossing edges are drawn in the neighborhood of the original crossing edges; and (3) there are at most \(6c{k}_{i}^{7/4}\log ^{3/2}{l}_{i}\) edge crossings.

Consider the following drawing \({\mathcal{D}}_{3}\) of G. (1) Empty edges are drawn the same way as in \(\mathcal{D}\), \({\mathcal{D}}_{1}\), and \({\mathcal{D}}_{2}\); (2) for i = 1, 2, edges in F i are drawn as in \({\mathcal{D}}_{i}\); (3) edges in F 0 are drawn as in \(\mathcal{D}\). Now count the number of edge crossings (crossing points) in the drawing \({\mathcal{D}}_{3}\). Edges in E are empty, edges in F 1 and in F 2 do not cross each other, and there are at most \(2c{k}_{i}^{7/4}\log ^{3/2}{l}_{i}\) crossings among edges in F i . The only problem is that edges in F 0 might cross edges in \({F}_{1} \cup {F}_{2}\) and each other several times, so we cannot give a reasonable upper bound for the number of crossings of this type. Color edges in F 1 and F 2 blue, and edges in F 0 red. For any piece p of an edge of G, let blue(p) [resp., red(p)] denote the number of crossings on p with blue (resp., red) edges of G. We will apply the following transformations.

ReduceCrossings( e, f) Suppose that two crossing edges, e and f, cross twice, say, in X and Y. Let e′ (resp., f′) be the piece of e (resp., f) between X and Y. If blue(e′) < blue(f′), or blue(e′) = blue(f′) and red(e′) ≤ red(f′), then redraw f′ along e′ from X to Y. Otherwise, redraw e′ along f′ from X to Y. See Fig. 1.

Fig. 1
figure 1figure 1

ReduceCrossings( e, f)

Full size image

Observe that ReduceCrossings might create self-crossing edges, so we need another transformation.

RemoveSelfCrossings( e) Suppose that an edge e crosses itself in X. Then X appears twice on e. Remove the part of e between the first and last appearances of X.

Start with drawing \({\mathcal{D}}_{3}\) of G, and apply ReduceCrossings and RemoveSelfCrossings recursively, as long as there are two crossing edges that cross at least twice, or there is a self-crossing edge.

Let BB, (resp., BR, RR) denote the number of blue–blue (resp., blue–red, red–red) crossings in the current drawing of G. Observe that the triple (BB, BR, RR) lexicographically decreases with each of the transformations. Indeed,

  • if e and f are both blue edges, then ReduceCrossings( e, f) decreases BB,

  • if e is blue and f is red, then either BB decreases, or if it stays the same, then BR decreases,

  • if e and f are both red edges, then BB stays the same, and either BR decreases, or if it also stays the same, then RR decreases,

  • if e is blue, then RemoveSelfCrossings( e) decreases BB,

  • and finally, if e is red, then BB does not change, BR does not increase, and RR decreases.

Therefore, after finitely many steps, we arrive at a drawing \({\mathcal{D}}_{4}\) of G, where any two edges cross at most once, and (BB, BR, RR) is lexicographically not larger than originally. That is, in the drawing \({\mathcal{D}}_{4}\), \(BB \leq 2c{k}_{1}^{7/4}\log {l}_{1} + 2c{k}_{2}^{7/4}\log {l}_{2}\), and any two edges cross at most once; therefore, \(BR + RR \leq {l}_{0}l\). So, for the total number of crossings, we have

$$\begin{array}{rcl} & & 6c{k}_{1}^{7/4}\log ^{3/2}{l}_{ 1} + 6c{k}_{2}^{7/4}\log ^{3/2}{l}_{ 2} + {l}_{0}l \\ & & \quad \leq 6c{k}_{1}^{7/4}\sqrt{\log l}\log (2l/3) + 6c{k}_{ 2}^{7/4}\sqrt{\log l}\log (2l/3) + {l}_{ 0}l \\ & & \quad \leq 6c({k}_{1}^{7/4} + {k}_{ 2}^{7/4})\sqrt{\log l}(\log l +\log (2/3)) + {l}_{ 0}l \\ & & \quad \leq 6c{k{}^{7/4}\log }^{3/2}l - 3c{k}^{7/4}\sqrt{\log l} + {l}_{ 0}l \\ & & \quad \leq 6c{k{}^{7/4}\log }^{3/2}l - 3c{k}^{7/4}\sqrt{\log l} + cl{k}^{3/4}\sqrt{\log k} \\ & & \quad \leq 6c{k{}^{7/4}\log }^{3/2}l - 3c{k}^{7/4}\sqrt{\log l} + 2c{k}^{7/4}\sqrt{\log k} \\ & & \quad \leq 6c{k{}^{7/4}\log }^{3/2}l - 3c{k}^{7/4}\sqrt{\log l} + 3c{k}^{7/4}\sqrt{\log l} \\ & & \quad = 6c{k{}^{7/4}\log }^{3/2}l.\end{array}$$

 □ 

Now consider a graph G and let pair-cr(G) = k. Take a drawing of G with exactly k crossing pairs of edges. Let l be the total number of crossing edges. By the lemma, G can be redrawn with at most \(6c{k{}^{7/4}\log }^{3/2}l\) crossings. Since 2k ≥ l, cr \((G) \leq 6c{k{}^{7/4}\log }^{3/2}l < 18c{k{}^{7/4}\log }^{3/2}k\). This concludes the proof of the theorem. □