Computing the flip distance between triangulations

DOI10.1007/S00454-017-9867-XzbMath1371.05063arXiv1407.1525OpenAlexW2528711716MaRDI QIDQ2408209

Eric Sedgwick, Ge Xia, Iyad A. Kanj

Publication date: 10 October 2017

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

triangulationstriangulated graphsparameterized complexityflip distance

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items (15)

A proof of the orbit conjecture for flipping edge-labelled triangulations ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ An improved kernel for the flip distance problem on simple convex polygons ⋮ The rotation distance of brooms ⋮ Orbiting triangle method for convex polygon triangulation ⋮ Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees ⋮ Transforming plane triangulations by simultaneous diagonal flips ⋮ Flip distance and triangulations of a polyhedron ⋮ Unnamed Item ⋮ Transition operations over plane trees ⋮ Flip distances between graph orientations ⋮ An improved FPT algorithm for the flip distance problem ⋮ Convex dominating sets in maximal outerplanar graphs ⋮ Kernelization of Whitney Switches ⋮ Kernelization of Whitney Switches

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the parameterized complexity of reconfiguration problems
• An improved kernel size for rotation distance in binary trees
• Flip distance between triangulations of a simple polygon is NP-complete
• Flip distance between two triangulations of a point set is NP-complete
• Flips in planar graphs
• Triangulations. Structures for algorithms and applications
• Rotation distance is fixed-parameter tractable
• Diagonal flips in Hamiltonian triangulations on the sphere
• Flipping edges in triangulations
• A lower bound on the number of triangulations of planar point sets
• Flip distance between triangulations of a planar point set is APX-hard
• Transforming triangulations
• Vertex Cover Reconfiguration and Beyond
• Reconfiguration over Tree Decompositions
• Flip Distance Is in FPT Time O(n+ k * c^k)
• An improved lower bound on the minimum number of triangulations
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• Short Encodings of Evolving Structures
• Efficient Planarity Testing
• Diagonal flips in labelled planar triangulations

This page was built for publication: Computing the flip distance between triangulations