0xDE (11011110) wrote,  Triangulations of points on two lines
I'm in Karlsruhe for Graph Drawing 2006. The first day had many
interesting talks; my own (in the session on tree drawing)
seemed to go well, and I've put the slides online here.  I
especially enjoyed Emo Welzl's invited talk, on counting
noncrossing configurations. A typical problem in this area would
be to ask how many triangulations a set of (n+2) points in
convex position has? This is, he says, known as the Euler-Segner
problem, and the answer is the Catalan numbers, (2n choose
n)/(n+1), asymptotically &Theta(4nn-3/2). Or how many crossing-
free perfect matchings are there on such a point set (the
Catalan numbers again, but with index n/2 instead of n). Or
noncrossing spanning trees, or simple Hamiltonian cycles, or...
And the point set can be in convex position, or a grid, or a
point set designed to make the number as large as possible, or
as small as possible... So there are a lot of different problems
of this type, and the ones for which we