Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique

Details Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique

2011-09-26

arxiv.org/abs/1109.5596v1

Computer Science

Discrete Mathematics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-689622