Ordered theta graphs

DOI10.1016/J.COMGEO.2004.01.003MaRDI QIDQ598550zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, Joachim Gudmundsson, Pat Morin

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)

Recommendations

• The price of order
• The price of order
• The \(\theta_5\)-graph is a spanner
• On the spanning ratio of theta-graphs
• Towards tight bounds on theta-graphs: more is not always better

Cites work

• scientific article; zbMATH DE number 2185613 (Why is no real title available?)
• scientific article; zbMATH DE number 4070353 (Why is no real title available?)
• scientific article; zbMATH DE number 1263225 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• Classes of graphs which approximate the complete Euclidean graph
• Dynamic algorithms for geometric spanners of small diameter: Randomized solutions
• Dynamic fractional cascading
• Multidimensional divide-and-conquer

Cited in

(15)

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

This page was built for publication: Ordered theta graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q598550)