Odd Yao-Yao graphs are not spanners

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

Authors Yifei Jin, Jian Li, 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)

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.

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

Cites work

• scientific article; zbMATH DE number 2090692 (Why is no real title available?)
• scientific article; zbMATH DE number 1424297 (Why is no real title available?)
• Algorithms and Computation
• Almost All Even Yao-Yao Graphs Are Spanners
• An infinite class of Sparse-Yao spanners
• Approximating geometric bottleneck shortest paths
• Beta-skeletons have unbounded dilation
• Connections between Theta-graphs, Delaunay triangulations, and orthogonal surfaces
• DISTRIBUTED SPANNERS WITH BOUNDED DEGREE FOR WIRELESS AD HOC NETWORKS
• Geometric Spanner Networks
• Geometric spanners with applications in wireless networks
• Improved bounds on the stretch factor of \(Y_{4}\)
• New and improved spanning ratios for Yao graphs
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• On certain geometric properties of the Yao-Yao graphs
• On the spanning ratio of theta-graphs
• On the stretch factor of the theta-4 graph
• Strong Connectivity in Directional Nearest-Neighbor Graphs
• The \(\varTheta_5\)-graph is a spanner
• The relative neighbourhood graph of a finite planar set
• Yao Graphs Span Theta Graphs
• \(\pi /2\)-angle Xao graphs are spanners

Cited in

(5)

• On certain geometric properties of the Yao-Yao graphs
• Spanning properties of Theta-Theta-6
• On certain geometric properties of the Yao-Yao graphs
• Almost All Even Yao-Yao Graphs Are Spanners
• 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)