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

DOI10.1016/J.COMGEO.2004.12.010MaRDI QIDQ883234zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Sequences of spanning trees and a fixed tree theorem
• Transforming spanning trees: A lower bound
• Transforming spanning trees and pseudo-triangulations

Cites work

• scientific article; zbMATH DE number 1696622 (Why is no real title available?)
• scientific article; zbMATH DE number 1418487 (Why is no real title available?)
• Distances between graphs under edge operations
• Sequences of spanning trees and a fixed tree theorem

Cited in

(13)

• Reconstruction of the path graph
• Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees
• Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees
• A note on the flip distance between non-crossing spanning trees
• Amortized efficiency of generating planar paths in convex position
• Fast enumeration algorithms for non-crossing geometric 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
• Transforming spanning trees: A lower bound
• Transforming spanning trees and pseudo-triangulations
• Reconfiguration of non-crossing spanning trees
• The edge rotation graph
• Flips in planar graphs

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

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