Computing the flip distance between triangulations
From MaRDI portal
Publication:2408209
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
Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Related Items (14)
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 ⋮ 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
