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.
Recognizing Unit Disk Graphs in Hyperbolic Geometry is $\exists\mathbb{R}$-Complete
1 Pith paper cite this work. Polarity classification is still indexing.
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
citation-polarity summary
fields
math.CO 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
support 1representative citing papers
citing papers explorer
-
Layered tree-independence number and clique-based separators
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.