Crossing Numbers Turn Useful (11w5144)

Objectives

* Profile of participants: a (geographical and thematical) cross--section of people working on crossing numbers.

We would like to bring together people who arrived
at crossing numbers from different directions: topological graph theorists who want to prove general theorems of a structural character; computer scientists who are interested in asymptotic results or estimates on crossing numbers of very large graphs; other computer scientists who are interested in several variants of the crossing number problem to model chip-design problems and want algorithms; network scientists, who look for graph theoretic concepts
potentially useful at grasping the complexity of networks; and discrete geometers who use crossing numbers as a proof technique.

* General objectives

1) Catching up.

Simply put, within the last ten or fifteen years the crossing numbers community has grown and broadened enormously. We propose to layout a plan to ask two or three senior researchers to
overview the state--of--the--art of the subject in their own field of expertise, highlighting how their own work has profited from other crossing number perspectives and clearly outlining the new
frontiers. This set of talks, each of which could run for 60 or up to 90 minutes, would be followed by an informal discussion involving all
participants. We expect to spend the first day of the workshop in this exercise. These keynote speakers would be asked to prepare notes, and
to make available the contents of their presentations. Assuming the facilities at BIRS allow it, it would be ideal to record these talks
and their ensuing discussions.

During the next couple of days, we would ask all participants to give a very short presentation (5--10 minutes) outlining their own recent
work, including one or two open problems. All participants would also be expected to provide a written account of their presentation.

In the spirit of the workshop (getting together people coming from several directions), we would encourage that these interventions have a lively, relaxed, informal spirit: the way we see this workshop, it is the ideal place to talk about which approaches have proved fruitful, which ones turned out to be dead ends, which results we were
aiming for and (as it happens so often) which ones we had to settle for. We expect this relaxed environment to be particularly beneficial to graduate students and junior researchers.

2) Actively let the different approaches to crossing numbers influence each other.

Topological graph theorists interested in proving structural theorems of a general character have traditionally nurtured from very specific questions arising from real--world applications and from algorithmic questions. This would be a great opportunity for the topological graph theory crowd to listen closely to those researchers working in the algorithmic front, not only to learn the
state--of--the--art, but also to see what issues they are facing, what are the relevant open problems, which kind of theoretical results have
been helpful and which new directions they foresee in the near future.

3) Keep the focus on fundamental questions.

We propose to keep a stock of fundamental questions in our fingertips at all times during the workshop. This would help us to keep a focused
eye on what are the really basic questions that have passed the test of time, and with so much and so diverse talent around, we are certain that some progress would be made on some of them.

4) Formally establish a network of crossing number
researchers.

New crossing numbers results are appearing in
all fronts at an unprecedented pace. A formal, coordinated effort to have a central repository of the state--of--the--art in the subject would be of great asset to this growing community.

We have a clear idea on how to undertake this project, namely, the creation of a stable, well--maintained web page with updated (say at least four times a year) information on the state--of--the--art of our subject. We visualize this as an extended version of a Dynamic Survey `a--la Electronic Journal of Combinatorics. This ongoing survey would consist of around a dozen sections, each of which would be maintained by a recognized expert. Needless to say, having together leading researchers from all fronts of crossing numbers into a workshop would greatly increase the chances of success of such an ambitious enterprise.

* Importance

We strongly believe this workshop would be a golden opportunity for the crossing number crowd, to reflect back on its diverse background, and to look forward as a multifaceted discipline in which its building communities look upon each other for new sources of techniques and motivations.

* Timeliness

There are several crossing number communities growing inexorably, each on its own defined direction. While it may be very healthy for a
while to let the somewhat disconnected approaches to keep going with their own momentum, we feel that something is lost if we don't take just a little time to sit down together, get to meet each other, and take mutual advantage of our diversely rich backgrounds.