Speaker: Emo Welzl, ETH Zurich
Title: On the Number of Crossing Free Configurations of Planar Point Sets
Abstract: We consider the family of crossing-free geometric graphs of a 
certain type -- most notably triangulations, but also spanning 
(Hamiltonian) cycles, spanning trees, matchings, etc. -- on a given 
finite point set in the plane. In particular, we address the question of 
how large these families can be in terms of the number of points. After 
the issue was raised for Hamiltonian cycles by Newborn and Moser, and 
for triangulations by Avis, it was shown in 1982 by Ajtai, Chv\'atal, 
Newborn, and Szemer\'edi that for any set $P$ of $n$ points the number 
of \emph{all} crossing-free geometric graphs on $P$ is at most $c^n$ for 
$c=10^{13}$ (as opposed to the previously known bounds of the form $c^{n 
\log n}$). We review some of the developments since then. While this 
problem seems elusive despite of some progress, related algorithmic 
questions are even less understood: For example the complexity of 
determining or approximating the number of triangulations of a point set 
or generating a triangulation uniformly at random from all 
triangulations of a point set.