Structure and independence in hyperbolic uniform disk graphs

DOI10.4230/LIPICS.SOCG.2025.21MaRDI QIDQ7312663zbMATH OpenFDO

Authors Thomas Bläsius, Jean-Pierre von der Heydt, Sándor Kisfaludi-Bak, Marcus Wilhelm, Geert van Wordragen

Publication date 11 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.SOCG.2025.21

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Hyperbolic and elliptic geometries (general) and generalizations (51M10)

Cites work

• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• A partial k-arboretum of graphs with bounded treewidth
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• Call routing and the ratcatcher
• Chordal embeddings of planar graphs
• Clique-based separators for geometric intersection graphs
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry
• Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry
• Graph minors. X: Obstructions to tree-decomposition
• scientific article; zbMATH DE number 7529154 (Why is no real title available?)
• scientific article; zbMATH DE number 3027510 (Why is no real title available?)
• Hyperbolic intersection graphs and (quasi)-polynomial time
• Hyperbolic random graphs: separators and treewidth
• Integer realizations of disk and segment graphs
• Label placement by maximum independent set in rectangles
• On Geometric Set Cover for Orthants
• On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs
• On the complexity of k-SAT
• On the diameter of hyperbolic random graphs
• Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams
• Parameterized algorithms
• Polynomial-time approximation schemes for packing and piercing fat objects
• Quasi-polynomial time approximation scheme for sparse subsets of polygons
• Random hyperbolic graphs: degree sequence and clustering (extended abstract)
• Separators for sphere-packings and nearest neighbor graphs
• Simple heuristics for unit disk graphs
• Solving vertex cover in polynomial time on hyperbolic random graphs
• Strongly hyperbolic unit disk graphs
• The diameter of KPKVB random graphs

This page was built for publication: Structure and independence in hyperbolic uniform disk graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7312663)