2026-07-23T04:09:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23225 2025-10-02T12:43:35Z ddc:004 open_access

Embedding Graphs as Euclidean kNN-Graphs Schibler, Thomas Suri, Subhash Xue, Jie Geometric graphs k-nearest neighbors graph embedding approximation algorithms 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 = {p_1, p_2, …, p_n} in ℝ^d along with a one-to-one mapping ϕ: V → P such that for any u,v ∈ V, u is an out-neighbor of v in G if and only if ϕ(u) is one of the k nearest neighbors of ϕ(v); we call the map ϕ a kNN-realization of G in ℝ^d. The kNN-realization problem, which aims to compute a kNN-realization of an input graph in ℝ^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: - For any fixed dimension d ≥ 2, we can efficiently compute an embedding realizing at least a 1 - ε fraction of G’s edges, or conclude that G is not kNN-realizable in ℝ^d. - 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} poly(log n)) time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Schibler and Subhash Suri and Jie Xue 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.73 urn:nbn:de:0030-drops-232253 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.73 eng https://creativecommons.org/licenses/by/4.0/legalcode