Recognizing Unit Disk Graphs in Hyperbolic Geometry is ∃ℝ-Complete

2023/01/13 by Nicholas Bieker, Bieker, Nicholas, Thomas Bläsius +5 · 2 citations
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Advanced Numerical Analysis Techniques #Mathematics and Applications

paper · pdf · doi:10.48550/arxiv.2301.05550

Abstract

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

Cited by

• Recognizing Penny and Marble Graphs is Hard for Existential Theory of the Reals
• Layered tree-independence number and clique-based separators

Related

• Hyperbolic intersection graphs and (quasi)-polynomial time
• Recognizing Penny and Marble Graphs is Hard for Existential Theory of the Reals
• Strongly Hyperbolic Unit Disk Graphs
• Structure and Independence in Hyperbolic Uniform Disk Graphs
• Integer realizations of disk and segment graphs