Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique

DOI10.1145/2261250.2261277MaRDI QIDQ2874581zbMATH OpenOpenAlexFDO

Authors Adam Sheffer, Micha Sharir, Emo Welzl

Publication date 7 August 2014

Published in Proceedings of the twenty-eighth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.5596

zbMATH Keywords

Kasteleyn's techniqueperfect matchingsspanning cyclestriangulations

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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

Recommendations

• Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
• On the Number of Crossing‐Free Matchings, Cycles, and Partitions
• Counting and enumerating crossing-free geometric graphs

Cited in

(7)

• How to calculate the number of perfect matchings in finite sections of certain infinite plane graphs
• Disjoint compatible geometric matchings
• Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
• On numbers of pseudo-triangulations
• On the Number of Crossing‐Free Matchings, Cycles, and Partitions
• On the number of spanning trees a planar graph can have
• An empirical study on randomized optimal area polygonization of planar point sets

This page was built for publication: Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2874581)