{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:52Z","timestamp":1740109312414,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,1,25]],"date-time":"2022-01-25T00:00:00Z","timestamp":1643068800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,25]],"date-time":"2022-01-25T00:00:00Z","timestamp":1643068800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["DP150101134","DP180102870"],"award-info":[{"award-number":["DP150101134","DP180102870"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004359","name":"Swedish Research Council","doi-asserted-by":"crossref","award":["2017-03750","2018-04001"],"award-info":[{"award-number":["2017-03750","2018-04001"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no <jats:italic>O<\/jats:italic>(1)-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin (SIAM J Comput 33(4):937\u2013951, 2004) showed that there exists an online routing algorithm that is <jats:italic>O<\/jats:italic>(1)-competitive. However, a Delaunay triangulation can have <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varOmega (n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set <jats:italic>V<\/jats:italic> of <jats:italic>n<\/jats:italic> points in the Euclidean plane, of a planar geometric graph on <jats:italic>V<\/jats:italic> that has small weight (within a constant factor of the weight of a minimum spanning tree on <jats:italic>V<\/jats:italic>), constant degree, and that admits a local routing strategy that is <jats:italic>O<\/jats:italic>(1)-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an <jats:italic>O<\/jats:italic>(1)-competitive routing strategy.<\/jats:p>","DOI":"10.1007\/s00453-022-00930-2","type":"journal-article","created":{"date-parts":[[2022,1,25]],"date-time":"2022-01-25T06:02:26Z","timestamp":1643090546000},"page":"1316-1340","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Local Routing in Sparse and Lightweight Geometric Graphs"],"prefix":"10.1007","volume":"84","author":[{"given":"Vikrant","family":"Ashvinkumar","sequence":"first","affiliation":[]},{"given":"Joachim","family":"Gudmundsson","sequence":"additional","affiliation":[]},{"given":"Christos","family":"Levcopoulos","sequence":"additional","affiliation":[]},{"given":"Bengt J.","family":"Nilsson","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9294-9947","authenticated-orcid":false,"given":"Andr\u00e9 van","family":"Renssen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,25]]},"reference":[{"key":"930_CR1","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D.P., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete Comput. Geom. 9, 81\u2013100 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"930_CR2","doi-asserted-by":"publisher","first-page":"19","DOI":"10.7155\/jgaa.00197","volume":"14","author":"P Angelini","year":"2010","unstructured":"Angelini, P., Frati, F., Grilli, L.: An algorithm to construct greedy drawings of triangulations. J. Graph Algorithms Appl. 14(1), 19\u201351 (2010)","journal-title":"J. Graph Algorithms Appl."},{"key":"930_CR3","unstructured":"Ashvinkumar, V., Gudmundsson, J., Levcopoulos, C., Nilsson, B.J., van Renssen, A.: Local routing in sparse and lightweight geometric graphs. In: Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC 2019), Leibniz International Proceedings in Informatics (LIPIcs), vol. 149, pp. 33:1\u201333:13 (2019)"},{"key":"930_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"MD Berg","year":"2008","unstructured":"Berg, M.D., Cheong, O., Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer, Berlin (2008)"},{"issue":"1","key":"930_CR5","first-page":"11","volume":"8","author":"A Biniaz","year":"2017","unstructured":"Biniaz, A., Bose, P., Carufel, J.D., Gavoille, C., Maheshwari, A., Smid, M.H.M.: Towards plane spanners of degree 3. J. Comput. Geom. 8(1), 11\u201331 (2017)","journal-title":"J. Comput. Geom."},{"key":"930_CR6","doi-asserted-by":"crossref","unstructured":"Bonichon, N., Bose, P., Carmi, P., Kostitsyna, I., Lubiw, A., Verdonschot, S.: Gabriel triangulations and angle-monotone graphs: local routing and recognition. In: International Symposium on Graph Drawing and Network Visualization (GD), Lecture Notes in Computer Science (LNCS), vol. 9801, pp. 519\u2013531 (2016)","DOI":"10.1007\/978-3-319-50106-2_40"},{"key":"930_CR7","unstructured":"Bonichon, N., Bose, P., De Carufel, J., Despr\u00e9, V., Hill, D., Smid, M.: Improved routing on the delaunay triangulation. In: Proceedings of the 26th Annual European Symposium on Algorithms (ESA), Leibniz International Proceedings in Informatics (LIPIcs), vol. 112, pp. 22:1\u201322:13 (2018)"},{"issue":"2","key":"930_CR8","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., Perkovi\u0107, L., Van Renssen, A.: Upper and lower bounds for online routing on Delaunay triangulations. Discrete Comput.l Geom. 58(2), 482\u2013504 (2017)","journal-title":"Discrete Comput.l Geom."},{"issue":"3","key":"930_CR9","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1007\/s00454-015-9676-z","volume":"53","author":"N Bonichon","year":"2015","unstructured":"Bonichon, N., Kanj, I., Perkovi\u0107, L., Xia, G.: There are plane spanners of degree 4 and moderate stretch factor. Discrete Comput. Geom. 53(3), 514\u2013546 (2015)","journal-title":"Discrete Comput. Geom."},{"key":"930_CR10","doi-asserted-by":"crossref","unstructured":"Borradaile, G., Le, H., Wulff-Nilsen, C.: Greedy spanners are optimal in doubling metrics. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2371\u20132379. SIAM (2019)","DOI":"10.1137\/1.9781611975482.145"},{"issue":"6","key":"930_CR11","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."},{"issue":"4","key":"930_CR12","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."},{"key":"930_CR13","unstructured":"Callahan, P.B., Kosaraju, S.R.: Faster algorithms for some geometric graph problems in higher dimensions. In: Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 291\u2013300 (1993)"},{"key":"930_CR14","doi-asserted-by":"crossref","unstructured":"Das, G., Heffernan, P.J., Narasimhan, G.: Optimally sparse spanners in 3-dimensional Euclidean space. In: Proceedings of the 9th Symposium on Computational Geometry, pp. 53\u201362. ACM (1993)","DOI":"10.1145\/160985.160998"},{"key":"930_CR15","unstructured":"Das, G., Narasimhan, G., Salowe, J.S.: A new way to weigh malnourished Euclidean graphs. In: Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 215\u2013222. ACM-SIAM (1995)"},{"issue":"2","key":"930_CR16","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s00454-009-9235-6","volume":"43","author":"R Dhandapani","year":"2010","unstructured":"Dhandapani, R.: Greedy drawings of triangulations. Discrete Comput. Geom. 43(2), 375\u2013392 (2010)","journal-title":"Discrete Comput. Geom."},{"key":"930_CR17","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1, 269\u2013271 (1959)","journal-title":"Numer. Math."},{"key":"930_CR18","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/BF02187801","volume":"5","author":"DP Dobkin","year":"1990","unstructured":"Dobkin, D.P., Friedman, S.J., Supowit, K.J.: Delaunay graphs are almost as good as complete graphs. Discrete Comput. Geom. 5, 399\u2013407 (1990)","journal-title":"Discrete Comput. Geom."},{"issue":"02","key":"930_CR19","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1142\/S0218195916500059","volume":"26","author":"A Dumitrescu","year":"2016","unstructured":"Dumitrescu, A., Ghosh, A.: Lower bounds on the dilation of plane spanners. Int. J. Comput. Geom. Appl. 26(02), 89\u2013110 (2016)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"2","key":"930_CR20","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1137\/18M1210678","volume":"49","author":"A Filtser","year":"2020","unstructured":"Filtser, A., Solomon, S.: The greedy spanner is existentially optimal. SIAM J. Comput. 49(2), 429\u2013447 (2020)","journal-title":"SIAM J. Comput."},{"key":"930_CR21","doi-asserted-by":"crossref","unstructured":"Gottlieb, L.: A light metric spanner. In: IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 759\u2013772. IEEE (2015)","DOI":"10.1109\/FOCS.2015.52"},{"issue":"2","key":"930_CR22","first-page":"3","volume":"8","author":"IA Kanj","year":"2017","unstructured":"Kanj, I.A., Perkovic, L., T\u00fcrkoglu, D.: Degree four plane spanners: simpler and better. J. Comput. Geom. 8(2), 3\u201331 (2017)","journal-title":"J. Comput. Geom."},{"issue":"1\u20136","key":"930_CR23","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01758846","volume":"8","author":"C Levcopoulos","year":"1992","unstructured":"Levcopoulos, C., Lingas, A.: There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees. Algorithmica 8(1\u20136), 251\u2013256 (1992)","journal-title":"Algorithmica"},{"key":"930_CR24","doi-asserted-by":"crossref","unstructured":"Li, X.Y., Wang, Y.: Efficient construction of low weight bounded degree planar spanner. In: Proceedings of the 9th Annual International Computing and Combinatorics Conference (COCOON), Lecture Notes in Computer Science (LNCS), vol. 2697, pp. 374\u2013384 (2003)","DOI":"10.1007\/3-540-45071-8_38"},{"key":"930_CR25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884","volume-title":"Geometric Spanner Networks","author":"G Narasimhan","year":"2007","unstructured":"Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007)"},{"issue":"4","key":"930_CR26","doi-asserted-by":"publisher","first-page":"1620","DOI":"10.1137\/110832458","volume":"42","author":"G Xia","year":"2013","unstructured":"Xia, G.: The stretch factor of the Delaunay triangulation is less than 1.998. SIAM J. Comput. 42(4), 1620\u20131659 (2013)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00930-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00930-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00930-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,28]],"date-time":"2022-04-28T05:04:00Z","timestamp":1651122240000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00930-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,25]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["930"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00930-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,1,25]]},"assertion":[{"value":"4 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}