Flip distance between two triangulations of a point set is NP-complete

DOI10.1016/j.comgeo.2014.11.001zbMath1333.65022arXiv1205.2425OpenAlexW2110762325MaRDI QIDQ906837

Vinayak Pathak, Anna Lubiw

Publication date: 29 January 2016

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1205.2425

zbMATH Keywords

rotationstriangulationsNP-completenessflipsbinary search treesflip distance

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (27)

On the parameterized complexity of reconfiguration of connected dominating sets ⋮ Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ Computing the flip distance between triangulations ⋮ A proof of the orbit conjecture for flipping edge-labelled triangulations ⋮ Token sliding on graphs of girth five ⋮ Flip distance between triangulations of a simple polygon is NP-complete ⋮ On the longest flip sequence to untangle segments in the plane ⋮ Galactic token sliding ⋮ Complexity results on untangling red-blue matchings ⋮ Token sliding on graphs of girth five ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ The rotation distance of brooms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On girth and the parameterized complexity of token sliding and Token Jumping ⋮ Reconfiguration on sparse graphs ⋮ Transforming plane triangulations by simultaneous diagonal flips ⋮ On flips in planar matchings ⋮ Unnamed Item ⋮ Transition operations over plane trees ⋮ Flip distances between graph orientations ⋮ An improved FPT algorithm for the flip distance problem ⋮ The Perfect Matching Reconfiguration Problem ⋮ Convex dominating sets in maximal outerplanar graphs ⋮ Kernelization of Whitney Switches ⋮ Introduction to reconfiguration ⋮ Kernelization of Whitney Switches

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• All triangulations are reachable via sequences of edge-flips: an elementary proof
• Efficient lower and upper bounds of the diagonal-flip distance between triangulations
• On the rotation distance between binary trees
• Strictly convex drawings of planar graphs
• Flip distance between triangulations of a simple polygon is NP-complete
• Flips in planar graphs
• Triangulations. Structures for algorithms and applications
• Rotation distance is fixed-parameter tractable
• A note on some tree similarity measures
• Transforming triangulations in polygonal domains
• On triangulating planar graphs under the four-connectivity constraint
• An efficient upper bound of the rotation distance of binary trees
• Lower bounds on the rotation distance of binary trees
• Flipping edges in triangulations
• Flip distance between triangulations of a planar point set is APX-hard
• Transforming triangulations
• Happy endings for flip graphs
• Rotation Distance, Triangulations, and Hyperbolic Geometry

This page was built for publication: Flip distance between two triangulations of a point set is NP-complete