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

DOI10.4230/LIPICS.SOCG.2024.9MaRDI QIDQ6895898zbMATH OpenFDO

Authors Boris Aronov, Mark de Berg, Leonidas Theocharous

Publication date 24 November 2025

Copyright license Creative Commons Attribution 4.0 International

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

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 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
• Crossing-Free Subgraphs
• 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
• Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications

Cited in

(2)

• A clique-based separator for intersection graphs of geodesic disks in \(\mathbb{R}^2\)
• Star-based separators for intersection graphs of c-colored pseudo-segments

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 Q6895898)