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

Organizers:
É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".) http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS21

Pach, J, Tóth G.: Thirteen Problems on Crossing Numbers http://math.cims.nyu.edu/~pach/publications/13problems.ps

Richter, R.B., Salazar, G.: Crossing numbers http://www.math.uwaterloo.ca/~brichter/pubs/June2008.pdf

Full information and how to apply can be found here.
 

Contact Information

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

Further web info for 2017 participants.