Almost All Even Yao-Yao Graphs Are Spanners

It is an open problem whether Yao-Yao graphs $\mathsf{YY}_k$ (also known as sparse-Yao graphs) are all spanners when the integer parameter $k$ is large enough. In this paper we show that, for any integer $k\geq 42$, the Yao-Yao graph $\mathsf{YY}_{2k}$ is a $t_k$-spanner, with stretch factor $t_k=6.03+O(k^{-1})$ when $k$ tends to infinity. Our result generalizes the best known result which asserts that all $\mathsf{YY}_{6k}$ are spanners for $k$ large enough [Bauer and Damian, SODA'13]. Our proof is also somewhat simpler.

• Publication year

  2016

• Venue

  Embedded Systems and Applications

• Publication date

  2016-04-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.4230/LIPIcs.ESA.2016.62arXiv 1604.05814
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Continuous Yao Graphs

  2014cited by this paper
• On certain geometric properties of the Yao–Yao graphs

  2014cited by this paper
• New and Improved Spanning Ratios for Yao Graphs

  2013cited by this paper
• An Infinite Class of Sparse-Yao Spanners

  2012influential reference
• Yao Graphs Span Theta Graphs

  2010cited by this paper
• Wireless Ad-Hoc and Sensor Networks

  2010cited by this paper
• π/2-Angle Yao Graphs are Spanners

  2010cited by this paper
• Yao spanners for wireless ad hoc networks

  2009cited by this paper
• Wireless Ad Hoc and Sensor Networks: Theory and Applications

  2008cited by this paper
• On the Stretch Factor of Convex Delaunay Graphs

  2008cited by this paper
• A Simple Yao-Yao-Based Spanner of Bounded Degree

  2008influential reference
• Geometric spanners with applications in wireless networks

  2007cited by this paper
• Geometric spanner networks

  2007cited by this paper
• Wireless Ad Hoc And sensor netWorks

  2007cited by this paper
• Constructing Plane Spanners of Bounded Degree and Low Weight

  2005cited by this paper
• Efficient construction of low weighted bounded degree planar spanner

  2004cited by this paper
• On local algorithms for topology control and routing in ad hoc networks

  2003cited by this paper
• Efficient Construction of Low Weight Bounded Degree Planar Spanner

  2003cited by this paper
• Fault-Tolerant Geometric Spanners

  2003cited by this paper
• Sparse power efficient topology for wireless networks

  2002cited by this paper
• Constructing Plane Spanners of Bounded Degree and Low Weight

  2002cited by this paper
• Sparse Power EÆcient Topology for Wireless Networks

  2001influential reference
• Power efficient and sparse spanner for wireless ad hoc networks

  2001cited by this paper
• Graph Spanners: a Survey

  1992cited by this paper
• Graph spanners

  1989cited by this paper
• Delaunay graphs are almost as good as complete graphs

  1987cited by this paper
• There is a planar graph almost as good as the complete graph

  1986cited by this paper
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems

  1977cited by this paper

• Truly Optimal Euclidean Spanners

  2019cites this paper
• Spanning Properties of Theta–Theta-6

  2018cites this paper
• Odd Yao-Yao Graphs may Not be Spanners

  2017cites this paper
• Odd Yao-Yao Graphs are Not Spanners

  2017influential citation