A clique-based separator for intersection graphs of geodesic disks in R^2

DOI10.1007/S00453-025-01337-5MaRDI QIDQ6917981zbMATH OpenFDO

Authors Boris Aronov, Mark de Berg, Leonidas Theocharous

Publication date 10 October 2025

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00453-025-01337-5

zbMATH Keywords

computational geometryintersection graphsseparator theorems

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Cites work

• A clique-based separator for intersection graphs of geodesic disks in \(\mathbb{R}^2\)
• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• A note on reachability and distance oracles for transmission graphs
• A Separator Theorem for Planar Graphs
• Almost optimal exact distance oracles for planar graphs
• Approximate distance oracles
• Approximate distance oracles with constant query time
• Approximation algorithms for polynomial-expansion and low-density graphs
• Clique-based separators for geometric intersection graphs
• Computing diameter+2 in truly-subquadratic time for unit-disk graphs
• Computing list homomorphisms in geometric intersection graphs
• Distance oracles beyond the Thorup-Zwick bound
• scientific article; zbMATH DE number 7236428 (Why is no real title available?)
• On approximate distance labels and routing schemes with affine stretch
• Optimal approximate distance oracle for planar graphs
• Optimality program in segment and string graphs
• Planar spanners and approximate shortest path queries among obstacles in the plane
• Reduced constants for simple cycle graph separation
• Separator theorems and Turán-type results for planar intersection graphs
• Separators in region intersection graphs
• Shortest-path queries in static networks
• The weighted region problem
• Theory and application of width bounded geometric separators
• Theory and practice of combinatorics. A collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday
• Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications

This page was built for publication: A clique-based separator for intersection graphs of geodesic disks in \(\mathbb{R}^2\)

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