Crossing Numbers: Theory and Applications (18w5029)


Bojan Mohar (Simon Fraser University)

(University of South Carolina)

Gelasio Salazar (Universidad Autonoma de San Luis Potosi)


The Banff International Research Station will host the "Crossing Numbers: Theory and Applications " workshop from October 21st to October 26th, 2018.

An ancient problem asks: A town contains three cottages and three utilities. Each cottage needs to be connected to each utility. Can all nine connections be made without any of the lines crossing?

The answer is no: regardless of how the lines are laid out there is some place where a pair must cross. While phrased as just a puzzle, the rapid growth in computers and their ubiquitous applications made the underlying question very important. Instead of thinking of cottages connected to utilities, we have processors connected by wires reflecting lines of communication. Wires in computers should not cross unnecessarily; the consequences can be shocking.

The application raises many interesting questions. For example, can we determine exactly which networks can be laid out without crossings? If a network must have some crossings, how do we find the layout with the fewest number? This minimum is called the crossing number. The exact number is difficult to calculate even for relatively simple networks. It has an interesting relation to the geometry of the plane.

The main focus of this conference is the study of crossing numbers. We will bring together experts from around to world who study both the theoretical side and practical applications. Issues important to each perspective should enhance those studied by the other.

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the U.S. National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT).