Disjoint compatibility graph of non-crossing matchings of points in convex position

zbMATH Open1308.05086arXiv1403.5546MaRDI QIDQ2263780FDOQ2263780

Tillmann Miltzow, Andrei Asinowski, Oswin Aichholzer

Publication date: 19 March 2015

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $X_{2k}$ be a set of $2k$ labeled points in convex position in the plane. We consider geometric non-intersecting straight-line perfect matchings of $X_{2k}$. Two such matchings, $M$ and $M^{\prime }$, are disjoint compatible if they do not have common edges, and no edge of $M$ crosses an edge of $M^{\prime }$. Denote by $mathrm{DCM}_k$ the graph whose vertices correspond to such matchings, and two vertices are adjacent if and only if the corresponding matchings are disjoint compatible. We show that for each $kgeq9$, the connected components of $mathrm{DCM}_k$ form exactly three isomorphism classes -- namely, there is a certain number of isomorphic small components, a certain number of isomorphic medium components, and one big component. The number and the structure of small and medium components is determined precisely.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

non-crossing partitionsreconfiguration graphcombinatorial enumerationplanar straight-line graphsdisjoint compatible matchingsnon-crossing geometric drawings

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Flipping edges in triangulations
• Relations between the ‘percolation’ and ‘colouring’ problem and other graph-theoretical problems associated with regular planar lattices: some exact results for the ‘percolation’ problem
• Catalan, Motzkin, and Riordan numbers
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• On the Number of Crossing‐Free Matchings, Cycles, and Partitions
• A large dihedral symmetry of the set of alternating sign matrices
• Combinatorial nature of the ground-state vector of the \(\mathrm{O}(1)\) loop model
• Proof of the Razumov-Stroganov conjecture
• Graphs of non-crossing perfect matchings
• Graphs of triangulations and perfect matchings
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• Computing simple circuits from a set of line segments
• A bijection between classes of fully packed loops and plane partitions
• Sequences of spanning trees and a fixed tree theorem
• Every set of disjoint line segments admits a binary tree
• Compatible geometric matchings
• Historical Note on a Recurrent Combinatorial Problem
• Point sets with many non-crossing perfect matchings
• Disjoint compatible geometric matchings
• Riordan paths and derangements
• Flip distance between triangulations of a simple polygon is NP-complete
• Quasi-Parallel Segments and Characterization of Unique Bichromatic Matchings
• Linear transformation distance for bichromatic matchings
• Bichromatic compatible matchings

Cited In (7)

• Packing 1-plane Hamiltonian cycles in complete geometric graphs
• Transition operations over plane trees
• Disjoint compatibility via graph classes
• Flip Distance to some Plane Configurations.
• On flips in planar matchings
• Compatible spanning trees in simple drawings of \(K_n\)
• Flip distance to some plane configurations

Recommendations

• Graphs of non-crossing perfect matchings 👍 👎
• Disjoint compatible geometric matchings 👍 👎
• Disjoint compatible geometric matchings 👍 👎
• Characterization of a class of graphs related to pairs of disjoint matchings 👍 👎
• Pairs of disjoint matchings and related classes of graphs 👍 👎
• Computing maximum non-crossing matching in convex bipartite graphs 👍 👎
• Computing Maximum Non-crossing Matching in Convex Bipartite Graphs 👍 👎
• Disjoint compatibility via graph classes 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Disjoint compatibility graph of non-crossing matchings of points in convex position

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