We introduce and analyze σ-local graphs, based on a definition of locality by Erickson [J. Erickson, Local polyhedra and geometric graphs, Computational Geometry: Theory and Applications 31 (1-2) (2005) 101-125]. We present two algorithms to construct such graphs, for any real number σ > 1 and any set S of n points. These algorithms run in time O (σd n + n log n) for sets in Rd and O (n log3 n log log n + k) for sets in the plane, where k is the size of the output. For sets in the plane, algorithms to find the minimum or maximum σ such that the corresponding graph has properties such as connectivity, planarity, and no-isolated vertex are presented, with complexities in O (n logO (1) n). These algorithms can also be used to efficiently construct the corresponding graphs.

Journal of Discrete Algorithms
School of Computer Science

Bose, P, Collette, S. (Sébastien), Langerman, S. (Stefan), Maheshwari, A, Morin, P, & Smid, M. (2010). Sigma-local graphs. Journal of Discrete Algorithms, 8(1), 15–23. doi:10.1016/j.jda.2008.10.002