We derive improved upper bounds on the number of crossing-free
straight-edge spanning cycles (also known as Hamiltonian tours and
simple polygonizations) that can be embedded over any specific set of
N points in the plane. More specifically, we bound the ratio between
the number of spanning cycles (or perfect matchings) that can be
embedded over a point set and the number of triangulations that can be
embedded over it. The respective bounds are O(1.8181^N) for cycles and
O(1.1067^N) for matchings. These imply a new upper bound of
O(54.543^N) on the number of crossing-free straight-edge spanning
cycles that can be embedded over any specific set of N points in the
plane (improving upon the previous best upper bound O(68.664^N)). Our
analysis is based on Kasteleyn's linear algebra technique.
This is a joint work with Micha Sharir and Emo Welzl.