Crossing number (graph theory)

A drawing of the Heawood graph with three crossings. This is the minimum number of crossings among all drawings of this graph, so the graph has crossing number cr(G) = 3.

In graph theory, the crossing number cr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero.

The mathematical origin of the study of crossing numbers is in Turán's brick factory problem, in which Pál Turán asked to determine the crossing number of the complete bipartite graph K_m,n,^[1] and independently in sociology at approximately the same time, in connection with the construction of sociograms.^[2] It continues to be of great importance in graph drawing. As well as complete bipartite graphs, another class of graphs for which a formula for the number of crossings has been conjectured, but not proven, are the complete graphs.

The crossing number inequality states that, for graphs where the number e of edges is sufficiently larger than the number n of vertices, the crossing number is at least proportional to e³/n². It has applications in VLSI design and incidence geometry.

Without further qualification, the crossing number allows drawings in which the edges may be represented by arbitrary curves; the rectilinear crossing number requires all edges to be straight line segments, and may differ from the crossing number. In particular, the rectilinear crossing number of a complete graph is essentially the same as the minimum number of convex quadrilaterals determined by a set of n points in general position, closely related to the Happy Ending problem.^[3]

Definitions

For the purposes of defining the crossing number, a drawing of an undirected graph is a mapping from the vertices of the graph to disjoint points in the plane, and from the edges of the graph to curves connecting their two endpoints. No vertex should be mapped onto an edge that it is not an endpoint of, and whenever two edges have curves that intersect (other than at a shared endpoint) their intersections should form a finite set of proper crossings, where the two curves are transverse. A crossing is counted separately for each of these crossing points, for each pair of edges that cross. The crossing number of a graph is then the minimum, over all such drawings, of the number of crossings in a drawing.^[4]

Some authors add more constraints to the definition of a drawing, for instance that each pair of edges have at most one intersection point (a shared endpoint or crossing). For the crossing number as defined above, these constraints make no difference, because a crossing-minimal drawing cannot have edges with multiple intersection points. If two edges with a shared endpoint cross, the drawing can be changed locally at the crossing point, leaving the rest of the drawing unchanged, to produce a different drawing with one fewer crossing. And similarly, if two edges cross two or more times, the drawing can be changed locally at two crossing points to make a different drawing with two fewer crossings. However, these constraints are relevant for variant definitions of the crossing number that, for instance, count only the numbers of pairs of edges that cross rather than the number of crossings.^[4]

Special cases

Complete bipartite graphs

During World War II, Hungarian mathematician Pál Turán was forced to work in a brick factory, pushing wagon loads of bricks from kilns to storage sites. The factory had tracks from each kiln to each storage site, and the wagons were harder to push at the points where tracks crossed each other, from which Turán was led to ask his brick factory problem: what is the minimum possible number of crossings in a drawing of a complete bipartite graph?^[5]

Zarankiewicz attempted to solve Turán's brick factory problem;^[6] his proof contained an error, but he established a valid upper bound of

${\textrm {cr}}(K_{m,n})\leq \left\lfloor {\frac {n}{2}}\right\rfloor \left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {m}{2}}\right\rfloor \left\lfloor {\frac {m-1}{2}}\right\rfloor$

for the crossing number of the complete bipartite graph K_m,n. This bound has been conjectured to be the optimal number of crossings for all complete bipartite graphs.

Complete graphs and graph coloring

The problem of determining the crossing number of the complete graph was first posed by Anthony Hill, and appeared in print in 1960.^[7] Hill and his collaborator John Ernest were two constructionist artists fascinated by mathematics, who not only formulated this problem but also originated a conjectural formula for this crossing number, which Richard K. Guy published in 1960.^[7] Namely, it is known that there always exists a drawing with

${\displaystyle {\textrm {cr}}(K_{p})\leq {\frac {1}{4}}\left\lfloor {\frac {p}{2}}\right\rfloor \left\lfloor {\frac {p-1}{2}}\right\rfloor \left\lfloor {\frac {p-2}{2}}\right\rfloor \left\lfloor {\frac {p-3}{2}}\right\rfloor }$

crossings. This formula gives values of 1, 3, 9, 18, 36, 60, 100, 150 for p = 5, ..., 12; see sequence A000241 in the On-line Encyclopedia of Integer Sequences. The conjecture is that there can be no better drawing, so that this formula gives the optimal number of crossings for the complete graphs. An independent formulation of the same conjecture was made by Thomas L. Saaty in 1964.^[8]

Saaty further verified that this formula gives the optimal number of crossings for p ≤ 10 and Pan and Richter showed that it also is optimal for p = 11, 12.^[9]

The Albertson conjecture, formulated by Michael O. Albertson in 2007, states that, among all graphs with chromatic number n, the complete graph K_n has the minimum number of crossings. That is, if the Guy-Saaty conjecture on the crossing number of the complete graph is valid, every n-chromatic graph has crossing number at least equal to the formula in the conjecture. It is now known to hold for n ≤ 16.^[10]

