{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:27:25Z","timestamp":1760441245858,"version":"3.40.5"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319126906"},{"type":"electronic","value":"9783319126913"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-12691-3_17","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T21:11:32Z","timestamp":1415999492000},"page":"216-230","source":"Crossref","is-referenced-by-count":1,"title":["Spanning Properties of Theta-Theta Graphs"],"prefix":"10.1007","author":[{"given":"Mirela","family":"Damian","sequence":"first","affiliation":[]},{"given":"Dumitru V.","family":"Voicu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,13]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"Arya, S., Das, G., Mount, D.M., Salowe, J.S., Smid, M.: Euclidean spanners: short, thin, and lanky. In: STOC \u201995: Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pp. 489\u2013498. ACM, New York (1995)","DOI":"10.1145\/225058.225191"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Barba, L., Bose, P., Damian, M., Fagerberg, R., Keng, W.L., O\u2019Rourke, J., van Renssen, A., Taslakian, P., Verdonschot, S., Xia, G.: New and improved spanning ratios for Yao graphs. In: Proceedings of the 30th Annual Symposium on Computational Geometry, SOCG\u201914, pp. 30\u201339. ACM, New York (2014)","DOI":"10.1145\/2582112.2582143"},{"key":"17_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/978-3-642-40104-6_10","volume-title":"Algorithms and Data Structures","author":"L Barba","year":"2013","unstructured":"Barba, L., Bose, P., De Carufel, J.-L., van Renssen, A., Verdonschot, S.: On the stretch factor of the Theta-4 graph. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol. 8037, pp. 109\u2013120. Springer, Heidelberg (2013)"},{"key":"17_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/978-3-642-16926-7_25","volume-title":"Graph Theoretic Concepts in Computer Science","author":"N Bonichon","year":"2010","unstructured":"Bonichon, N., Gavoille, C., Hanusse, N., Ilcinkas, D.: Connections between Theta-graphs, Delaunay triangulations, and orthogonal surfaces. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol. 6410, pp. 266\u2013278. Springer, Heidelberg (2010)"},{"key":"17_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/978-3-642-14165-2_3","volume-title":"Automata, Languages and Programming","author":"N Bonichon","year":"2010","unstructured":"Bonichon, N., Gavoille, C., Hanusse, N., Perkovi\u0107, L.: Plane spanners of maximum degree six. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 19\u201330. Springer, Heidelberg (2010)"},{"issue":"2","key":"17_CR6","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.comgeo.2012.07.001","volume":"46","author":"P Bose","year":"2013","unstructured":"Bose, P., Carmi, P., Chaitman, L., Collette, S., Katz, M.J., Langerman, S.: Stable roommates spanner. Comput. Geom. Theory Appl. 46(2), 120\u2013130 (2013). (Special issue of selected papers from the 22nd Canadian Conference on Computational Geometry, CCCG\u201910)","journal-title":"Comput. Geom. Theory Appl."},{"key":"17_CR7","unstructured":"Bose, P., De Carufel, J.-L., Morin, P., van Renssen, A., Verdonschot, S.: Towards tight bounds on Theta-graphs. CoRR abs\/1404.6233 (2014)"},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"Bose, P., Damian, M., Dou\u00efeb, K., O\u2019Rourke, J., Seamone, B., Smid, M.H.M., Wuhrer, S.: Pi\/2-angle Yao graphs are spanners. CoRR, abs\/1001.2913 (2010)","DOI":"10.1007\/978-3-642-17514-5_38"},{"issue":"1","key":"17_CR9","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1142\/S0218195912600047","volume":"22","author":"P Bose","year":"2012","unstructured":"Bose, P., Damian, M., Dou\u00efeb, K., O\u2019Rourke, J., Seamone, B., Smid, M.H.M., Wuhrer, S.: Pi\/2-angle Yao graphs are spanners. Int. J. Comput. Geom. Appl. 22(1), 61\u201382 (2012)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"1","key":"17_CR10","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.comgeo.2004.01.003","volume":"28","author":"P Bose","year":"2004","unstructured":"Bose, P., Gudmundsson, J., Morin, P.: Ordered Theta graphs. Comput. Geom. Theory Appl. 28(1), 11\u201318 (2004)","journal-title":"Comput. Geom. Theory Appl."},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"Bose, P., Morin, P., van Renssen, A., Verdonschot, S.: The Theta-5 graph is a spanner. CoRR abs\/1212.0570 (2014) (To appear in Computational Geometry: Theory and Applications)","DOI":"10.1016\/j.comgeo.2014.08.005"},{"key":"17_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-642-40104-6_16","volume-title":"Algorithms and Data Structures","author":"P Bose","year":"2013","unstructured":"Bose, P., van Renssen, A., Verdonschot, S.: On the spanning ratio of Theta-graphs. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol. 8037, pp. 182\u2013194. Springer, Heidelberg (2013)"},{"issue":"2","key":"17_CR13","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0022-0000(89)90044-5","volume":"39","author":"LP Chew","year":"1989","unstructured":"Chew, L.P.: There are planar graphs almost as good as the complete graph. J. Comput. Syst. Sci. 39(2), 205\u2013219 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L.: Approximation algorithms for shortest path motion planning. In: Proceedings of the 19th Annual ACM Conference on Theory of Computing, STOC\u201987, pp. 56\u201365 (1987)","DOI":"10.1145\/28395.28402"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"Cowen, L.J., Wagner, C.G.: Compact roundtrip routing in directed networks (extended abstract). In: Proceedings of the 19th Annual ACM Symposium on Principles of Distributed Computing, PODC \u201900, pp. 51\u201359. ACM, New York (2000)","DOI":"10.1145\/343477.343516"},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"Damian, M., Bauer, M.: An infinite class of sparse-Yao spanners. In: Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms, SODA\u201913, pp. 184\u2013196, 6\u20138 January 2013","DOI":"10.1137\/1.9781611973105.14"},{"key":"17_CR17","unstructured":"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\u201324, March 2009"},{"issue":"2","key":"17_CR18","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1142\/S1793830912500243","volume":"4","author":"M Damian","year":"2012","unstructured":"Damian, M., Raudonis, K.: Yao graphs span Theta graphs. Discret. Math. Algorithms Appl. 4(2), 181\u2013194 (2012)","journal-title":"Discret. Math. Algorithms Appl."},{"key":"17_CR19","doi-asserted-by":"crossref","unstructured":"Damian, M., Voicu, D.M.: Spanning properties of theta-theta graphs. CoRR abs\/1407.3507 (2014)","DOI":"10.1007\/978-3-319-12691-3_17"},{"key":"17_CR20","unstructured":"Hamdaoui, B., Ramanathan, P.: Energy efficient and MAC-aware routing for data aggregation in sensor networks. Sensor Network Operations, pp. 291\u2013308 (2006)"},{"issue":"4","key":"17_CR21","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1109\/TMC.2008.132","volume":"8","author":"IA Kanj","year":"2009","unstructured":"Kanj, I.A., Perkovic, L., Xia, G.: Local construction of near-optimal power spanners for wireless ad hoc networks. IEEE Trans. Mob. Comput. 8(4), 460\u2013474 (2009)","journal-title":"IEEE Trans. Mob. Comput."},{"key":"17_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1007\/3-540-19487-8_23","volume-title":"SWAT\u201988","author":"JM Keil","year":"1988","unstructured":"Keil, J.M.: Approximating the complete Euclidean graph. In: Karlsson, R., Lingas, A. (eds.) SWAT\u201988. LNCS, vol. 318, pp. 208\u2013213. Springer, Heidelberg (1988)"},{"key":"17_CR23","unstructured":"Keng, W.L., Xia, G.: The Yao graph $$y_5$$ is a spanner. CoRR abs\/1307.5030 (2013)"},{"key":"17_CR24","unstructured":"Li, M., Wan, P.-J., Wang, Y.: Power efficient and sparse spanner for wireless ad hoc networks. In: Proceedings of the 10th International Conference on Computer Communications and Networks, pp. 564\u2013567 (2001)"},{"key":"17_CR25","unstructured":"Molla, N.: Yao spanners for wireless ad hoc networks. Technical report, M.S. Thesis, Department of Computer Science, Villanova University, December 2009"},{"issue":"3","key":"17_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1367064.1367069","volume":"4","author":"I Roditty","year":"2008","unstructured":"Roditty, I., Thorup, M., Zwick, U.: Roundtrip spanners and roundtrip routing in directed graphs. ACM Trans. Algorithms 4(3), 1\u201317 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"17_CR27","unstructured":"Ruppert, J., Seidel, R.: Approximating the $$d$$ -dimensional complete Euclidean graph. In: Proceedings of the 3rd Canadian Conference on Computational Geometry, CCCG\u201991, pp. 207\u2013210 (1991)"},{"key":"17_CR28","unstructured":"Scheideler, C.: Overlay networks for wireless systems. New Topics in Theoretical Computer Science, pp. 213\u2013251 (2008)"},{"key":"17_CR29","doi-asserted-by":"crossref","unstructured":"Song, W.-Z., Wang, Y., Li, X.-Y., Frieder, O.: Localized algorithms for energy efficient topology in wireless ad hoc networks. In: Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc\u201904, pp. 98\u2013108. ACM, New York (2004)","DOI":"10.1145\/989459.989473"},{"issue":"2","key":"17_CR30","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1142\/S0129054103001674","volume":"14","author":"Y Wang","year":"2003","unstructured":"Wang, Y., Li, X.-Y., Frieder, O.: Distributed spanners with bounded degree for wireless ad hoc networks. Int. J. Found. Comput. Sci. 14(2), 183\u2013200 (2003)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"4","key":"17_CR31","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1137\/0211059","volume":"11","author":"AC-C Yao","year":"1982","unstructured":"Yao, A.C.-C.: On constructing minimum spanning trees in $$k$$ -dimensional spaces and related problems. SIAM J. Comput. 11(4), 721\u2013736 (1982)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-12691-3_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T18:26:01Z","timestamp":1747160761000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-12691-3_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319126906","9783319126913"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-12691-3_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}