{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T08:55:15Z","timestamp":1765961715079,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T00:00:00Z","timestamp":1696550400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T00:00:00Z","timestamp":1696550400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["Discovery Grant"],"award-info":[{"award-number":["Discovery Grant"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2024,4]]},"DOI":"10.1007\/s00454-023-00597-8","type":"journal-article","created":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T17:02:08Z","timestamp":1696611728000},"page":"872-892","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Spanning and Routing Ratio of the Directed Theta-Four Graph"],"prefix":"10.1007","volume":"71","author":[{"given":"Prosenjit","family":"Bose","sequence":"first","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Jean-Lou","family":"De Carufel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5210-7112","authenticated-orcid":false,"given":"Darryl","family":"Hill","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,10,6]]},"reference":[{"issue":"9","key":"597_CR1","doi-asserted-by":"publisher","first-page":"910","DOI":"10.1016\/j.comgeo.2014.05.001","volume":"47","author":"O Aichholzer","year":"2014","unstructured":"Aichholzer, O., Bae, S.W., Barba, L., Bose, P., Korman, M., Van Renssen, A., Taslakian, P., Verdonschot, S.: Theta-3 is connected. Comput. Geom. 47(9), 910\u2013917 (2014)","journal-title":"Comput. Geom."},{"key":"597_CR2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2022.101881","volume":"105\u2013106","author":"HA Akitaya","year":"2022","unstructured":"Akitaya, H.A., Biniaz, A., Bose, P.: On the spanning and routing ratios of the directed theta-6-graph. Comput. Geom. 105\u2013106, 101881 (2022)","journal-title":"Comput. Geom."},{"key":"597_CR3","doi-asserted-by":"crossref","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.) Algorithms and Data Structures\u201413th International Symposium, WADS 2013, London, ON, Canada, August 12\u201314, 2013. Proceedings, vol. 8037 of Lecture Notes in Computer Science, pp. 109\u2013120. Springer, New York (2013)","DOI":"10.1007\/978-3-642-40104-6_10"},{"key":"597_CR4","unstructured":"Bonichon, N., Bose, P., De Carufel, J.-L., Despr\u00e9, V., Hill, D., Smid, M.H.M.: Improved routing on the Delaunay triangulation. In: ESA, vol. 112 of LIPIcs, pp. 22:1\u201322:13. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik (2018)"},{"issue":"2","key":"597_CR5","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1007\/s00454-016-9842-y","volume":"58","author":"N Bonichon","year":"2017","unstructured":"Bonichon, N., Bose, P., De Carufel, J.-L., Perkovic, L., van Renssen, A.: Upper and lower bounds for online routing on Delaunay triangulations. Discret. Comput. Geom. 58(2), 482\u2013504 (2017)","journal-title":"Discret. Comput. Geom."},{"key":"597_CR6","doi-asserted-by":"crossref","unstructured":"Bonichon, N., Gavoille, C., Hanusse, N., Ilcinkas, D.: Connections between theta-graphs, Delaunay triangulations, and orthogonal surfaces. In: WG, vol. 6410 of Lecture Notes in Computer Science, pp. 266\u2013278 (2010)","DOI":"10.1007\/978-3-642-16926-7_25"},{"issue":"1","key":"597_CR7","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s00446-012-0179-3","volume":"26","author":"P Bose","year":"2013","unstructured":"Bose, P., Carmi, P., Durocher, S.: Bounding the locality of distributed routing algorithms. Distrib. Comput. 26(1), 39\u201358 (2013)","journal-title":"Distrib. Comput."},{"issue":"1","key":"597_CR8","first-page":"212","volume":"11","author":"P Bose","year":"2020","unstructured":"Bose, P., De Carufel, J.-L., Devillers, O.: Expected complexity of routing in theta-6 and half-theta-6 graphs. J. Comput. Geom. 11(1), 212\u2013234 (2020)","journal-title":"J. Comput. Geom."},{"key":"597_CR9","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.tcs.2015.12.017","volume":"616","author":"P Bose","year":"2016","unstructured":"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, 70\u201393 (2016)","journal-title":"Theoret. Comput. Sci."},{"issue":"6","key":"597_CR10","doi-asserted-by":"publisher","first-page":"1626","DOI":"10.1137\/140988103","volume":"44","author":"P Bose","year":"2015","unstructured":"Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S.: Optimal local routing on Delaunay triangulations defined by empty equilateral triangles. SIAM J. Comput. 44(6), 1626\u20131649 (2015)","journal-title":"SIAM J. Comput."},{"key":"597_CR11","doi-asserted-by":"crossref","unstructured":"Bose, P., Hill, D., Ooms, A.: Improved bounds on the spanning ratio of the theta-5-graph. In: Lubiw, A., Salavatipour, M.R. (eds.) Algorithms and Data Structures\u201417th International Symposium, WADS 2021, Virtual Event, August 9-11, 2021, Proceedings, vol. 12808 of Lecture Notes in Computer Science, pp. 215\u2013228. Springer, New York (2021)","DOI":"10.1007\/978-3-030-83508-8_16"},{"issue":"2\u20133","key":"597_CR12","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.tcs.2004.05.019","volume":"324","author":"P Bose","year":"2004","unstructured":"Bose, P., Morin, P.: Competitive online routing in geometric graphs. Theoret. Comput. Sci. 324(2\u20133), 273\u2013288 (2004)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"597_CR13","doi-asserted-by":"publisher","first-page":"937","DOI":"10.1137\/S0097539700369387","volume":"33","author":"P Bose","year":"2004","unstructured":"Bose, P., Morin, P.: Online routing in triangulations. SIAM J. Comput. 33(4), 937\u2013951 (2004)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"597_CR14","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/j.comgeo.2014.08.005","volume":"48","author":"P Bose","year":"2015","unstructured":"Bose, P., Morin, P., van Renssen, A., Verdonschot, S.: The theta-5-graph is a spanner. Comput. Geom. 48(2), 108\u2013119 (2015)","journal-title":"Comput. Geom."},{"issue":"1","key":"597_CR15","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1002\/rsa.20630","volume":"49","author":"N Broutin","year":"2016","unstructured":"Broutin, N., Devillers, O., Hemsley, R.: Efficiently navigating a random Delaunay triangulation. Random Struct. Algorithms 49(1), 95\u2013136 (2016)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"597_CR16","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/j.comgeo.2011.12.005","volume":"45","author":"D Chen","year":"2012","unstructured":"Chen, D., Devroye, L., Dujmovic, V., Morin, P.: Memoryless routing in convex subdivisions: random walks are optimal. Comput. Geom. 45(4), 178\u2013185 (2012)","journal-title":"Comput. Geom."},{"key":"597_CR17","doi-asserted-by":"crossref","unstructured":"Chew, P.: There is a planar graph almost as good as the complete graph. In: Symposium on Computational Geometry, pp. 169\u2013177. ACM (1986)","DOI":"10.1145\/10515.10534"},{"issue":"2","key":"597_CR18","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0022-0000(89)90044-5","volume":"39","author":"P Chew","year":"1989","unstructured":"Chew, 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":"597_CR19","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L.: Approximation algorithms for shortest path motion planning. In: STOC, pp. 56\u201365. ACM (1987)","DOI":"10.1145\/28395.28402"},{"key":"597_CR20","unstructured":"El Molla, N.M.: Yao spanners for wireless ad-hoc networks. Master\u2019s thesis, Villanova University, Pennsylvania (2009)"},{"key":"597_CR21","unstructured":"Keil, J.M.: Approximating the complete Eclidean graph. In: Karlsson, R.G., Lingas, A. (eds.) SWAT 88, 1st Scandinavian Workshop on Algorithm Theory, Halmstad, Sweden, July 5\u20138, 1988, Proceedings, vol. 318 of Lecture Notes in Computer Science, pp. 208\u2013213. Springer, New York (1988)"},{"issue":"1","key":"597_CR22","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF02187821","volume":"7","author":"JM Keil","year":"1992","unstructured":"Keil, J.M., Gutwin, C.A.: Classes of graphs which approximate the complete Eclidean graph. Discret. Comput. Geom. 7(1), 13\u201328 (1992)","journal-title":"Discret. Comput. Geom."},{"key":"597_CR23","unstructured":"Kranakis, E., Singh, H., Urrutia, J.: Compass routing on geometric networks. In: Proceedings of the 11th Canadian Conference on Computational Geometry, UBC, Vancouver, British Columbia, Canada, August 15\u201318 (1999)"},{"key":"597_CR24","doi-asserted-by":"crossref","unstructured":"Ruhrup, S.: Theory and practice of geographic routing. Chapter 5 in Ad Hoc and Sensor Wireless Networks: Architectures, Algorithms and Protocols (2009)","DOI":"10.2174\/978160805018510901010069"},{"key":"597_CR25","unstructured":"Ruppert, J., Seidel, R.: Approximating the d-dimensional complete Euclidean graph. In: Proceedings of the 3rd Canadian Conference on Computational Geometry, Simon Fraser University, Vancouver, British Columbia, Canada, August 6\u201310 (1991)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00597-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00597-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00597-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T15:12:16Z","timestamp":1710169936000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00597-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,6]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["597"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00597-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2023,10,6]]},"assertion":[{"value":"16 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 September 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 September 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 October 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}