Transforming spanning trees and pseudo-triangulations

DOI10.1016/j.ipl.2005.09.003zbMath1191.68457OpenAlexW2089255329WikidataQ61732496 ScholiaQ61732496MaRDI QIDQ1044747

Clemens Huemer, Hannes Krasser, Franz Aurenhammer, Oswin Aichholzer

Publication date: 18 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.09.003

zbMATH Keywords

computational geometryspanning treespseudo-triangulationsflipping distance

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (9)

Compatible spanning trees in simple drawings of \(K_n\) ⋮ Amortized efficiency of generating planar paths in convex position ⋮ Compatible geometric matchings ⋮ Fast enumeration algorithms for non-crossing geometric graphs ⋮ Flips in edge-labelled pseudo-triangulations ⋮ Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees ⋮ Transition operations over plane trees ⋮ Transforming spanning trees: A lower bound ⋮ Bichromatic compatible matchings

Cites Work

• A quadratic distance bound on sliding between crossing-free spanning trees
• Flipping edges in triangulations
• Reverse search for enumeration
• Transforming pseudo-triangulations
• Pseudotriangulations from Surfaces and a Novel Type of Edge Flip
• Algorithms and Data Structures
• Sequences of spanning trees and a fixed tree theorem

This page was built for publication: Transforming spanning trees and pseudo-triangulations