Given a large weighted graph G = (V;E) and a subset U of V , we de¯ne several graphs
with vertex set U in which two vertices are adjacent if they satisfy some prescribed proximity rule. These rules use the shortest path distance in G and generalize the proximity rules that generate some of the most common proximity graphs in Euclidean spaces. We prove basic properties of the de¯ned graphs and provide algorithms for their computation.
Ábrego, B. [et al.]. Proximity graphs inside large weighted graphs. A: European Workshop on Computational Geometry. "26th European Workshop on Computational Geometry". Dortmund: 2010, p. 9-12.