{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T15:57:43Z","timestamp":1770047863995,"version":"3.49.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,12,11]],"date-time":"2025-12-11T00:00:00Z","timestamp":1765411200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,12,11]],"date-time":"2025-12-11T00:00:00Z","timestamp":1765411200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100016378","name":"Technische Universit\u00e4t Dortmund","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100016378","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Given a point set\n                    <jats:italic>P<\/jats:italic>\n                    in the Euclidean plane and a parameter\n                    <jats:italic>t<\/jats:italic>\n                    , we define an\n                    <jats:italic>oriented<\/jats:italic>\n                    <jats:italic>t<\/jats:italic>\n                    <jats:italic>-spanner<\/jats:italic>\n                    <jats:italic>G<\/jats:italic>\n                    as an oriented subgraph of the complete bi-directed graph such that for every pair of points, the shortest closed walk in\n                    <jats:italic>G<\/jats:italic>\n                    through those points is at most a factor\n                    <jats:italic>t<\/jats:italic>\n                    longer than the shortest cycle in the complete graph on\n                    <jats:italic>P<\/jats:italic>\n                    . We investigate the problem of computing sparse graphs with small oriented dilation. As we can show that minimising oriented dilation for a given number of edges is NP-hard in the plane, we first consider one-dimensional point sets. While obtaining a 1-spanner in this setting is straightforward, already for five points such a spanner has no plane embedding with the leftmost and rightmost point on the outer face. This leads to restricting to oriented graphs with a one-page book embedding on the one-dimensional point set. For this case we present a dynamic program to compute the graph of minimum oriented dilation that runs in\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\mathcal {O}(n^7)$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    time for\n                    <jats:italic>n<\/jats:italic>\n                    points, and a greedy algorithm that computes a 5-spanner in\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\mathcal {O}(n\\log n)$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    time. Expanding these results finally gives us a result for two-dimensional point sets: we prove that for convex point sets the greedy triangulation results in a plane oriented\n                    <jats:italic>t<\/jats:italic>\n                    -spanner with\n                    <jats:inline-formula>\n                      <jats:tex-math>$$t=7.2 \\cdot t_g$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , where\n                    <jats:inline-formula>\n                      <jats:tex-math>$$t_g$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    is an upper bound on the dilation of the greedy triangulation.\n                  <\/jats:p>","DOI":"10.1007\/s00453-025-01342-8","type":"journal-article","created":{"date-parts":[[2025,12,11]],"date-time":"2025-12-11T12:55:32Z","timestamp":1765457732000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Oriented Spanners"],"prefix":"10.1007","volume":"88","author":[{"given":"Kevin","family":"Buchin","sequence":"first","affiliation":[]},{"given":"Joachim","family":"Gudmundsson","sequence":"additional","affiliation":[]},{"given":"Antonia","family":"Kalb","sequence":"additional","affiliation":[]},{"given":"Aleksandr","family":"Popov","sequence":"additional","affiliation":[]},{"given":"Carolin","family":"Rehs","sequence":"additional","affiliation":[]},{"given":"Andr\u00e9","family":"van Renssen","sequence":"additional","affiliation":[]},{"given":"Sampson","family":"Wong","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,12,11]]},"reference":[{"key":"1342_CR1","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 _{\\text{6 }}$$-graph. Comput. Geom. 105\u2013106, 101881 (2022). https:\/\/doi.org\/10.1016\/j.comgeo.2022.101881","journal-title":"Comput. Geom."},{"key":"1342_CR2","doi-asserted-by":"publisher","unstructured":"Aronov, B., Buchin, K., Buchin, M., Jansen, B., De Jong, T., Kreveld, M.v., L\u00f6ffler, M., Luo, J., Speckmann, B., Silveira, R.I.: Connect the dot: computing feed-links for network extension. J. Spatial Inform. Sci. 3, 3\u201331 (2011). https:\/\/doi.org\/10.5311\/JOSIS.2011.3.47","DOI":"10.5311\/JOSIS.2011.3.47"},{"issue":"1","key":"1342_CR3","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/s00453-015-0016-8","volume":"75","author":"MA Bekos","year":"2016","unstructured":"Bekos, M.A., Gronemann, M., Raftopoulou, C.N.: Two-page book embeddings of 4-planar graphs. Algorithmica 75(1), 158\u2013185 (2016). https:\/\/doi.org\/10.1007\/s00453-015-0016-8","journal-title":"Algorithmica"},{"key":"1342_CR4","doi-asserted-by":"publisher","unstructured":"Bose, P., Lee, A., Smid, M.: On generalized diamond spanners. In: F.\u00a0Dehne, J.R. Sack, N.\u00a0Zeh (eds.) Proc. 10th Internat. Sympos. Algorithms and Data Struct., Lecture Notes in Computer Science, vol. 4619, pp. 325\u2013336. Springer-Verlag (2007). https:\/\/doi.org\/10.1007\/978-3-540-73951-7_29","DOI":"10.1007\/978-3-540-73951-7_29"},{"issue":"7","key":"1342_CR5","doi-asserted-by":"publisher","first-page":"818","DOI":"10.1016\/j.comgeo.2013.04.002","volume":"46","author":"P Bose","year":"2013","unstructured":"Bose, P., Smid, M.: On plane geometric spanners: a survey and open problems. Comput. Geom. Theory Appl. 46(7), 818\u2013830 (2013). https:\/\/doi.org\/10.1016\/j.comgeo.2013.04.002","journal-title":"Comput. Geom. Theory Appl."},{"key":"1342_CR6","unstructured":"Brandt, A.F., Gaiowski, M.M., de\u00a0Souza, C.C., de\u00a0Rezende, P.J.: Minimum dilation triangulation: Reaching optimality efficiently. In: Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG) (2014)"},{"key":"1342_CR7","doi-asserted-by":"publisher","unstructured":"Buchin, K., Gudmundsson, J., Kalb, A., Popov, A., Rehs, C., van Renssen, A., Wong, S.: Oriented spanners. In: I.L. G\u00f8rtz, M.\u00a0Farach-Colton, S.J. Puglisi, G.\u00a0Herman (eds.) 31st Annual European Symposium on Algorithms, ESA 2023, September 4\u20136, 2023, Amsterdam, The Netherlands, LIPIcs, vol. 274, pp. 26:1\u201326:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2023.26","DOI":"10.4230\/LIPIcs.ESA.2023.26"},{"key":"1342_CR8","doi-asserted-by":"publisher","unstructured":"Burkhart, M., Von\u00a0Rickenbach, P., Wattenhofer, R., Zollinger, A.: Does topology control reduce interference? In: Proceedings of the Fifth ACM International Symposium Mobile Ad Hoc Networking and Computing, pp. 9\u201319 (2004). https:\/\/doi.org\/10.1145\/989459.989462","DOI":"10.1145\/989459.989462"},{"issue":"1","key":"1342_CR9","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/0608002","volume":"8","author":"FRK Chung","year":"1987","unstructured":"Chung, F.R.K., Leighton, F.T., Rosenberg, A.L.: Embedding graphs in books: a layout problem with applications to vlsi design. SIAM J. Algebraic Discrete Methods 8(1), 33\u201358 (1987). https:\/\/doi.org\/10.1137\/0608002","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"1342_CR10","doi-asserted-by":"publisher","unstructured":"Cowen, L.J., Wagner, C.G.: Compact roundtrip routing for digraphs. In: R.E. Tarjan, T.J. Warnow (eds.) Proceeding of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 885\u2013886. SIAM (1999). https:\/\/doi.org\/10.5555\/314500.315068","DOI":"10.5555\/314500.315068"},{"issue":"1","key":"1342_CR11","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jalgor.2003.08.001","volume":"50","author":"LJ Cowen","year":"2004","unstructured":"Cowen, L.J., Wagner, C.G.: Compact roundtrip routing in directed networks. J. Algor. 50(1), 79\u201395 (2004). https:\/\/doi.org\/10.1016\/j.jalgor.2003.08.001","journal-title":"J. Algor."},{"key":"1342_CR12","doi-asserted-by":"publisher","unstructured":"Das, G., Joseph, D.: Which triangulations approximate the complete graph? In: H.\u00a0Djidjev (ed.) Optimal Algorithms, Lecture Notes in Computer Science, vol. 401, pp. 168\u2013192. Springer-Verlag (1989). https:\/\/doi.org\/10.1007\/3-540-51859-2_15","DOI":"10.1007\/3-540-51859-2_15"},{"issue":"1","key":"1342_CR13","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1177\/0278364913498","volume":"33","author":"A Dobson","year":"2014","unstructured":"Dobson, A., Bekris, K.: Sparse roadmap spanners for asymptotically near-optimal motion planning. Int. J. Robot. Res. 33(1), 18\u201347 (2014). https:\/\/doi.org\/10.1177\/0278364913498","journal-title":"Int. J. Robot. Res."},{"issue":"1\u20132","key":"1342_CR14","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/S0166-218X(00)00236-5","volume":"109","author":"RLS Drysdale","year":"2001","unstructured":"Drysdale, R.L.S., McElfresh, S.A., Snoeyink, J.: On exclusion regions for optimal triangulations. Discrete Appl. Math. 109(1\u20132), 49\u201365 (2001). https:\/\/doi.org\/10.1016\/S0166-218X(00)00236-5","journal-title":"Discrete Appl. Math."},{"key":"1342_CR15","doi-asserted-by":"publisher","first-page":"339","DOI":"10.46298\/dmtcs.317","volume":"6","author":"V Dujmovic","year":"2004","unstructured":"Dujmovic, V., Wood, D.R.: On linear layouts of graphs. Discrete Math. Theor. Comput. Sci. 6, 339\u2013358 (2004). https:\/\/doi.org\/10.46298\/dmtcs.317","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"1342_CR16","doi-asserted-by":"publisher","unstructured":"Eppstein, D.: Spanning trees and spanners. In: Handbook of Computational Geometry, pp. 425\u2013461. North-Holland (2000). https:\/\/doi.org\/10.1016\/B978-044482537-7\/50010-3","DOI":"10.1016\/B978-044482537-7\/50010-3"},{"issue":"2","key":"1342_CR17","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1142\/S0218195910003244","volume":"20","author":"P Giannopoulos","year":"2010","unstructured":"Giannopoulos, P., Klein, R., Knauer, C., Kutz, M., Marx, D.: Computing geometric minimum-dilation graphs is NP-hard. Int. J. Comput. Geom. Appl. 20(2), 147\u2013173 (2010). https:\/\/doi.org\/10.1142\/S0218195910003244","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"4","key":"1342_CR18","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/0211056","volume":"11","author":"A Itai","year":"1982","unstructured":"Itai, A., Papadimitriou, C.H., Szwarcfiter, J.L.: Hamilton paths in grid graphs. SIAM J. Comput. 11(4), 676\u2013686 (1982)","journal-title":"SIAM J. Comput."},{"key":"1342_CR19","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 Euclidean graph. Discrete Comput. Geom. 7, 13\u201328 (1992). https:\/\/doi.org\/10.1007\/BF02187821","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"1342_CR20","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0925-7721(99)00037-1","volume":"14","author":"C Levcopoulos","year":"1999","unstructured":"Levcopoulos, C., Krznaric, D.: The greedy triangulation can be computed from the Delaunay triangulation in linear time. Comput. Geom. Theory Appl. 14(4), 197\u2013220 (1999). https:\/\/doi.org\/10.1016\/S0925-7721(99)00037-1","journal-title":"Comput. Geom. Theory Appl."},{"issue":"2","key":"1342_CR21","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/BF01994882","volume":"32","author":"C Levcopoulos","year":"1992","unstructured":"Levcopoulos, C., Lingas, A.: Fast algorithms for greedy triangulation. BIT 32(2), 280\u2013296 (1992). https:\/\/doi.org\/10.1007\/BF01994882","journal-title":"BIT"},{"key":"1342_CR22","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884","author":"G Narasimhan","year":"2007","unstructured":"Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press (2007). https:\/\/doi.org\/10.1017\/CBO9780511546884","journal-title":"Geometric Spanner Networks. Cambridge University Press"},{"issue":"3","key":"1342_CR23","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/j.comgeo.2006.02.001","volume":"36","author":"C Schindelhauer","year":"2007","unstructured":"Schindelhauer, C., Volbert, K., Ziegler, M.: Geometric spanners with applications in wireless networks. Comput. Geom. Theory Appl. 36(3), 197\u2013214 (2007). https:\/\/doi.org\/10.1016\/j.comgeo.2006.02.001","journal-title":"Comput. Geom. Theory Appl."},{"issue":"1","key":"1342_CR24","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/0022-0000(89)90032-9","volume":"38","author":"M Yannakakis","year":"1989","unstructured":"Yannakakis, M.: Embedding planar graphs in four pages. J. Comput. Syst. Sci. 38(1), 36\u201367 (1989). https:\/\/doi.org\/10.1016\/0022-0000(89)90032-9","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01342-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01342-8","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01342-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T05:11:26Z","timestamp":1770009086000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01342-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,11]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["1342"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01342-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,11]]},"assertion":[{"value":"12 June 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 October 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 December 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"14"}}