Approximate similarity search in high-dimensional spaces is currently dominated by graph-based indexing methods. While the practical results of these methods are well-studied, the theoretical underpinnings are less understood. That lead to numerous heuristics and yet little indicators for proper parameter settings. Many publications emphasize the efficacy of graph classes such as Relative Neighborhood Graphs (RNG) or k-Nearest Neighbor Graphs (kNNG) for indexing but lack both an evaluation of how well their algorithm approximates these graph classes and a theoretical understanding of the implications of these approximations. This paper intends to advance the theoretical understanding of the aspired graph classes and discuss the consequences for how we build and search in graphs. While parts of this work are preliminary, we experimentally confirm some immediate practical implications of our findings.