Geometric and Structural Graph Theory (17w5154)

Arriving in Banff, Alberta Sunday, August 20 and departing Friday August 25, 2017


(Princeton University)

(École Polytechnique Fédérale de Lausanne)

Bojan Mohar (Simon Fraser University)


This workshop will follow a similar model as used in a highly successful BIRS workshop that some of us have organized in 2006. At that time we have focused of bringing together researchers working in Topological Graph Theory with those working in Geometric Graph Theory and crossing numbers. This time the goal is to include some of the main protagonists in the newly emerging area of Computational Topology (H. Edelsbrunner, J. Erickson, E. Colin de Verdiere, S. Cabello) and work on related questions from structural graph theory. One particular example where we expect some synergy are problems about graph immersions. We intend to have a number of graduate students and postdocs. For them it will be instrumental to be able learn a great deal about the methods, results and open problems in the areas of Topological and Geometric Graph Theory, together with Structural Graph Theory in combination with Discrete Geometry and Computational Topology.

Specific questions that we plan to discuss at the meeting are: Hadwiger conjecture from 1943 (stating that graphs with the complete graph $K_n$ excluded as a minor have chromatic number less than $n$); Erdős-Hajnal conjecture; Harary-Hill conjecture and the Turan problem from 1960's about the crossing number of complete and complete bipartite graphs; Well-quasiordering of the strong immersion relation, computational problems related to graph immersions, and the Hadwiger Conjecture version for immersions. All these problems have undergone through a (partial) breakthrough in the last 10 years but further progress is stuck at this time. We hope for synergy of the tools and methods used in some of these areas to give additional boost for the others.