Computing the flip distance between triangulations

DOI10.1007/S00454-017-9867-XMaRDI QIDQ2408209zbMATH OpenOpenAlexFDO

Authors Eric Sedgwick, Ge Xia, Iyad 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

flip distanceparameterized complexitytriangulated graphstriangulations

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)

Abstract: Let $calT$ be a triangulation of a set $calP$ of $n$ points in the plane, and let $e$ be an edge shared by two triangles in $calT$ such that the quadrilateral $Q$ formed by these two triangles is convex. A {em flip} of $e$ is the operation of replacing $e$ by the other diagonal of $Q$ to obtain a new triangulation of $calP$ from $calT$. The {em flip distance} between two triangulations of $calP$ is the minimum number of flips needed to transform one triangulation into the other. The Flip Distance problem asks if the flip distance between two given triangulations of $calP$ is at most $k$, for some given $kinN$. It is a fundamental and a challenging problem. We present an algorithm for the {sc Flip Distance} problem that runs in time $O(n+kcdot{c}^k)$, for a constant $cleq2cdot14^{11}$, which implies that the problem is fixed-parameter tractable. We extend our results to triangulations of polygonal regions with holes, and to labeled triangulated graphs.

Recommendations

• Flip distance is in FPT time O(n+ k c^k)
• An improved FPT algorithm for the flip distance problem
• scientific article; zbMATH DE number 7204399

Cites work

• A lower bound on the number of triangulations of planar point sets
• An improved kernel size for rotation distance in binary trees
• An improved lower bound on the minimum number of triangulations
• Diagonal flips in Hamiltonian triangulations on the sphere
• Diagonal flips in labelled planar triangulations
• Efficient Planarity Testing
• Flip distance between triangulations of a planar point set is APX-hard
• Flip distance between two triangulations of a point set is NP-complete
• Flip distance is in FPT time O(n+ k c^k)
• Flipping edges in triangulations
• Flips in planar graphs
• Graph theory
• scientific article; zbMATH DE number 2185626 (Why is no real title available?)
• scientific article; zbMATH DE number 3575612 (Why is no real title available?)
• scientific article; zbMATH DE number 1079755 (Why is no real title available?)
• scientific article; zbMATH DE number 1418487 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Reconfiguration over tree decompositions
• Rotation distance is fixed-parameter tractable
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• Short Encodings of Evolving Structures
• Transforming triangulations
• Triangulations. Structures for algorithms and applications
• Vertex Cover Reconfiguration and Beyond

Cited in

(27)

• 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
• An improved FPT algorithm for the flip distance problem
• Convex dominating sets in maximal outerplanar graphs
• A proof of the orbit conjecture for flipping edge-labelled triangulations
• Flip distance between triangulations of a planar point set is APX-hard
• Flip distance is in FPT time O(n+ k c^k)
• Flip Algorithm for Segment Triangulations
• scientific article; zbMATH DE number 1418487 (Why is no real title available?)
• Kernelization of Whitney switches
• scientific article; zbMATH DE number 7204399 (Why is no real title available?)
• Orbiting triangle method for convex polygon triangulation
• Kernelization of Whitney Switches
• Flip distances between graph orientations
• Flip paths between lattice 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
• Flip distance and triangulations of a polyhedron
• An \(\mathcal{O}(3.82^k)\) time \(\mathcal{FPT}\) algorithm for convex flip distance
• Shortest paths on polymatroids and hypergraphic polytopes
• Flips in odd matchings
• An \(\mathcal{O}(3.82^k)\) time \(\mathsf{FPT}\) algorithm for convex flip distance
• Hardness of finding combinatorial shortest paths on graph associahedra
• Computing distances on graph associahedra is fixed-parameter tractable
• Efficient lower and upper bounds of the diagonal-flip distance between triangulations
• Flip distance between two triangulations of a point set is NP-complete

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

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