DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2025.73

Embedding Graphs as Euclidean kNN-Graphs

Authors: Thomas Schibler, Subhash Suri, and Jie Xue

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract

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.

Cite as

Thomas Schibler, Subhash Suri, and Jie Xue. Embedding Graphs as Euclidean kNN-Graphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schibler_et_al:LIPIcs.SoCG.2025.73,
  author =	{Schibler, Thomas and Suri, Subhash and Xue, Jie},
  title =	{{Embedding Graphs as Euclidean kNN-Graphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{73:1--73:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.73},
  URN =		{urn:nbn:de:0030-drops-232253},
  doi =		{10.4230/LIPIcs.SoCG.2025.73},
  annote =	{Keywords: Geometric graphs, k-nearest neighbors, graph embedding, approximation algorithms}
}

Document

DOI: 10.4230/LIPIcs.ESA.2017.65

K-Dominance in Multidimensional Data: Theory and Applications

Authors: Thomas Schibler and Subhash Suri

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract

We study the problem of k-dominance in a set of d-dimensional vectors, prove bounds on the number of maxima (skyline vectors), under both worst-case and average-case models, perform experimental evaluation using synthetic and real-world data, and explore an application of k-dominant skyline for extracting a small set of top-ranked vectors in high dimensions where the full skylines can be unmanageably large.

Cite as

Thomas Schibler and Subhash Suri. K-Dominance in Multidimensional Data: Theory and Applications. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 65:1-65:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{schibler_et_al:LIPIcs.ESA.2017.65,
  author =	{Schibler, Thomas and Suri, Subhash},
  title =	{{K-Dominance in Multidimensional Data: Theory and Applications}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{65:1--65:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.65},
  URN =		{urn:nbn:de:0030-drops-78402},
  doi =		{10.4230/LIPIcs.ESA.2017.65},
  annote =	{Keywords: Dominance, skyline, database search, average case analysis, random vectors}
}

Search Results

Documents authored by Schibler, Thomas

Embedding Graphs as Euclidean kNN-Graphs

Abstract

Cite as

K-Dominance in Multidimensional Data: Theory and Applications

Abstract

Cite as

Thanks for your feedback!

Could not send message