A quadratic distance bound on sliding between crossing-free spanning trees

DOI10.1016/j.comgeo.2004.12.010zbMath1115.68154OpenAlexW1993940507MaRDI QIDQ883234

Klaus Reinhardt, Oswin Aichholzer

Publication date: 4 June 2007

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

Full work available at URL: https://idus.us.es/xmlui/handle/11441/54977

zbMATH Keywords

transformationflipscrossing free spanning treesedge slides

Mathematics Subject Classification ID

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

Related Items (12)

Reconstruction of the path graph ⋮ The edge rotation graph ⋮ Amortized efficiency of generating planar paths in convex position ⋮ Fast enumeration algorithms for non-crossing geometric graphs ⋮ Flips in planar graphs ⋮ Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees ⋮ On the diameter of geometric path graphs of points in convex position ⋮ Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees ⋮ Transition operations over plane trees ⋮ Transforming spanning trees: A lower bound ⋮ Reconstruction of the Crossing Type of a Point Set from the Compatible Exchange Graph of Noncrossing Spanning Trees ⋮ Transforming spanning trees and pseudo-triangulations

Cites Work

• Unnamed Item
• Unnamed Item
• Distances between graphs under edge operations
• Sequences of spanning trees and a fixed tree theorem

This page was built for publication: A quadratic distance bound on sliding between crossing-free spanning trees