On the Number of Crossing‐Free Matchings, Cycles, and Partitions

DOI10.1137/050636036zbMath1120.68085OpenAlexW2085179971WikidataQ54308783 ScholiaQ54308783MaRDI QIDQ3446814

Micha Sharir, Ermo Welzl

Publication date: 26 June 2007

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/050636036

zbMATH Keywords

countingcrossing-free geometric graphscrossing-free partitionssimple polygonizationscrossing-free matchings

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial complexity of geometric structures (52C45)

Related Items (35)

Configurations of non-crossing rays and related problems ⋮ On Compatible Matchings ⋮ On the number of plane geometric graphs ⋮ Convex Polygons in Geometric Triangulations ⋮ Convex Polygons in Geometric Triangulations ⋮ On the number of crossing-free partitions ⋮ Packing 1-plane Hamiltonian cycles in complete geometric graphs ⋮ Perfect matchings with crossings ⋮ Parameterized analysis and crossing minimization problems ⋮ Trapezoidal diagrams, upward triangulations, and prime Catalan numbers ⋮ Crossings in grid drawings ⋮ An upper bound for the number of rectangulations of a planar point set ⋮ Disjoint compatible geometric matchings ⋮ A QPTAS for the base of the number of crossing-free structures on a planar point set ⋮ Point sets with many non-crossing perfect matchings ⋮ Linear transformation distance for bichromatic matchings ⋮ Colored ray configurations ⋮ Crossing-Free Perfect Matchings in Wheel Point Sets ⋮ On numbers of pseudo-triangulations ⋮ From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices ⋮ Counting polygon triangulations is hard ⋮ Counting Plane Graphs with Exponential Speed-Up ⋮ Special Frequency Quadrilaterals and an Application ⋮ Flips in planar graphs ⋮ Structural properties of bichromatic non-crossing matchings ⋮ Untangling planar graphs from a specified vertex position-Hard cases ⋮ Disjoint compatibility graph of non-crossing matchings of points in convex position ⋮ Perfect matchings with crossings ⋮ Unnamed Item ⋮ Monotone paths in geometric triangulations ⋮ Connecting the dots (with minimum crossings) ⋮ The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem ⋮ Counting triangulations and other crossing-free structures approximately ⋮ Counting triangulations and other crossing-free structures via onion layers ⋮ A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals

This page was built for publication: On the Number of Crossing‐Free Matchings, Cycles, and Partitions