Embedding Graphs as Euclidean kNN-Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916680220803072 |
|---|---|
| author | Schibler, T. Suri, S. Xue, J. |
| author_facet | Schibler, T. Suri, S. Xue, J. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_06503 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Embedding Graphs as Euclidean kNN-Graphs Schibler, T. Suri, S. Xue, J. Computational Geometry 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. |
| title | Embedding Graphs as Euclidean kNN-Graphs |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2504.06503 |