# Recognizing Unit Disk Graphs in Hyperbolic Geometry is existsℝ-Complete

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jan 2023.

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

- [Weighted Embeddings for Low-Dimensional Graph Representation](https://mlsanity.com/paper/2410.06042/) (2024)

## Abstract (arXiv)

A graph G is a (Euclidean) unit disk graph if it is the intersection graph of unit disks in the Euclidean plane ℝ2. Recognizing them is known to be existsℝ-complete, i.e., as hard as solving a system of polynomial inequalities. In this note we describe a simple framework to translate existsℝ-hardness reductions from the Euclidean plane ℝ2 to the hyperbolic plane mathbbH2. We apply our framework to prove that the recognition of unit disk graphs in the hyperbolic plane is also existsℝ-complete.