Improved bounds on the spanning ratio of the theta-5-graph

DOI10.1007/978-3-030-83508-8_16OpenAlexW3193265284MaRDI QIDQ832862

Darryl Hill, Aurélien Ooms, Prosenjit Bose

Publication date: 25 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-83508-8_16

zbMATH Keywords

geometric spannerstheta graphsstretch factorspanning ratio

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Data structures (68P05)

Related Items (6)

On the spanning and routing ratios of the directed \(\Theta_6\)-graph ⋮ Generalized sweeping line spanners ⋮ On the spanning and routing ratio of the directed theta-four graph ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ Generalized sweeping line spanners ⋮ Emanation graph: a plane geometric spanner with Steiner points

Cites Work

• Unnamed Item
• Theta-3 is connected
• Towards tight bounds on theta-graphs: more is not always better
• Classes of graphs which approximate the complete Euclidean graph
• There are planar graphs almost as good as the complete graph
• The \(\varTheta_5\)-graph is a spanner
• On the Stretch Factor of the Theta-4 Graph
• On the Spanning and Routing Ratio of Theta-Four

This page was built for publication: Improved bounds on the spanning ratio of the theta-5-graph