{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:21:04Z","timestamp":1760440864201},"reference-count":27,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p> Given a set P of n points in the plane, the order-k Delaunay graph is a graph with vertex set P and an edge exists between two points p, q \u2208 P when there is a circle through p and q with at most k other points of P in its interior. We provide upper and lower bounds on the number of edges in an order-k Delaunay graph. We study the combinatorial structure of the set of triangulations that can be constructed with edges of this graph. Furthermore, we show that the order-k Delaunay graph is connected under the flip operation when k \u2264 1 but not necessarily connected for other values of k. If P is in convex position then the order-k Delaunay graph is connected for all k \u2265 0. We show that the order-k Gabriel graph, a subgraph of the order-k Delaunay graph, is Hamiltonian for k \u2265 15. Finally, the order-k Delaunay graph can be used to efficiently solve a coloring problem with applications to frequency assignments in cellular networks. <\/jats:p>","DOI":"10.1142\/s0218195909003143","type":"journal-article","created":{"date-parts":[[2010,1,7]],"date-time":"2010-01-07T10:22:17Z","timestamp":1262859737000},"page":"595-615","source":"Crossref","is-referenced-by-count":24,"title":["ON STRUCTURAL AND GRAPH THEORETIC PROPERTIES OF HIGHER ORDER DELAUNAY GRAPHS"],"prefix":"10.1142","volume":"19","author":[{"given":"MANUEL","family":"ABELLANAS","sequence":"first","affiliation":[{"name":"Departamento de Matem\u00e1tica Aplicada, Facultad de Inform\u00e1tica, Universidad Polit\u00e9cnica de Madrid, Boadilla del Monte 28660, Madrid, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PROSENJIT","family":"BOSE","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario K1S 5B6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JES\u00daS","family":"GARC\u00cdA","sequence":"additional","affiliation":[{"name":"Departamento de Matem\u00e1tica Aplicada, Escuela de Inform\u00e1tica, Universidad Polit\u00e9cnica de Madrid, Ctra. de Valencia, Km. 7, 28031, Madrid, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"FERRAN","family":"HURTADO","sequence":"additional","affiliation":[{"name":"Departament de Matem\u00e0tica Aplicada II, Universitat Polit\u00e8cnica de Catalunya, Edifici Omega, Campus Nord, Jordi Girona, 1-3, 08034, Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CARLOS M.","family":"NICOL\u00c1S","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Kentucky, Lexington, KY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PEDRO","family":"RAMOS","sequence":"additional","affiliation":[{"name":"Departamento de Matem\u00e1ticas, Universidad de Alcal\u00e1, Apartado de Correos 20, 28871 Alcal\u00e1 de Henares, Madrid, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/j.csda.2006.09.004"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50003-6"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50006-1"},{"key":"rf5","unstructured":"M.\u00a0Bern, Handbook of Discrete and Computational Geometry, 2nd edn., eds. J.\u00a0Goodman and J.\u00a0O'Rourke (Elsevier Science Publishers B.V., North-Holland, Amsterdam, 2004)\u00a0pp. 563\u2013582."},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-52921-7_55"},{"key":"rf7","first-page":"793","volume":"7","author":"Delone B.","journal-title":"Izvestia Akad Nauk SSSR Otdel. Mat. Sov. Nauk."},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90160-8"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187810"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9"},{"key":"rf11","first-page":"1","volume":"32","author":"Edelsbrunner H.","journal-title":"Geom. Dedicata"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/PL00014417"},{"key":"rf14","unstructured":"S.\u00a0Fortune, Handbook of Discrete and Computational Geometry, 2nd edn., eds. J.\u00a0Goodman and J.\u00a0O'Rourke (Elsevier Science Publishers B.V., North-Holland, Amsterdam, 2004)\u00a0pp. 513\u2013528."},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00027-X"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.11.001"},{"key":"rf17","unstructured":"D.\u00a0Halperin, Handbook of Discrete and Computational Geometry, 2nd edn., eds. J.\u00a0Goodman and J.\u00a0O'Rourke (Elsevier Science Publishers B.V., North-Holland, Amsterdam, 2004)\u00a0pp. 529\u2013562."},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-005-1162-6"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1109\/5.163414"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2005.09.005"},{"key":"rf23","doi-asserted-by":"crossref","unstructured":"C.\u00a0Lawson, Mathematical Software III, ed. J.\u00a0Rice (Academic Press, New York, 1977)\u00a0pp. 161\u2013194.","DOI":"10.1016\/B978-0-12-587260-7.50011-X"},{"key":"rf24","first-page":"478","volume":"31","author":"Lee D. T.","journal-title":"IEEE Trans. Comput."},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/342\/06138"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1002\/9780470317013"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-7958-3_25"},{"key":"rf31","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-52921-7_56"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(91)90065-D"},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45995-2_4"},{"key":"rf34","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80069-7"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195909003143","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:24:15Z","timestamp":1565137455000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195909003143"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":27,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2009,12]]}},"alternative-id":["10.1142\/S0218195909003143"],"URL":"https:\/\/doi.org\/10.1142\/s0218195909003143","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]}}}