Ordered theta graphs

DOI10.1016/j.comgeo.2004.01.003zbMath1081.68066OpenAlexW2165849228MaRDI QIDQ598550

Pat Morin, Prosenjit Bose, Joachim Gudmundsson

Publication date: 6 August 2004

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

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

zbMATH Keywords

Low degreeLow diameterSpannersTheta graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

On the Power of the Semi-Separated Pair Decomposition ⋮ Fast query structures in anisotropic media ⋮ Generalized sweeping line spanners ⋮ Generalized sweeping line spanners ⋮ Online Spanners in Metric Spaces ⋮ On the power of the semi-separated pair decomposition ⋮ An Optimal Dynamic Spanner for Doubling Metric Spaces ⋮ Local properties of geometric graphs ⋮ Geometric spanners with small chromatic number ⋮ Quickest path queries on transportation network ⋮ Kinetic spanners in \(\mathbb R^{d}\) ⋮ The Price of Order ⋮ The Price of Order ⋮ Fully dynamic geometric spanners

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multidimensional divide-and-conquer
• Dynamic fractional cascading
• Classes of graphs which approximate the complete Euclidean graph
• Dynamic algorithms for geometric spanners of small diameter: Randomized solutions