Sequences of spanning trees and a fixed tree theorem

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

Oswin Aichholzer, Franz Aurenhammer, Ferran Hurtado

Publication date: 3 September 2002

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

zbMATH Keywords

Euclidean minimum spanning tree

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

65D99: Numerical approximation and computational geometry (primarily algorithms)

Related Items

Fast enumeration algorithms for non-crossing geometric graphs, Amortized efficiency of generating planar paths in convex position, A quadratic distance bound on sliding between crossing-free spanning trees, Compatible geometric matchings, 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, Transforming spanning trees: A lower bound, Transforming spanning trees and pseudo-triangulations, Gray code enumeration of plane straight-line graphs

Uses Software

• Voronoi

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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