Crossing Numbers: Theory and Applications (18w5029)

Arriving in Banff, Alberta Sunday, October 21 and departing Friday October 26, 2018


(Universidad Autónoma de San Luis Potosí)

(University of South Carolina)

Bojan Mohar (Simon Fraser University)


General objectives.

    \item{\em Interaction of researchers with a variety of backgrounds and interests}

    The community of researchers working on crossing numbers has grown and broadened greatly in the last few years. We have recently witnessed a flurry of activity both in the parametric, structural, and algorithmical aspects of the theory. We have seen a series of successful applications of geometric techniques to the topological setting; we have gained a lot of insight from tackling structural problems with an eye of obtaining improved approximation algorithms; and we have also continued to see the fruitful application of techniques from other branches of mathematics (such as semidefinite programming and flag algebras) to crossing numbers. One of the foremost objectives of this workshop is to bring together all the researchers that have played a major role in this impressive run, so that we can enrich our understanding and horizons learning from each other's experience and background.

    \itemExposing younger researchers to the breadth of this thriving field

    The area of crossing numbers has quickly established itself as an important, mainstream part of Topological Graph Theory. Most of the cornerstone results in the field have been proved in the last couple of decades. This remarkable progress has involved researchers from many parts of mathematics and computer science, from people coming from the Graph Minors tradition of Structural Graph Theory, to computer scientists with an interest in the explicit implementation of graph drawing and visualization algorithms.

    Since this discipline brings together people from such diverse backgrounds and interests, most younger researchers and graduate students interested in the field almost never have the opportunity to interact with all the protagonists in the field in the same event. Several meetings on the general field of Topological Graph Theory take place each year; the same is true about Discrete Geometry or (the much broader field of) Algorithms. A central objective of this workshop is to expose junior researchers to the many facets of crossing numbers, as seen and told by their most active players.

    \itemSetting an agenda

    Bringing together researchers from the variety of areas that nurture the field of crossing numbers is not only an ideal environment for proving new results; it is also a great opportunity to come up with new questions, and to redefine the main goals and paradigms of the area. This branch of Topological Graph Theory has benefited enormously from the interaction of graph theorists, computer scientists, and people with background and interests in mathematical programming, extremal combinatorics, and discrete geometry, among others. An intensive, weeklong interaction promises to be a very fruitful ground to set an ambitious agenda for the area for years to come.

Relevance, importance, and timeliness.

We have been witnessing in the last few years the coming of age of Crossing Numbers as a mainstream part of Topological Graph Theory. Some important conjectures and questions have been settled~[2page,m1,m2}; important applications to other branches of mathematics have been unveiled~\cite{ap,ap2,tao}; and different perspectives have been applied to old problems that have allowed to apply techniques and results from areas such as mathematical programming~\cite{dekp,dps1,dps2}, extremal combinatorics~\cite{norinstalksiam}, and discrete geometry~\cite{cyl,kyncl].

We seem to face a unique opportunity to bring together both the major veterans in the field, as well as the new, younger protagonists that have developed an interest in the area unveiling the close relationship of crossing numbers to other parts of mathematics. Several problems that have given a direction to this field have been successfully tackled, and the time seems ripe to get together and set a fresh agenda for years to come.

