Constrained flips in plane spanning trees

DOI10.4230/LIPICS.GD.2025.5MaRDI QIDQ7354795zbMATH OpenFDO

Authors Oswin Aichholzer, Joseph Dorfer, Birgit Vogtenhuber

Publication date 21 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.GD.2025.5

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• A note on the flip distance between non-crossing spanning trees
• A quadratic distance bound on sliding between crossing-free spanning trees
• An improved kernel for the flip distance problem on simple convex polygons
• An improved kernel size for rotation distance in binary trees
• Flip distance between triangulations of a planar point set is APX-hard
• Flip distance between triangulations of a simple polygon is NP-complete
• Flip distance between two triangulations of a point set is NP-complete
• Flipping non-crossing spanning trees
• Geometric tree graphs of points in convex position
• Graphs of non-crossing perfect matchings
• Reconfiguration of non-crossing spanning trees
• Reconfiguration of plane trees in convex geometric graphs
• Reverse search for enumeration
• Rotation distance is fixed-parameter tractable
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• Transition operations over plane trees

This page was built for publication: Constrained flips in plane spanning trees

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