Sparse geometric graphs with small dilation

B. Aronov, M. Berg, de, O. Cheong, J. Gudmundsson, H.J. Haverkort, A. Vigneron

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)


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’ Organisation for Scientific Research (NWO) under project no. 639.023.301.
Original languageEnglish
Title of host publicationAlgorithms and Computation : 16th International Symposium, ISAAC2005, Sanya, Hainan, China, December 19-21, 2005 : proceedings
EditorsX. Deng, D. Du
Place of PublicationBerlin
ISBN (Print)3-540-30935-7
Publication statusPublished - 2005

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Sparse geometric graphs with small dilation'. Together they form a unique fingerprint.

Cite this