Transforming spanning trees: A lower bound

DOI10.1016/j.comgeo.2008.03.005zbMath1169.05314OpenAlexW2147388254MaRDI QIDQ1028225

Kevin Buchin, Andreas Razen, Uli Wagner, Takeaki Uno

Publication date: 30 June 2009

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

Full work available at URL: https://doi.org/10.1016/j.comgeo.2008.03.005

zbMATH Keywords

transformation graphscrossing-free geometric graphscompatible spanning trees

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

Compatible spanning trees in simple drawings of \(K_n\), Amortized efficiency of generating planar paths in convex position, Compatible geometric matchings, Transition operations over plane trees, Bichromatic compatible matchings

Cites Work

• A quadratic distance bound on sliding between crossing-free spanning trees
• Transforming spanning trees and pseudo-triangulations
• Geometric tree graphs of points in convex position
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• Graphs of non-crossing perfect matchings
• Reverse search for enumeration
• Graphs of triangulations and perfect matchings
• Compatible Geometric Matchings
• Sequences of spanning trees and a fixed tree theorem