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

MaRDI QIDQ2263780zbMATH OpenFDO

Authors Andrei Asinowski, Tillmann Miltzow, Oswin Aichholzer

Publication date 19 March 2015

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

Full work available at URL https://arxiv.org/abs/1403.5546, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p65

IPFS 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)

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.

Recommendations

• Non-crossing configurations in complements of geometric graphs and disjoint compatibility
• Graphs of non-crossing perfect matchings
• Disjoint compatible geometric matchings
• Disjoint compatible geometric matchings
• Disjoint compatibility via graph classes
• Pairs of disjoint matchings and related classes of graphs
• Characterization of a class of graphs related to pairs of disjoint matchings
• Noncrossing matchings with fixed points
• Computing maximum non-crossing matching in convex bipartite graphs
• Computing maximum non-crossing matching in convex bipartite graphs

Cites work

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

Cited in

(10)

• Packing 1-plane Hamiltonian cycles in complete geometric graphs
• Disjoint compatibility via graph classes
• On flips in planar matchings
• Non-crossing configurations in complements of geometric graphs and disjoint compatibility
• Graphs of triangulations and perfect matchings
• Compatible spanning trees in simple drawings of \(K_n\)
• Flip distance to some plane configurations
• Graphs of non-crossing perfect matchings
• Compatible geometric matchings
• Flip distance to some plane configurations

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)