Pith. sign in

Recognizing Unit Disk Graphs in Hyperbolic Geometry is $\exists\mathbb{R}$-Complete

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
abstract

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

citation-role summary

background 1

citation-polarity summary

fields

math.CO 1

years

2025 1

verdicts

CONDITIONAL 1

roles

background 1

polarities

support 1

representative citing papers

Layered tree-independence number and clique-based separators

math.CO · 2025-06-14 · conditional · novelty 7.0

Map graphs, hyperbolic uniform disk graphs, and spherical uniform disk graphs are shown to have bounded or radius-dependent layered tree-independence number, yielding new weighted subexponential algorithms.

citing papers explorer

Showing 1 of 1 citing paper.

  • Layered tree-independence number and clique-based separators math.CO · 2025-06-14 · conditional · none · ref 7 · internal anchor

    Map graphs, hyperbolic uniform disk graphs, and spherical uniform disk graphs are shown to have bounded or radius-dependent layered tree-independence number, yielding new weighted subexponential algorithms.