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

zbMath1308.05086arXiv1403.5546MaRDI QIDQ2263780

Tillmann Miltzow, Andrei Asinowski, 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

zbMATH Keywords

combinatorial enumerationnon-crossing partitionsreconfiguration graphplanar straight-line graphsdisjoint compatible matchingsnon-crossing geometric drawings

Mathematics Subject Classification ID

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

Related Items (7)

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

Cites Work

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

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