# «Abstract The crossing number of a graph G is the minimum num- ber of crossings in a drawing of G. We introduce several variants of this deﬁnition, ...»

Thirteen Problems on

Crossing Numbers

J´nos Pach∗

a

Courant Institute, NYU

and Hungarian Academy of Sciences

G´za T´th†

e o

Massachusetts Institute of Technology

and Hungarian Academy of Sciences

Abstract

The crossing number of a graph G is the minimum num-

ber of crossings in a drawing of G. We introduce several

variants of this deﬁnition, and present a list of related open

problems. The ﬁrst item is Zarankiewicz’s classical conjec-

ture about crossing numbers of complete bipartite graphs, the last ones are new and less carefully tested. In Section 5, we state some conjectures about the expected values of var- ious crossing numbers of random graphs, and prove a large deviation result.

1 Introduction Let G be a graph, whose vertex set and edge set are denoted by V (G) and E(G), respectively. A drawing of G is a representation of ∗ Supported by NSF grant CR-97-32101, PSC-CUNY Research Award 667339 and OTKA-T-020914.

† Supported by NSF grant DMS-99-70071, OTKA-T-020914 and OTKA-F- 22234.

1 G in the plane such that its vertices are represented by distinct points and its edges by simple continuous arcs connecting the corresponding point pairs. For simplicity, we assume that in a drawing (a) no edge passes through any vertex other than its endpoints, (b) no two edges touch each other (i.e., if two edges have a common interior point, then at this point they properly cross each other), and (c) no three edges cross at the same point.

Tur´n [23] deﬁned the crossing number of G, cr(G), as the small- a est number of edge crossings in any drawing of G. Clearly, cr(G) = 0 if and only if G is planar.

** Problem 1. (Zarankiewicz’s Conjecture [11]) The crossing number of the complete bipartite graph Kn,m with n and m vertices in its classes satisﬁes m m−1 n n−1 cr(Kn,m ) = · · ·.**

2 2 2 2 Kleitman [13] veriﬁed this conjecture in the special case when min{m, n} ≤ 6 and Woodall [25] for m = 7, n ≤ 10.

** Problem 2. Is it true that the crossing number of the complete graph Kn satisﬁes 1n n−1 n−2 n−3 cr(Kn ) = · · ·.**

42 2 2 2 Of course, the best known upper bounds for both cr(Kn,m ) and cr(Kn ) are the conjectured values in Problems 1 and 2, respectively.

The best known lower bounds, cr(Km,n )≥ n2 m2 (1/20 − o(1)) and cr(Kn ) ≥ n4 (1/80 − o(1)), can be deduced from Kleitman’s result by an easy counting argument.

Garey and Johnson [10] proved that the determination of the crossing number is an NP-complete problem. In the past twenty years, it turned out that crossing numbers play an important role in various ﬁelds of discrete and computational geometry, and they can also be used, e.g.,to obtain lower bounds on the chip area required for the VLSI circuit layout of a graph [14].

4 exists and is positive.

M. Simonovits suggested that the lower bound (1) for crossing numbers may be substantially improved, if we restrict our attention to some special classes of graphs, e.g., to graphs not containing some ﬁxed, so-called forbidden subgraph. Indeed, this turned out to be true.

A graph property P is said to be monotone if (i) for any graph G satisfying P, every subgraph of G also satisﬁes P; and (ii) if G1 and G2 satisfy P, then their disjoint union also satisﬁes P.

For any monotone property P, let ex(n, P) denote the maximum number of edges that a graph of n vertices can have if it satisﬁes P.

In the special case when P is the property that the graph does not contain a subgraph isomorphic to a ﬁxed forbidden subgraph H, we write ex(n, H) for ex(n, P).

Let P be a monotone graph property with ex(n, P) = O(n1+α ) for some α 0. In [19], we proved that there exist two constants c, c 0 such that the crossing number of any graph G with property P, which has n vertices and e ≥ cn log2 n edges, satisﬁes e2+1/α cr(G) ≥ c. (4) n1+1/α This bound is asymptotically tight, up to a constant factor.

In some interesting special cases when we know the precise order of magnitude of the function ex(n, P), we obtained a slightly stronger result: we proved that (4) is valid for every e ≥ 4n. For instance, if P is the property that G does not contain C4, a cycle of length 4, as a subgraph, then ex(n, P) = ex(n, C4 ) = O(n3/2 ), and we know that the crossing number of any graph with n vertices and e ≥ 4n edges, which satisﬁes this property, is at least constant times e4 /n3. This bound is asymptotically tight.

If the answer to the following question were in the aﬃrmative, we could extend this stronger result to many further graph properties P.

** Problem 7. Let G be a bipartite graph, and let G be a graph that can be obtained from G by identifying two vertices whose distance is at least three.**

Is it true that ex(n, G) = O (ex(n, G ))?

5 4 Three Other Crossing Numbers We deﬁne three variants of the notion of crossing number.

(1) The rectilinear crossing number, lin-cr(G), of a graph G is the minimum number of crossings in a drawing of G, in which every edge is represented by a straight-line segment.

(2) The pairwise crossing number of G, pair-cr(G), is the minimum number of crossing pairs of edges over all drawings of G. (Here the edges can be represented by arbitrary continuous curves, so that two edges may cross more than once, but every pair of edges can contribute at most one to pair-cr(G).) (3) The odd-crossing number of G, odd-cr(G), is the minimum number of those pairs of edges which cross an odd number of times, over all drawings of G.

