Flip Distance to some Plane Configurations.

DOI10.4230/LIPIcs.SWAT.2018.11zbMath1477.05058OpenAlexW2805404443MaRDI QIDQ5116475

Ahmad Biniaz, Anil Maheshwari, Michiel H. M. Smid

Publication date: 25 August 2020

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

zbMATH Keywords

perfect matchingsspanning treesflip distancenon-crossing edges

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Non-crossing matchings of points with geometric objects
• Flip distance between triangulations of a simple polygon is NP-complete
• Flips in planar graphs
• Nearest neighbor queries in metric spaces
• Cutting dense point sets in half
• Flipping edges in triangulations
• Lines, line-point incidences and crossing families in dense sets
• Disjoint compatible geometric matchings
• Disjoint compatibility graph of non-crossing matchings of points in convex position
• Bichromatic compatible matchings
• Compatible spanning trees
• Transforming triangulations
• A Bottleneck Matching Problem with Edge-Crossing Constraints
• A History of Flips in Combinatorial Triangulations
• The Number of Flips Required to Obtain Non-crossing Convex Cycles

This page was built for publication: Flip Distance to some Plane Configurations.