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.
1
-
$\begingroup$ This may be the same as 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). $\endgroup$– Gerry MyersonCommented Jul 24, 2013 at 7:39
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
9
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.
answered Jul 24, 2013 at 10:48
-
$\begingroup$ 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. $\endgroup$ Commented Jul 24, 2013 at 12:18
-
$\begingroup$ 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? $\endgroup$ Commented Jul 24, 2013 at 12:44
-
1$\begingroup$ 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. $\endgroup$ Commented Jul 24, 2013 at 12:47
-
$\begingroup$ 12 graphs in cs.anu.edu.au/~bdm/8-gon-triang.pdf $\endgroup$ Commented Jul 24, 2013 at 12:59
-
$\begingroup$ A131481 seems to be the diagonal in the first table at recmath.com/PolyPages/PolyPages/index.htm?Isopoly1s.html . Maybe that helps. $\endgroup$ Commented Jul 24, 2013 at 13:09