3

The number of triangulations of a convex $n$-gon is $C_{n-2}$ the $n-2$nd Catalan number. What I am wondering, is if there is a way to enumerate the isomorphism types of these as graphs? I am currently working an a project where I want to only consider all possible unlabeled triangulations of $n$-gons as a way to classify an $n$-gon. Clearly $C_{n-2}$ is an upper bound, but I haven't been able to make or find any progress on that thus far.

Minirogue
  • 143
  • This may be the same as http://oeis.org/A131481 --- number of $n$-cell polyiamonds (triangular polyominoes) with perimeter $n+2$ (but shifted by 2, that is, there are 3 classes of triangulations of a 6-gon, and 3 4-cell polyiamonds with perimeter 6). – Gerry Myerson Jul 24 '13 at 07:39

1 Answers1

6

If I understand correctly, these are A001683 if turning over the $n$-gon is not allowed as an isomorphism, and A000207 if it is. In both articles there are formulae.

You might also be interested that plantri can compute these isomorphism classes very quickly, several hundred thousand per second. The argument lists for triangulating an $n$-gon are "plantri -P# -c2m2 -o #" and "plantri -P# -c2m2 #" respectively, where # is the value of $n$.

ADDED: Every abstract isomorphism between two triangulations preserves the $n$-gon, for the following reason. The $n$-gon is a hamiltonian cycle in the graph. Every chord is a separating edge (removing its two vertices disconnects the graph) and such edges cannot lie on a hamiltonian cycle. I.e., the $n$-gon is the unique hamiltonian cycle.

Brendan McKay
  • 37,203
  • OP asks for isomorphism classes as graphs, whereas the links you give are to isomorphism classes under the action of the cyclic or dihedral groups. I think it's possible for two of these graphs to be isomorphic even if there is no rigid motion taking one to the other. I count 11 classes of triangulation of the octagon (in accord with A131481 in my comment) while A000207 gives 12. – Gerry Myerson Jul 24 '13 at 12:18
  • I asked for clarification from the OP, but then I thought: any abstract isomorphism maps triangles to triangles, so it may be a bit hard to avoid mapping the $n$-gon to itself. Up to $n=20$, they are all non-isomorphic as graphs (i.e 12 for an 8-gon, not 11). How can we resolve this? – Brendan McKay Jul 24 '13 at 12:44
  • 1
    Diagrams at 50 paces. Unfortunately, I am an unarmed man, as I don't have the computer-savvy to transfer my little drawings on scraps of paper to the internet. – Gerry Myerson Jul 24 '13 at 12:47
  • 12 graphs in http://cs.anu.edu.au/~bdm/8-gon-triang.pdf – Brendan McKay Jul 24 '13 at 12:59
  • A131481 seems to be the diagonal in the first table at http://www.recmath.com/PolyPages/PolyPages/index.htm?Isopoly1s.html . Maybe that helps. – Brendan McKay Jul 24 '13 at 13:09
  • OK, I was counting your graphs 1 and 11 as isomorphic for some reason that made perfectly good sense at the time but which I can no longer support. 12 it is, A131481 it isn't. – Gerry Myerson Jul 24 '13 at 13:15
  • I was, in fact, referring to http://oeis.org/A000207. At the time that I posted this, I wan't yet familiar with the OEIS. Thank you – Minirogue Mar 17 '15 at 20:10
  • @BrendanMcKay having studied https://mathoverflow.net/questions/114646/ i realise there is an isomorphism between a) the families of triangulations of an (n+1)-gon in which every pair of triangulations shares some diagonal and b) the triangulations of an n-gon. I have a notional proof involving the number of maps across a matrix, after deducting duplicates which are rotations or reflections of each other but it will take some considerable work to convert into something communicable. However I can see that your answer above is a more elegant expression of the same concept. – it's a hire car baby Nov 24 '17 at 09:58
  • @BrendanMcKay the key to the linked problem is to realise that the largest family of intersecting triangulations must all share the same diagonal. Isomorphism proves this because triangulation of an n-gon is fundamentally the non crossing partitions of a group. The concept of noncrossing relies depends upon selecting some ordering of the group. The isomorphism in question sends selection of the diagonal which the family shares, to the choice of the start and end of the ordering. I thought I'd mention it in case you care to have a look. – it's a hire car baby Nov 24 '17 at 10:05