The Library
On flips in planar matchings
Tools
Milich, Marcel, Mutze, Torsten and Pergel, Martin (2021) On flips in planar matchings. Discrete Applied Mathematics, 289 . pp. 427-445. doi:10.1016/j.dam.2020.10.018 ISSN 0166-218X.
|
PDF
WRAP-On-flips-planar-matchings-Mutze-2020.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (1772Kb) | Preview |
Official URL: https://doi.org/10.1016/j.dam.2020.10.018
Abstract
In this paper we investigate the structure of flip graphs on non-crossing perfect matchings in the plane.
Consider all non-crossing straight-line perfect matchings on a set of $2n$ points that are placed equidistantly on the unit circle.
The graph~$\mathcal{H}_n$ has those matchings as vertices, and an edge between any two matchings that differ in replacing two matching edges that span an empty quadrilateral with the other two edges of the quadrilateral, provided that the quadrilateral contains the center of the unit circle.
We show that the graph~$\mathcal{H}_n$ is connected for odd~$n$, but has exponentially many small connected components for even~$n$, which we characterize and count via Catalan and generalized Narayana numbers.
For odd $n$, we also prove that the diameter of~$\mathcal{H}_n$ is linear in~$n$.
Furthermore, we determine the minimum and maximum degree of~$\mathcal{H}_n$ for all~$n$, and characterize and count the corresponding vertices.
Our results imply the non-existence of certain rainbow cycles, and they answer several open questions and conjectures raised in a recent paper by Felsner, Kleist, M\"utze, and Sering.
Item Type: | Journal Article | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
|||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
Library of Congress Subject Headings (LCSH): | Graph theory -- Data processing, Graph theory, Combinatorial analysis | |||||||||
Journal or Publication Title: | Discrete Applied Mathematics | |||||||||
Publisher: | Elsevier Science Ltd. | |||||||||
ISSN: | 0166-218X | |||||||||
Official Date: | 31 January 2021 | |||||||||
Dates: |
|
|||||||||
Volume: | 289 | |||||||||
Page Range: | pp. 427-445 | |||||||||
DOI: | 10.1016/j.dam.2020.10.018 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||
Date of first compliant deposit: | 5 October 2020 | |||||||||
Date of first compliant Open Access: | 7 November 2021 | |||||||||
RIOXX Funder/Project Grant: |
|
|||||||||
Related URLs: | ||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year