Here is the flip graph of 3x3 triangulations again, with the triangulations grouped according to their set of length-sqrt(2) edges. The number of edges shown between each pair of groups indicates the number of pairs of triangulations that can be flipped from one group to the other. Despite not showing the detailed connections as well, I think this kind of clustered graph drawing makes the overall structure of the flip graph much clearer.





Comments:

imluxionverdin:
2006-09-23T03:39:03Z
Nice.
11011110:
2006-09-23T03:44:21Z
Thanks!
boyinasuitcase:
2006-09-23T09:50:30Z
Very impressive. I especially liked this one.
None:
2006-09-23T10:54:11Z
Does it make sense to factor out the symmetries of the square? -Ken Clarkson
11011110:
2006-09-23T16:07:56Z
I guess it depends on what you're trying to analyze. If you want a roadmap of the possible triangulations, and what flips are available from each, the factored version would probably be more compact. And if you're trying to count triangulations asymptotically (as Emo was in his talk) either way could work, though not factoring out the symmetries could lead to simpler encodings that are easier to count. But what I'm wondering about is the global structure of the flip graph, and I think factoring symmetries could destroy that structure; e.g., it's bipartite, but the factored graph might not be.
11011110:
2006-09-23T16:03:43Z
Thanks! Though, my dissatisfaction with that one (its reduced symmetry, and the small relative size of the individual grids) was what led me to draw it again here...