It readily follows from the deﬁnitions that odd-cr(G) ≤ pair-cr(G) ≤ cr(G) ≤ lin-cr(G).

Bienstock and Dean [6] exhibited a series of graphs with crossing number 4, whose rectilinear crossing numbers are arbitrary large.

The following is perhaps the most exciting unsolved problem in the area.

Problem 8. Is it true that

** odd-cr(G) = pair-cr(G) = cr(G),**

for every graph G?

According to a remarkable theorem of Hanani (alias Chojnacki) [7] and Tutte [24], if a graph G can be drawn in the plane so that any pair of its edges cross an even number of times, then it can also be drawn without any crossing. In other words, odd-cr(G) = 0 implies that cr(G) = 0. Note that in this case, by a theorem of F´ry [9], we also have that lin-cr(G) = 0.

a 6 The main diﬃculty in this problem is that a graph has so many essentially diﬀerent drawings that the computation of any of the above crossing numbers, for a graph of only 15 vertices, appears to be a hopelessly diﬃcult task even for a very fast computer [22].

As we mentioned at the end of the Introduction, Garey and Johnson [10] showed that the determination of the crossing number is an NP-complete problem. Analogous results hold for the rectilinear crossing number [5] and for the odd-crossing number [21]. However, for the pairwise crossing number, we could prove only that it is NP-hard.

Problem 9. Given a graph G of n vertices and an integer K, can one check in polynomial time that pair-cr(G) ≤ K? In other words, is the problem of ﬁnding the pairwise crossing number of a graph in NP?

Concerning Problem 8, all we can show is that the parameters cr(G), pair-cr(G), and odd-cr(G), are not completely unrelated.

More precisely, we proved in [21] that cr(G) ≤ 2(odd-cr(G))2, for every graph G. The next step would be to answer the following question.

Problem 10. Does there exist a constant C such that cr(G) ≤ C · odd-cr(G) holds for every graph G?

Although we are far from knowing the expectations of crossing numbers of random graphs, it is not hard to argue that the crossing numbers are sharply concentrated in very short intervals around these values.

To show this, we need a simple observation.

Lemma. Let G be a graph with edge set E = E(G), and let G be another graph obtained from G by adding an edge. Then

Proof: Parts (ii) and (iii) are obviously true, because we can arbitrarily add to any optimal drawing of G an arc representing the new edge.

To prove part (i), ﬁx a drawing of G, which minimizes the number of crossings. It is easy to see that in such a drawing any two edges have at most one point in common [22]. Add a continuous arc a representing the new edge so as to minimize the number of crossings in the resulting drawing of G.

In this new drawing, a cannot have two points, p and q, in common with any arc b representing an edge of E = E(G). Otherwise, we could replace the piece of a between p and q by an arc running very close to the piece of b between p and q. By the minimality of the initial drawing of G, this replacement would strictly decrease the number of crossings, because at least one crossing between a and b would be eliminated. This would contradict the minimality of the drawing of G. 2 Theorem. Let G(n, p) be a random graph with n vertices, with edge probability 0 p = p(n) 1, and let e = p n. Then 2

6 Even More Crossing Numbers

**We can further modify each of the above crossing numbers, by applying one of the following rules:**

Rule + : Consider only those drawings where two edges with a common endpoint do not cross each other.

Rule 0 : Two edges with a common endpoint are allowed to cross and their crossing counts.

Rule − : Two edges with a common endpoint are allowed to cross, but their crossing does not count.

10 In the previous deﬁnitions we have always used Rule 0. If we apply Rule + (Rule −) in the deﬁnition of the crossing numbers, then we indicate it by using the corresponding subscript, as shown in the table below. This gives us an array of nine diﬀerent crossing numbers. It is easy to see that in a drawing of a graph, which minimizes the number of crossing points, any two edges have at most one point in common (see e.g. [22]). Therefore, cr+ (G) = cr(G), which slightly simpliﬁes the picture.

[12] R. K. Guy: Crossing numbers of graphs, in: Graph theory and applications (Proc. Conf. Western Michigan Univ., Kalamazoo, Mich., 1972) Lecture Notes in Mathematics 303, Springer, Berlin, 111-124.

[13] D. J. Kleitman: The crossing number of K5,n, Journal of Combinatorial Theory 9 (1970), 315–323.

[14] T. Leighton: Complexity Issues in VLSI, Foundations of Computing Series, MIT Press, Cambridge, MA, 1983.

[15] F. T. Leighton: New lower bound techniques for VLSI, Math.

Systems Theory 17 (1984), 47–70.

[16] R. Lipton and R. Tarjan: A separator theorem for planar graphs, SIAM J. Applied Mathematics 36 (1979), 177–189.

[17] J. Pach and P.K. Agarwal: Combinatorial Geometry, J. Wiley and Sons, New York, 1995.

[18] J. Pach, F. Shahrokhi, and M. Szegedy: Applications of the crossing number, Algorithmica 16 (1996), 111–117.

[21] J. Pach and G. T´th: Which crossing number is it, anyway?, o in: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, IEEE Press, 1998, 617-626. Also in: Journal of Combinatorial Theory, Ser. B.

13 [22] R. B. Richter and C. Thomassen: Relations between crossing numbers of complete and complete bipartite graphs, American Mathematical Monthly, February 1997, 131–137.

[24] W. T. Tutte: Toward a theory of crossing numbers, Journal of Combinatorial Theory 8 (1970), 45–53.

[25] D. R. Woodall: Cyclic-order graphs and Zarankiewicz’s crossing-number conjecture, Journal of Graph Theory 17 (1993), 657–671.

14