Sequences of spanning trees and a fixed tree theorem

DOI10.1016/S0925-7721(01)00042-6zbMath0991.68122OpenAlexW2063600012MaRDI QIDQ5959551

Oswin Aichholzer, Ferran Hurtado, Franz Aurenhammer

Publication date: 3 September 2002

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

Full work available at URL: https://doi.org/10.1016/s0925-7721(01)00042-6

zbMATH Keywords

Euclidean minimum spanning tree

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical approximation and computational geometry (primarily algorithms) (65D99)

Related Items (15)

Reconstruction of the path graph ⋮ A quadratic distance bound on sliding between crossing-free spanning trees ⋮ Amortized efficiency of generating planar paths in convex position ⋮ Compatible spanning trees ⋮ Compatible geometric matchings ⋮ Fast enumeration algorithms for non-crossing geometric graphs ⋮ Gray code enumeration of plane straight-line graphs ⋮ Flips in planar graphs ⋮ Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees ⋮ Disjoint compatibility graph of non-crossing matchings of points in convex position ⋮ On the diameter of geometric path graphs of points in convex position ⋮ Transition operations over plane trees ⋮ Transforming spanning trees: A lower bound ⋮ Transforming spanning trees and pseudo-triangulations ⋮ Bichromatic compatible matchings

Uses Software

• Voronoi

Cites Work

• On the shortest spanning subtree of a graph and the traveling salesman problem
• Generalized Delaunay triangulation for planar graphs
• Constrained Delaunay triangulations
• Geometric tree graphs of points in convex position
• Distances between graphs under edge operations
• Ramsey-type results for geometric graphs. I
• Matching convex shapes with respect to the symmetric difference
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• On connectivities of tree graphs
• Crossing-Free Subgraphs
• Matching Shapes with a Reference Point
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• On the Tree Graph of a Matroid
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Sequences of spanning trees and a fixed tree theorem