{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T23:43:12Z","timestamp":1648856592119},"reference-count":7,"publisher":"World Scientific Pub Co Pte Lt","issue":"03n04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:p> We present tight bounds on the spanning ratio of a large family of ordered [Formula: see text]-graphs. A [Formula: see text]-graph partitions the plane around each vertex into [Formula: see text] disjoint cones, each having aperture [Formula: see text]. An ordered [Formula: see text]-graph is constructed by inserting the vertices one by one and connecting each vertex to the closest previously-inserted vertex in each cone. We show that for any integer [Formula: see text], ordered [Formula: see text]-graphs with [Formula: see text] cones have a tight spanning ratio of [Formula: see text]. We also show that for any integer [Formula: see text], ordered [Formula: see text]-graphs with [Formula: see text] cones have a tight spanning ratio of [Formula: see text]. We provide lower bounds for ordered [Formula: see text]-graphs with [Formula: see text] and [Formula: see text] cones. For ordered [Formula: see text]-graphs with [Formula: see text] and [Formula: see text] cones these lower bounds are strictly greater than the worst case spanning ratios of their unordered counterparts. These are the first results showing that ordered [Formula: see text]-graphs have worse spanning ratios than unordered [Formula: see text]-graphs. Finally, we show that, unlike their unordered counterparts, the ordered [Formula: see text]-graphs with 4, 5, and 6 cones are not spanners. <\/jats:p>","DOI":"10.1142\/s0218195916600013","type":"journal-article","created":{"date-parts":[[2017,4,17]],"date-time":"2017-04-17T05:27:36Z","timestamp":1492406856000},"page":"135-149","source":"Crossref","is-referenced-by-count":0,"title":["The Price of Order"],"prefix":"10.1142","volume":"26","author":[{"given":"Prosenjit","family":"Bose","sequence":"first","affiliation":[{"name":"School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, K1S 5B6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, K1S 5B6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"van Renssen","sequence":"additional","affiliation":[{"name":"JST, ERATO, Kawarabayashi Large Graph Project, National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2017,4,17]]},"reference":[{"key":"S0218195916600013BIB001","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884"},{"key":"S0218195916600013BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.01.003"},{"key":"S0218195916600013BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90044-5"},{"key":"S0218195916600013BIB008","doi-asserted-by":"publisher","DOI":"10.1137\/140988103"},{"key":"S0218195916600013BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.12.017"},{"key":"S0218195916600013BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2014.05.001"},{"key":"S0218195916600013BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2014.08.005"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195916600013","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T09:29:23Z","timestamp":1565170163000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195916600013"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9]]},"references-count":7,"journal-issue":{"issue":"03n04","published-online":{"date-parts":[[2017,4,17]]},"published-print":{"date-parts":[[2016,9]]}},"alternative-id":["10.1142\/S0218195916600013"],"URL":"https:\/\/doi.org\/10.1142\/s0218195916600013","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9]]}}}