Embedding Euclidean Distance Graphs in ℝⁿ and ℚⁿ

2021/08/17 by Matt Noble, Noble, Matt
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Metric Geometry (math.MG)

paper · pdf · doi:10.48550/arxiv.2108.07713

openalex publication_date 2021/08/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For S ⊆ ℝ, positive integer n, and d > 0, let G(Sⁿ, d) be the graph whose vertex set is Sⁿ where any two vertices are adjacent if and only if they are Euclidean distance d apart. The primary question we will consider in our work is as follows. Given n and distance d actually realized as a distance between points of the rational space ℚⁿ, does there exist a finite graph G that appears as a subgraph of G(ℚⁿ, d) but not as a subgraph of G(ℝ^n-1, 1)? We answer this question affirmatively for n ≤ 5, and along the way, resolve a few related questions as well.

Related

• Two notions of unit distance graphs
• On the Euclidean dimension of graphs
• Answer to an Isomorphism Problem in ℤ²
• The least Euclidean distortion constant of a distance-regular graph
• Interpolation of point configurations in the discrete plane