Cubic graphs

The smallest cubic graphs with crossing numbers 1–8 are known (sequence A110507 in the OEIS). The smallest 1-crossing cubic graph is the complete bipartite graph K_3,3, with 6 vertices. The smallest 2-crossing cubic graph is the Petersen graph, with 10 vertices. The smallest 3-crossing cubic graph is the Heawood graph, with 14 vertices. The smallest 4-crossing cubic graph is the Möbius-Kantor graph, with 16 vertices. The smallest 5-crossing cubic graph is the Pappus graph, with 18 vertices. The smallest 6-crossing cubic graph is the Desargues graph, with 20 vertices. None of the four 7-crossing cubic graphs, with 22 vertices, are well known.^[11] The smallest 8-crossing cubic graphs include the Nauru graph and the McGee graph or (3,7)-cage graph, with 24 vertices.

In 2009, Exoo conjectured that the smallest cubic graph with crossing number 11 is the Coxeter graph, the smallest cubic graph with crossing number 13 is the Tutte–Coxeter graph and the smallest cubic graph with crossing number 170 is the Tutte 12-cage.^[12][13]

Known crossing numbers

As of April 2015, crossing numbers are known for very few graph families. In particular, except for a few initial cases, the crossing number of complete graphs, bipartite complete graphs, and products of cycles all remain unknown. There has been some progress on lower bounds, as reported by de Klerk et al. (2006).^[14] An extensive survey on the various crossing-number variants, including references to recently recognized subtleties in the definition, is available. ^[15]

Complexity

In general, determining the crossing number of a graph is hard; Garey and Johnson showed in 1983 that it is an NP-hard problem.^[16] In fact the problem remains NP-hard even when restricted to cubic graphs^[17] and to near-planar graphs^[18] (graphs that become planar after removal of a single edge). More specifically, determining the rectilinear crossing number is complete for the existential theory of the reals.^[19]

On the positive side, there are efficient algorithms for determining if the crossing number is less than a fixed constant k. In other words, the problem is fixed-parameter tractable.^[20][21] It remains difficult for larger k, such as k = |V|/2. There are also efficient approximation algorithms for approximating cr(G) on graphs of bounded degree.^[22] In practice heuristic algorithms are used, such as the simple algorithm which starts with no edges and continually adds each new edge in a way that produces the fewest additional crossings possible. These algorithms are used in the Rectilinear Crossing Number distributed computing project.^[23]

The crossing number inequality

For an undirected simple graph G with n vertices and e edges such that e > 7n the crossing number is always at least

$\operatorname {cr} (G)\geq {\frac {e^{3}}{29n^{2}}}.$

This relation between edges, vertices, and the crossing number was discovered independently by Ajtai, Chvátal, Newborn, and Szemerédi,^[24] and by Leighton.^[25] It is known as the crossing number inequality or crossing lemma.

The constant 29 is the best known to date, and is due to Ackerman,^[26] The constant 7 can be lowered to 4, but at the expense of replacing 29 with the worse constant of 64.

The motivation of Leighton in studying crossing numbers was for applications to VLSI design in theoretical computer science. Later, Székely^[27] also realized that this inequality yielded very simple proofs of some important theorems in incidence geometry, such as Beck's theorem and the Szemerédi-Trotter theorem, and Tamal Dey used it to prove upper bounds on geometric k-sets.^[28]

Variations

If edges are required to be drawn as straight line segments, rather than arbitrary curves, then some graphs need more crossings. The rectilinear crossing number is defined to be the minimum number of crossings of a drawing of this type. It is always at least as large as the crossing number, and is larger for some graphs. The rectilinear crossing numbers for K₅ through K₁₂ are 1, 3, 9, 19, 36, 62, 102, 153, (A014540) and values up to K₂₇ are known, with K₂₈ requiring either 7233 or 7234 crossings. Further values are collected by the Rectilinear Crossing Number project.^[29]

A graph has local crossing number k if it can be drawn with at most k crossings per edge, but not fewer. The graphs that can be drawn with at most k crossings per edge are also called k-planar.^[30]

Other variants of the crossing number include the pairwise crossing number (the minimum number of pairs of edges that cross in any drawing) and the odd crossing number (the number of pairs of edges that cross an odd number of times in any drawing). The odd crossing number is at most equal to the pairwise crossing number, which is at most equal to the crossing number. However, by the Hanani–Tutte theorem, whenever one of these numbers is zero, they all are.^[4]

See also

• Planarization, a planar graph formed by replacing each crossing by a new vertex

References

