@inproceedings{be1a8884af814848bdcf5987832f15d0,

title = "Sparse geometric graphs with small dilation",

abstract = "Given a set S of n points in the plane, and an integer k such that 0 = k <n, we show that a geometric graph with vertex set S, at most n – 1 + k edges, and dilation O(n / (k + 1)) can be computed in time O(n log n). We also construct n–point sets for which any geometric graph with n – 1 + k edges has dilation O(n / (k + 1)); a slightly weaker statement holds if the points of S are required to be in convex position. This work was supported by LG Electronics and NUS research grant R-252-000-166-112. Research by B.A. has been supported in part by NSF ITR Grant CCR-00-81964 and by a grant from US-Israel Binational Science Foundation. Part of the work was carried out while B.A. was visiting TU/e in February 2004 and in the summer of 2005. MdB was supported by the Netherlands{\textquoteright} Organisation for Scientific Research (NWO) under project no. 639.023.301.",

author = "B. Aronov and {Berg, de}, M. and O. Cheong and J. Gudmundsson and H.J. Haverkort and A. Vigneron",

year = "2005",

doi = "10.1007/11602613_7",

language = "English",

isbn = "3-540-30935-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "50--59",

editor = "X. Deng and D. Du",

booktitle = "Algorithms and Computation : 16th International Symposium, ISAAC2005, Sanya, Hainan, China, December 19-21, 2005 : proceedings",

address = "Germany",

}