# Embedding Graphs as Euclidean kNN-Graphs

arXiv: https://arxiv.org/abs/2504.06503 · HTML: https://mlsanity.com/paper/2504.06503/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Apr 2025.

## Built on by (most cited first, 1 of 1)

- [Semantic Communities and Boundary-Spanning Lyrics in K-pop: A Graph-Based Unsupervised Analysis](https://mlsanity.com/paper/2602.12881/) (2026)

## Abstract (arXiv)

Let G = (V, E) be a directed graph on n vertices where each vertex has out-degree k. We say that G is kNN-realizable in d-dimensional Euclidean space if there exists a point set P = {p1, p2, ..., pn} in R^d along with a one-to-one mapping phi: V -> P such that for any u, v in V, u is an out-neighbor of v in G if and only if phi(u) is one of the k nearest neighbors of phi(v); we call the map phi a "kNN realization" of G in R^d. The kNN realization problem, which aims to compute such a mapping in R^d, is known to be NP-hard already for d = 2 and k = 1 (Eades and Whitesides, Theoretical Computer Science, 1996), and to the best of our knowledge, has not been studied in dimension d = 1. The main results of this paper are the following: (1) For any fixed dimension d >= 2, we can efficiently compute an embedding realizing at least a (1 - epsilon) fraction of G's edges, or conclude that G is not kNN-realizable in R^d. (2) For d = 1, we can decide in O(kn) time whether G is kNN-realizable and, if so, compute a realization in O(n^{2.5} * polylog(n)) time.