1. Turán, P. (1977). "A Note of Welcome". Journal of Graph Theory. 1: 7–9. doi:10.1002/jgt.3190010105.
2. Bronfenbrenner, Urie (1944). "The graphic presentation of sociometric data". Sociometry. 7 (3): 283–289. JSTOR 2785096. The arrangement of subjects on the diagram, while haphazard in part, is determined largely by trial and error with the aim of minimizing the number of intersecting lines.
3. Scheinerman, Edward R.; Wilf, Herbert S. (1994). "The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability". American Mathematical Monthly. 101 (10): 939–943. doi:10.2307/2975158. JSTOR 2975158.
4. Pach, J.; Toth, G. (1998). "Which crossing number is it, anyway?". Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998). pp. 617–626. doi:10.1109/SFCS.1998.743512..
5. Pach, János; Sharir, Micha (2009). "5.1 Crossings—the Brick Factory Problem". Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures. Mathematical Surveys and Monographs. 152. American Mathematical Society. pp. 126–127.
6. Zarankiewicz, K. (1954). "On a Problem of P. Turán Concerning Graphs". Fundamenta Mathematicae. 41: 137–145.
7. Guy, R.K. (1960). "A combinatorial problem". Nabla (Bulletin of the Malayan Mathematical Society). 7: 68–72.
8. Saaty, T.L. (1964). "The minimum number of intersections in complete graphs". Proceedings of the National Academy of Sciences of the United States of America. 52: 688–690. doi:10.1073/pnas.52.3.688.
9. Pan, Shengjun; Richter, R. Bruce (2007). "The crossing number of K₁₁ is 100". Journal of Graph Theory. 56 (2): 128–134. doi:10.1002/jgt.20249. MR 2350621..
10. Barát, János; Tóth, Géza (2009). "Towards the Albertson Conjecture". arXiv:0909.0413 [math.CO].
11. Weisstein, Eric W. "Graph Crossing Number". MathWorld.
12. Exoo, G. "Rectilinear Drawings of Famous Graphs".
13. Pegg, E. T.; Exoo, G. (2009). "Crossing Number Graphs". Mathematica Journal. 11.
14. de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, B.; Salazar, G. (2006). "Improved bounds for the crossing numbers of K_m,n and K_n". SIAM Journal on Discrete Mathematics. 20 (1): 189–202. doi:10.1137/S0895480104442741.
15. Schaefer, Marcus (2014). "The graph crossing number and its variants: a survey". The Electronic Journal of Combinatorics: #DS21.
16. Garey, M. R.; Johnson, D. S. (1983). "Crossing number is NP-complete". SIAM Journal on Algebraic Discrete Methods. 4 (3): 312–316. doi:10.1137/0604033. MR 0711340.
17. Hliněný, P. (2006). "Crossing number is hard for cubic graphs". Journal of Combinatorial Theory. Series B. 96 (4): 455–471. doi:10.1016/j.jctb.2005.09.009. MR 2232384.
18. Cabello S. and Mohar B. (2013). "Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard". SIAM Journal on Computing. 42 (5): 1803–1829. doi:10.1137/120872310.
19. Schaefer, Marcus (2010). Complexity of some geometric and topological problems (PDF). Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers. Lecture Notes in Computer Science. 5849. Springer-Verlag. pp. 334–344. doi:10.1007/978-3-642-11805-0_32. ISBN 978-3-642-11804-3..
20. Grohe, M. (2005). "Computing crossing numbers in quadratic time". Journal of Computer and System Sciences. 68 (2): 285–302. doi:10.1016/j.jcss.2003.07.008. MR 2059096.
21. Kawarabayashi, Ken-ichi; Reed, Bruce (2007). Computing crossing number in linear time. Proceedings of the 29th Annual ACM Symposium on Theory of Computing. pp. 382–390. doi:10.1145/1250790.1250848. ISBN 978-1-59593-631-8.
22. Even, Guy; Guha, Sudipto; Schieber, Baruch (2003). "Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas". SIAM Journal on Computing. 32 (1): 231–252. doi:10.1137/S0097539700373520.
23. Rectilinear Crossing Number on the Institute for Software Technology at Graz, University of Technology (2009).
24. Ajtai, M.; Chvátal, V.; Newborn, M.; Szemerédi, E. (1982). Crossing-free subgraphs. Theory and Practice of Combinatorics. North-Holland Mathematics Studies. 60. pp. 9–12. MR 0806962.
25. Leighton, T. (1983). Complexity Issues in VLSI. Foundations of Computing Series. Cambridge, MA: MIT Press.
26. Ackerman, Eyal (2013). "On topological graphs with at most four crossings per edge" (PDF).
27. Székely, L. A. (1997). "Crossing numbers and hard Erdős problems in discrete geometry". Combinatorics, Probability and Computing. 6 (3): 353–358. doi:10.1017/S0963548397002976. MR 1464571.
28. Dey, T. L. (1998). "Improved bounds for planar k-sets and related problems". Discrete and Computational Geometry. 19 (3): 373–382. doi:10.1007/PL00009354. MR 1608878.
29. Oswin Aichholzer. "Rectilinear Crossing Number project".
30. Ringel, Gerhard (1965). "Ein Sechsfarbenproblem auf der Kugel". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (in German). 29: 107–117. doi:10.1007/BF02996313. MR 0187232.