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.