Flip distance to some plane configurations

DOI10.4230/LIPICS.SWAT.2018.11zbMATH Open1477.05058OpenAlexW2805404443MaRDI QIDQ5116475FDOQ5116475

Ahmad Biniaz, Michiel Smid, Anil Maheshwari

Publication date: 25 August 2020

Full work available at URL: https://dblp.uni-trier.de/db/conf/swat/swat2018.html#BiniazMS18

Recommendations

• Flip distance to some plane configurations
• Complexity results on untangling red-blue matchings
• On flips in planar matchings
• Flip distance is in FPT time \(O(n+ k \cdot c^k)\)
• The Flip Diameter of Rectangulations and Convex Subdivisions

zbMATH Keywords

spanning treesperfect matchingsflip distancenon-crossing edges

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Flipping edges in triangulations
• Title not available (Why is that?)
• Non-crossing matchings of points with geometric objects
• Cutting dense point sets in half
• Transforming triangulations
• Flips in planar graphs
• Lines, line-point incidences and crossing families in dense sets
• A History of Flips in Combinatorial Triangulations
• Nearest neighbor queries in metric spaces
• Title not available (Why is that?)
• Disjoint compatible geometric matchings
• A bottleneck matching problem with edge-crossing constraints
• Flip distance between triangulations of a simple polygon is NP-complete
• The Number of Flips Required to Obtain Non-crossing Convex Cycles
• Bichromatic compatible matchings
• Disjoint compatibility graph of non-crossing matchings of points in convex position
• Compatible spanning trees

Cited In (1)

• Complexity results on untangling red-blue matchings

This page was built for publication: Flip distance to some plane configurations

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