% *************************************************************************** % ****************************** BIBLIOGRAPHY ****************************** % ***************************************************************************



  1. [2page] B.M.~\'Abrego, O.~Aichholzer, S.~Fern\'andez-Merchant, P.~Ramos, and G.~Salazar, The 2-page crossing number of $K_n$. Discrete and Computational Geometry 49 (2013), 747--777.

  2. [cyl] B.M.~\'Abrego, O.~Aichholzer, S.~Fern\'andez-Merchant, P.~Ramos, and G.~Salazar, Shellable drawings and the cylindrical crossing number of $K_n$. Discrete and Computational Geometry, to appear.

  3. [crolem] M.~Ajtai, V.~Chv\'atal, M.~Newborn, E.~Szemer\'edi, Crossing-free subgraphs. Theory and Practice of Combinatorics. North-Holland Mathematics Studies 60. pp.~9--12.

  4. [kyncl] M.~Balko, R.~Fulek, and J.~Kyn\v{c}l, Crossing numbers and combinatorial characterization of monotone drawings of $K_n$. arXiv}:1312.3679 {\tt [math.CO].

  5. [factory] L.~Beineke and R.~Wilson, The early history of the brick factory problem. Math. Intelligencer 32 (2010), 41--48.

  6. [DCG] D.~Bokal, \'E.~Czabarka, L.A.~Sz\'ekely, and I.~Vrt'o, General lower bounds for the minor crossing numbers of graphs. Discrete and Computational Geometry 44 (2010), 463--483.

  7. [minormohar] D.~Bokal, G.~Fijav\v{z}, B.~Mohar, The minor crossing number. SIAM J.~Discrete Math.~ 20 (2006), 344--356.

  8. [bors] D.~Bokal, B.~Oporowski, R.B.~Richter, and G.~Salazar, Characterizing $2$-crossing-critical graphs. arXiv}:1312.3712 {\tt{[math.CO]}.

  9. [stretch2] S.~Cabello, M.~Chimani, and P.~Hlin\v{e}n\'y, Computing the stretch of an embedded graph. SIAM J. Discrete Math. 28 (2014), 1391--1401.

  10. [cabellomohar] S.~Cabello and B.~Mohar, Crossing number and weighted crossing number of near-planar graphs. Algorithmica 60 (2011), 484--504.

  11. [ckt] J.~\v{C}ern\'y, J.~Kyn\v{c}l, and G.~T\'oth, Improvement on the decay of crossing numbers. Graphs and Combinatorics 29 (2013), 365--371.

  12. [apex] M.~Chimani, P.~Hlin\v{e}n\'y, and P.~Mutzel, Vertex insertion approximates the crossing number of apex graphs. European J. Combin. 33 (2012), 326--335.

  13. [dk1] E.~de Klerk, J.~Maharry, D.V.~Pasechnik, R.B.~Richter, and G.~Salazar, Improved bounds for the crossing numbers of $K_{m,n}$ and $K_n$. SIAM J. Discrete Math. 20 (2006), 189--202.

  14. [dk2] E.~de Klerk, D.V.~Pasechnik, and A.~Schrijver, Reduction of symmetric semidefinite programs using the regular $\ast$-representation. Math. Program. Ser. B 109 (2007), 613--624.

  15. [dekp] E.~de Klerk and D.V.~Pasechnik, Improved lower bounds for the $2$-page crossing numbers of $K_{m,n}$ and $K_n$ via semidefinite programming. SIAM J. Optim. 22 (2012), 581--595.

  16. [dps1] E.~de Klerk, D.V.~Pasechnik, and G.~Salazar, Improved lower bounds on book crossing numbers of complete graphs. SIAM J. Discrete Math. 27 (2013), 619--633.

  17. [dps2} E.~de Klerk, D.V.~Pasechnik, and G.~Salazar, Book drawings of complete bipartite graphs. Discrete Appl. Math. 167 (2014), 80--93. \bibitem{m1] M.~DeVos, B.~Mohar, and R.~\v{S}\'amal, Unexpected behaviour of crossing sequences. J. Combin. Theory Ser. B 101 (2011), 448--463.

  18. [dey] T.~Dey, Improved bounds for planar $k$-sets and related problems, Discrete Comput.~Geom. 19 (1998), 373--382.

  19. [m2] Z.~Dvo\v{r}\'ak and B.~Mohar, Crossing-critical graphs with large maximum degree. J. Combin. Theory Ser. B 100 (2010), 413--417.

  20. [elekes] G.~Elekes, M.B.~Nathanson, I.~Z.~Ruzsa, Convexity and sumsets. J. Number Theory 83 (2) (2000), 194--201.

  21. [even} G.~Even, S.~Guha, and B.~Schieber, Improved approximations of crossings in graph drawings and VLSI layout areas, in: {\it Proc. 32nd Annual Symposium on Theory of Computing, STOC'00] (ACM Press, 2000) 296--305.

  22. [ncube] L.~Faria, C.M.H.~de Figueiredo, O.~S\'ykora, and I.~Vrt'o, An improved upper bound on the crossing number of the hypercube. J.~Graph Theory 59 (2008), 145--161.

  23. [foxtoth] J.~Fox and C.D.~T\'oth, On the decay of crossing numbers. J.~Combin.~Theory Ser.~B 98 (2008), 33--42.

  24. [garcia] E.~Garcia-Moreno, and G.~Salazar, Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree. J.~Graph Theory 36 (2001), 168--173.

  25. [gj] M.R.~Garey and D.S.~Johnson, Crossing number is NP-complete. SIAM J. Alg. Discrete Methods 4 (1983) 312--316.

  26. [proj] I.~Gitler, P.~Hlin\v{e}n\'y, J.~Lea\~nos, and G.~Salazar, The crossing number of a projective graph is quadratic in the face-width. Electronic Journal of Combinatorics 15 (2008), Research paper 46, 8 pp.

  27. [glebskysalazar] L.Y.~Glebsky, G.~Salazar, The crossing number of $C\sb m\times C\sb n$ is as conjectured for $n\geq m(m+1)$. J.~Graph Theory 47 (2004), 53--72.

  28. [guyy] R.K.~Guy, The decline and fall of Zarankiewicz's Theorem. In Proof Techniques in Graph Theory, Proceedings of the Second Ann Arbor Graph Theory Conference, Ann Arbor, Michigan, 1968. New York: Academic Press, 63--69, (1969).

  29. [hararyhill] F.~Harary and A.~Hill, On the number of crossings in a complete graph. Proc. Edinburgh Math. Soc. (2) 13 (1962/1963), 333-338.

  30. [cubic] P.~Hlin\'en\'y, Crossing number is hard for cubic graphs. J.~Combin.~Theory Ser.~B 96, no.~4 (2006), 455--471.

  31. [ch] P.~Hlin\v{e}n\'y and M.~Chimani, Approximating the crossing number of graphs embeddable in any orientable surface. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 918--927, SIAM, Philadelphia, PA, 2010.

  32. [bode] P.~Hlin\v{e}n\'y and G.~Salazar, On the crossing number of almost planar graphs. Lecture Notes in Computer Science 4372 (2007), 162--173.

  33. [ap] M.~Iliopoulou, Counting joints with multiplicities. Proc. Lond. Math. Soc. (3) 106 (2013), 675--702.

  34. [iosevich] A.~Iosevich, S.~Konyagin, M.~Rudnev, and V.~Ten, Combinatorial complexity of convex sequences. Disc.~Comput.~Geom 35 (2006), 143--158.

  35. [kleitman] D.J.~Kleitman, The crossing number of $K_{5,n}$. J.~Combin.~Th. 9, 315--323 (1970).

  36. [le] F. T. Leighton, Complexity Issues in VLSI. MIT Press, Cambridge, 1983.

  37. [lr] F.~T.~Leighton, S.~Rao, Multicommodity max--flow min--cut theorems and their use in designing approximation algorithms. J.~ACM 46 (1999), 787--832.

  38. [norinstalksiam] S.~Norin, Tur\'an's Brickyard Problem and flag algebras. Talk at the SIAM Conference on Discrete Mathematics. June 18--21, Halifax, Nova Scotia, Canada.

  39. [alk3] J.~Pach and M.~~Sharir, On the number of incidences between points and curves. Combinatorics, Probability, and Computing 7 (1998), 121--127.

  40. [panrichter] S.~Pan and R.B.~Richter, The crossing number of $K_{11}$ is $100$. J. Graph Theory 56 (2007), 128--134.

  41. [rotation] M.J.~Pelsmajer, M.~Schaefer and D.~Stefankovic, Crossing numbers of graphs with rotation systems. Algorithmica 60(3) (2011), 679--702.

  42. [purchase] H.C.~Purchase, Which aesthetic has the greatest effect on human understanding? {\em Proc.~5th.~Int.~Symp.~on Graph Drawing (GD'97)}, Lecture Notes in Computer Science 1353, 248--261. Springer--Verlag, 1997.

  43. [richterthomassen2] R.B.~Richter and C.~Thomassen, Minimal graphs with crossing number at least $k$. J.~Combin.~Theory Ser.~B 58 (1993), 217--224.

  44. [richterthomassen1] R.B.~Richter and C.~Thomassen, Intersections of curve systems and the crossing number of $C\sb 5\times C\sb 5$. Discrete Comput.~Geom. 13 (1995), 149--159.

  45. [dynsch] M.~Schaefer, The graph crossing number and its variants. Electr.~J.~of Comb.. Dynamic Survey (2014).

  46. [ap2] C-Y.~Shen, Algebraic methods in sum-product phenomena. Israel J. Math. 188 (2012), 123--130.

  47. [tao] J.~Solymosi and T.~Tao, An incidence theorem in higher dimensions. Discrete Comput. Geom. 48 (2012), 255--280.

  48. [zolimozi] J.~Solymosi, G.~Tardos and C.D.~T\'oth, The $k$ most frequent distances in the plane. Discrete Comput.~Geom. 28 (2002), 639--648.

  49. [zolimozitocsa} J.~Solymosi and C.D.~T\'oth, Distinct distances in homogeneous sets in Euclidean space. {\em Discrete Comput.~Geom.] 35 (2006), 537--549.

  50. [hard] L.~A.~Sz\'ekely, Crossing numbers and hard Erd\H os problems in discrete geometry, Combinatorics, Probability and Computing 6 (1997) 353--358.

  51. [tardos] G.~Tardos, On distinct sums and distinct distances. Adv.~Math 180 (2003), 275--289.

  52. [welcome] P.~Tur\'an, A note of welcome. Journal of Graph Theory 1 (1977), 7--9.

  53. [woodall] D.R.~Woodall, Cyclic-order graphs and Zarankiewicz's crossing-number conjecture. Journal of Graph Theory 17 (1993), 657--671.

  54. [zaran] K.~Zarankiewicz, On a problem of P.~Tur\'an concerning graphs. Fund. Math. 41, 137--145, (1954).