×

Spanning properties of Theta-Theta-6. (English) Zbl 1439.05102

Summary: We show that, unlike the Yao-Yao graph \(YY_6\), the Theta-Theta graph \({\varTheta}{\varTheta}_6\) defined by six cones is a spanner for sets of points in convex position. We also show that, for sets of points in non-convex position, the spanning ratio of \({\varTheta}{\varTheta}_6\) is unbounded.

MSC:

05C22 Signed and weighted graphs
05C12 Distance in graphs
05C38 Paths and cycles
05C90 Applications of graph theory
05C82 Small world graphs, complex networks (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alzoubi, K.; Xiang-Yang Li, Y.; Wang, P-JW; Frieder, O., Geometric spanners for wireless ad hoc networks, IEEE Trans. Parallel Distrib. Syst., 14, 4, 408-421 (2003) · doi:10.1109/TPDS.2003.1195412
[2] Barba, L.; Bose, P.; Damian, M.; Fagerberg, R.; Keng, WL; O’Rourke, J.; van Renssen, A.; Taslakian, P.; Verdonschot, S.; Xia, G., New and improved spanning ratios for Yao graphs, J. Comput. Geom., 6, 2, 19-53 (2015) · Zbl 1395.68282
[3] Bonichon, N., Gavoille, C., Hanusse, N., Ilcinkas, D.: Connections between Theta-graphs, Delaunay triangulations, and orthogonal surfaces. In: Proceedings of the 36th international conference on graph-theoretic concepts in computer science, WG’10, pp. 266-278. Berlin, Heidelberg (2010). Springer-Verlag · Zbl 1309.68146
[4] Bose, P., Damian, M., Douïeb, K., O’Rourke, J., Seamone, B., Michiel S.H.M., Wuhrer, S.: \( \pi /2\)-angle Yao graphs are spanners (2010). CoRR, abs/1001.2913 · Zbl 1310.68156
[5] Bose, P., De Carufel, J.L., Hill, D., Smid, M.: On the spanning and routing ratio of Theta-four. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’19, pp. 2361-2370 (2019) · Zbl 1432.68588
[6] Bose, P.; De Carufel, J-L; Morin, P.; van Renssen, A.; Verdonschot, S., Towards tight bounds on Theta-graphs: More is not always better, Theoret. Comput. Sci., 616, C, 70-93 (2016) · Zbl 1334.68237 · doi:10.1016/j.tcs.2015.12.017
[7] Bose, P.; Morin, P.; van Renssen, A.; Verdonschot, S., The Theta-5 graph is a spanner. A preliminary version appeared in Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG’13), Comput. Geom. Theory Appl., 48, 2, 108-119 (2015) · Zbl 1307.05093 · doi:10.1016/j.comgeo.2014.08.005
[8] Chew, LP, There are planar graphs almost as good as the complete graph, J. Comput. Syst. Sci., 39, 2, 205-219 (1989) · Zbl 0682.05032 · doi:10.1016/0022-0000(89)90044-5
[9] Clarkson, K.L.: Approximation algorithms for shortest path motion planning. In: Proceedings of the 19th Annual ACM Conference on Theory of Computing, STOC’87, pp. 56-65 (1987)
[10] Damian, M., Cone-based spanners of constant degree, Computational Geometry Theory and Applications, 68, 48-61 (2018) · Zbl 1380.05117 · doi:10.1016/j.comgeo.2017.05.004
[11] Damian, M., Bauer, M.: An infinite class of sparse-Yao spanners. In: Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms, SODA’13, pp. 184-196, January 6-8 (2013) · Zbl 1422.68241
[12] Damian, M., Molla, N., Pinciu, V.: Spanner properties of \(\pi /2\)-angle Yao graphs. In: Proceedings of the 25th European Workshop on Computational Geometry, pp. 21-24 (2009)
[13] Damian, M.; Nelavalli, N., Improved bounds on the stretch factor of \({Y}_4\), Comput. Geom. Theory Appl., 62, C, 14-24 (2017) · Zbl 1365.05059 · doi:10.1016/j.comgeo.2016.12.001
[14] Eppstein, D.; Sack, J-R; Urrutia, J., Spanning trees and spanners, Handbook of Computational Geometry, 425-461 (2000), Amsterdam: Elsevier Science, Amsterdam · Zbl 0944.05021
[15] Fischer, M., Lukovszki, T., Ziegler, M.: Geometric searching in walkthrough animations with weak spanners in real time. In: ESA ’98: Proceedings of the 6th Annual European Symposium on Algorithms, pp. 163-174 (1998)
[16] Jin, Y., Li, J., Zhan, W.: Odd Yao-Yao graphs are not spanners. In: 34th International Symposium on Computational Geometry (SoCG’18), June 11-14, 2018, Budapest, Hungary, vol. 49, pp. 1-15 (2018) · Zbl 1468.68265
[17] Keil, J.M.: Approximating the complete Euclidean graph. In: Proceedings of the 1st Scandinavian Workshop on Algorithm Theory, number 318 in SWAT’88, pp. 208-213. Springer-Verlag, London, UK (1988) · Zbl 0655.68087
[18] Li, J., Zhan, W.: Almost all even Yao-Yao graphs are spanners. In: 24th Annual European Symposium on Algorithms ESA’16, vol. 62, pp. 1-13 (2016) · Zbl 1397.68204
[19] Li, X-Y, Wireless Ad Hoc and Sensor Networks: Theory and Applications (2008), New York, NY, USA: Cambridge University Press, New York, NY, USA
[20] Li, X.Y., Wan, P.J., Wang, Y., Frieder, O.: Sparse power efficient topology for wireless networks. In: HICSS’02: Proceedings of the 35th Annual Hawaii Int. Conference on System Sciences, vol. 9, p. 296.2, (2002)
[21] Molla, N.: Yao spanners for wireless ad hoc networks. Technical report, M.S. Thesis, Department of Computer Science, Villanova University (December 2009)
[22] Narasimhan, G.; Smid, M., Geometric Spanner Networks (2007), New York, NY, USA: Cambridge University Press, New York, NY, USA · Zbl 1140.68068
[23] Ruppert, J., Seidel, R.: Approximating the \(d\)-dimensional complete Euclidean graph. In: Proceedings of the 3rd Canadian Conference on Computational Geometry, CCCG’91, pp. 207-210 (1991)
[24] Yao, AC-C, On constructing minimum spanning trees in \(k\)-dimensional spaces and related problems, SIAM J. Comput., 11, 4, 721-736 (1982) · Zbl 0492.68050 · doi:10.1137/0211059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.