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 know exact answers are a rarity; more often we know upper and lower bounds of the form cn but where the constant c in the upper bound is much bigger than the one in the lower bound.

One particular question Emo described in some detail concerned triangulations of an n×n grid of points. He described an encoding of a triangulation as a sequence of bits, where each bit describes the edge through one of the grid's half-integer points. Anclin used this idea to prove a bound of O(8n2) on the number of triangulations, but Emo showed that the bits are sufficiently unbalanced in the number of 0's vs 1's that one can get a better bound of roughly the number in position n2 of the Fibonacci series (approximately 6.86n2), but something he said in passing here intrigued me: apparently, for these point sets, if one forms a flip graph with a vertex per triangulation and an edge when two triangles differ by changing the diagonal of a single quadrilateral, this graph is bipartite and can be represented as an induced subgraph of a hypercube. This made me wonder whether these flip graphs might be partial cubes themselves; when I asked, he said no because they have cubic diameter while the diameter of the hypercube they're embedded in is only quadratic, but of course it might still be possible for them to also embed into a larger hypercube, so I don't think the question is settled.

Here's a simplified version of the question: Suppose you have a point set where the points lie on two horizontal lines — e.g., a 2×n grid, although the grid placement is irrelevant for such sets. What do their triangulations look like? If there are n points, there must be n-2 triangles in the triangulation, and we can encode the triangulation by specifying a bit per triangle, in left to right order: 0 if it has an edge on the upper line, 1 if it has an edge on the lower line. When we do, we can see some interesting structure, as below for the flip graph of a 2×4 grid.

It looks very much like an isometric lattice subgraph, only the labels are not isometric: they differ by two for every flip in the triangulations, while we would prefer labels that differ by one. The label set forms all ways of choosing three items out of six, and this is not a coincidence: on any two lines with x points above and y points below, the label set can be described as the set of choices of x-1 items out of x+y-2. To find isometric lattice labels for such choices, label them with the vector of positions of the chosen x-1 items, in sorted order; for instance, the triangulation labeled 001101 in the figure would be labeled by the vector of positions of the 1's, (2,3,5). Besides being isometric, this family of label vectors forms a distributive lattice under componentwise minimum and maximum operations. So the flip graph of points on two lines form a partial cube, and provides a natural partial cube structure to the family of choices of k items out of an ordered set of n.

Tags: combinatorial enumeration, conferences, flip graphs, graph drawing, karlsruhe, media theory, talks, triangulation
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded  

  • 2 comments