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.

flip graph of 3x3 triangulations




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...