Mathematics Research Communities

Week 2: June 11 – 17, 2017, Beyond Planarity: Crossing Numbers of Graphs

Éva Czabarka (University of South Carolina)
Silvia Fernández-Merchant (California State University, Northridge)
Gelasio Salazar (Universidad Autonoma de San Luis Potosi, Mexico)
Marcus Schaefer (DePaul University)
László A. Székely (University of South Carolina)

When a non-planar graph is drawn in the plane, some edge crossings result. One may want to minimize the number of crossings under different definitions of drawing and different methods of counting them. Crossing numbers of graphs play an important role in areas ranging from the applied—such as VLSI design, graph visualization, coevolution—to the theoretical—such as incidence problems for points and curves, and other problems of discrete geometry. Tantalizing open problems abound, including the determination of the crossing number for large complete graphs. Crossing numbers are vigorously investigated by computer science and mathematics communities.

The target audience of this workshop is graduate students and early-career mathematicians/computer scientists who have an interest in graph theory, discrete geometry, algorithms, or complexity theory. Only familiarity with basic graph theory is expected. At the workshop, collaborative research in groups will commence on a variety of promising crossing number problems under the guidance of experts in the area.

Suggested Readings:

B. M. ´Abrego, B.M, Fernández-Merchant, S., and Gelasio Salazar, G: The rectilinear crossing number of K_n: closing in (or are we?). Thirty essays in Geometric Graph Theory (János Pach, Ed.). Springer (2013), pp. 5-18.

Beineke, L., Wilson, R.: The early history of the Brick Factory Problem. The Mathematical Intelligencer 32(2), 41-48 (2010).

Székely, L.A.: Turán's Brick Factory Problem: the Status of the Conjectures of Zarankiewicz and Hill, in: Graph Theory Favorite Conjectures and Open Problems, eds. R. Gera, S. Hedetniemi, C. Larson, Problem Books in Mathematics series, Springer-Verlag, to appear in September 2016.

Schaefer, M.: The graph crossing number and its variants: a survey. Electr. J. Comb. Dynamic Survey \#DS21: May 15, (2014). (Read the text before the chapter "A Compendium of Crossing Numbers".)

Pach, J, Tóth G.: Thirteen Problems on Crossing Numbers

Richter, R.B., Salazar, G.: Crossing numbers

Full information and how to apply can be found here.

Contact Information

For further information, please contact Associate Executive Director at

Here is a list of individuals who participated in this conference:

Aida Abiad
Elie Alhajjar
Robin Lydiann Anderson
John Asplund
Pavel Avdeyev
Shuliang Bai
Martin Balko
Fidel Barrera-Cruz
Axel T. Brandt
Charles Anthony Camacho
Walter Carballosa
Hsien-Chih Chang
Gregory J. Clark
Garner Paul Cochran
Giordano Da Lozzo
Jennifer Diemunsch
Thao T. Do
Joshua E. Fallon
Arran Christopher Hamm
Natalie Hobson
Kirsten Hogenson
Kenan Andrew Ince
Tanya Spellman Jeffries
Marija Jelic
Lauren Keough
Rachel Kirsch
Linda Kleist
Jephian C.-H Lin
Sarah Loeb
Mario Lomeli
Elizabeth Ashley Bailey Matson
Austin T. Mohr
Carlos Alejandro Alfaro Montufar
Alain Olavarrieta
Yakov Sapozhnikov
Heather Christina Smith
Pablo Soberón
Libby Taylor
Zhiyu Wang
Hays Whitlatch

Further web info for 2017 participants.

Top of Page