Odd Yao-Yao Graphs are Not Spanners

DOI10.4230/LIPIcs.SoCG.2018.49zbMath1468.68265arXiv1704.03132OpenAlexW2796251934MaRDI QIDQ5115817

Jian Li, Yifei Jin, Wei Zhan

Publication date: 18 August 2020

Full work available at URL: https://arxiv.org/abs/1704.03132

zbMATH Keywords

counterexamplespannerodd Yao-Yao graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distance in graphs (05C12)

Related Items (2)

Truly Optimal Euclidean Spanners ⋮ Spanning properties of Theta-Theta-6

Cites Work

• Unnamed Item
• Unnamed Item
• Geometric spanners with applications in wireless networks
• The relative neighbourhood graph of a finite planar set
• Beta-skeletons have unbounded dilation
• Approximating geometric bottleneck shortest paths
• The \(\varTheta_5\)-graph is a spanner
• Improved bounds on the stretch factor of \(Y_{4}\)
• On the Stretch Factor of the Theta-4 Graph
• On the Spanning Ratio of Theta-Graphs
• New and improved spanning ratios for Yao graphs
• Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
• Yao Graphs Span Theta Graphs
• On Certain Geometric Properties of the Yao-Yao Graphs
• Geometric Spanner Networks
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Strong Connectivity in Directional Nearest-Neighbor Graphs
• Almost All Even Yao-Yao Graphs Are Spanners
• π/2-ANGLE YAO GRAPHS ARE SPANNERS
• DISTRIBUTED SPANNERS WITH BOUNDED DEGREE FOR WIRELESS AD HOC NETWORKS
• Algorithms and Computation
• An Infinite Class of Sparse-Yao Spanners

This page was built for publication: Odd Yao-Yao Graphs are Not Spanners