Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique
Metadata only
Date
2012-06Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
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.8181N) for cycles and O(1.1067N) for matchings. These imply a new upper bound of O(54.543N) 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.664N)). Our analysis is based on a weighted variant of Kasteleyn's linear algebra technique. Show more
Publication status
publishedExternal links
Book title
SoCG '12: Proceedings of the Twenty-Eighth Annual Symposium on Computational GeometryPages / Article No.
Publisher
Association for Computing MachineryEvent
Subject
Spanning cycles; Perfect matchings; Kasteleyn's technique; TriangulationsOrganisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
More
Show all metadata
ETH Bibliography
yes
Altmetrics