Structure and Independence in Hyperbolic Uniform Disk Graphs
Loading...
Access rights
openAccess
CC BY
CC BY
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
16
Series
41st International Symposium on Computational Geometry, SoCG 2025, pp. 1-16, Leibniz International Proceedings in Informatics, LIPIcs ; Volume 332
Abstract
We consider intersection graphs of disks of radius r in the hyperbolic plane. Unlike the Euclidean setting, these graph classes are different for different values of r, where very small r corresponds to an almost-Euclidean setting and r ∈ Ω(log n) corresponds to a firmly hyperbolic setting. We observe that larger values of r create simpler graph classes, at least in terms of separators and the computational complexity of the Independent Set problem. First, we show that intersection graphs of disks of radius r in the hyperbolic plane can be separated with O((1 + 1/r) log n) cliques in a balanced manner. Our second structural insight concerns Delaunay complexes in the hyperbolic plane and may be of independent interest. We show that for any set S of n points with pairwise distance at least 2r in the hyperbolic plane, the corresponding Delaunay complex has outerplanarity 1 + O(log n/r), which implies a similar bound on the balanced separators and treewidth of such Delaunay complexes. Using this outerplanarity (and treewidth) bound we prove that Independent Set can be solved in nO(1+ log n/r) time. The algorithm is based on dynamic programming on some unknown sphere cut decomposition that is based on the solution. The resulting algorithm is a far-reaching generalization of a result of Kisfaludi-Bak (SODA 2020), and it is tight under the Exponential Time Hypothesis. In particular, Independent Set is polynomial-time solvable in the firmly hyperbolic setting of r ∈ Ω(log n). Finally, in the case when the disks have ply (depth) at most ℓ, we give a PTAS for Maximum Independent Set that has only quasi-polynomial dependence on 1/∈ and ℓ. Our PTAS is a further generalization of our exact algorithm.Description
Publisher Copyright: © Thomas Bläsius, Jean-Pierre von der Heydt, Sándor Kisfaludi-Bak, Marcus Wilhelm, and Geert van Wordragen.
Other note
Citation
Bläsius, T, Von Der Heydt, J P, Kisfaludi-Bak, S, Wilhelm, M & Van Wordragen, G 2025, Structure and Independence in Hyperbolic Uniform Disk Graphs. in O Aichholzer & H Wang (eds), 41st International Symposium on Computational Geometry, SoCG 2025., 21, Leibniz International Proceedings in Informatics, LIPIcs, vol. 332, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-16, International Symposium on Computational Geometry, Kanazawa, Japan, 23/06/2025. https://doi.org/10.4230/LIPIcs.SoCG.2025.21