Pith. sign in

REVIEW 1 cited by

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

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2301.05550 v1 pith:YQWNL4LC submitted 2023-01-13 cs.CG

classification cs.CG
keywords mathbbexistsplaneunitcompletediskeuclideangraph
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Layered tree-independence number and clique-based separators

    math.CO 2025-06 conditional novelty 7.0 of 10

    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.

Pith tools