Odd Yao-Yao graphs are not spanners

DOI10.4230/LIPICS.SOCG.2018.49zbMATH Open1468.68265arXiv1704.03132OpenAlexW2796251934MaRDI QIDQ5115817FDOQ5115817

Jian Li, Yifei Jin, Wei Zhan

Publication date: 18 August 2020

Abstract: It is a long standing open problem whether Yao-Yao graphs $mathsf{YY}_k$ are all spanners [li2002sparse]. Bauer and Damian [bauer2013infinite] showed that all $mathsf{YY}_{6k}$ for $kgeq6$ are spanners. Li and Zhan [li2016almost] generalized their result and proved that all even Yao-Yao graphs $mathsf{YY}_{2k}$ are spanners (for $kgeq42$). However, their technique cannot be extended to odd Yao-Yao graphs, and whether they are spanners are still elusive. In this paper, we show that, surprisingly, for any integer $kgeq1$, there exist odd Yao-Yao graph $mathsf{YY}_{2k+1}$ instances, which are not spanners.

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

Recommendations

• Almost All Even Yao-Yao Graphs Are Spanners
• On certain geometric properties of the Yao-Yao graphs
• On certain geometric properties of the Yao-Yao graphs
• New and improved spanning ratios for Yao graphs
• New and improved spanning ratios for Yao graphs

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)

Cites Work

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

Cited In (3)

• Almost All Even Yao-Yao Graphs Are Spanners
• Spanning properties of Theta-Theta-6
• Truly Optimal Euclidean Spanners

This page was built for publication: Odd Yao-Yao graphs are not spanners

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