A Clique-Based Separator for Intersection Graphs of Geodesic Disks in ℝ²

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Downloads (Pure)

Abstract

Let d be a (well-behaved) shortest-path metric defined on a path-connected subset of ℝ² and let 𝒟 = {D_1,…,D_n} be a set of geodesic disks with respect to the metric d. We prove that 𝒢^×(𝒟), the intersection graph of the disks in 𝒟, has a clique-based separator consisting of O(n^{3/4+ε}) cliques. This significantly extends the class of objects whose intersection graphs have small clique-based separators.
Our clique-based separator yields an algorithm for q-Coloring that runs in time 2^O(n^{3/4+ε}), assuming the boundaries of the disks D_i can be computed in polynomial time. We also use our clique-based separator to obtain a simple, efficient, and almost exact distance oracle for intersection graphs of geodesic disks. Our distance oracle uses O(n^{7/4+ε}) storage and can report the hop distance between any two nodes in 𝒢^×(𝒟) in O(n^{3/4+ε}) time, up to an additive error of one. So far, distance oracles with an additive error of one that use subquadratic storage and sublinear query time were not known for such general graph classes.
Original languageEnglish
Title of host publication40th International Symposium on Computational Geometry (SoCG 2024)
EditorsWolfgang Mulzer, Jeff M. Phillips
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages9:1-9:15
Number of pages15
ISBN (Electronic)978-3-95977-316-4
DOIs
Publication statusPublished - 6 Jun 2024
Event40th International Symposium on Computational Geometry - Eugenides Foundation, Athens, Greece
Duration: 11 Jun 202414 Jun 2024
Conference number: 40
https://socg24.athenarc.gr/socg.html

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume293
ISSN (Electronic)1868-8969

Conference

Conference40th International Symposium on Computational Geometry
Abbreviated titleSoCG 2024
Country/TerritoryGreece
CityAthens
Period11/06/2414/06/24
Internet address

Funding

Boris Aronov: Work has been supported by NSF grant CCF 20-08551. Mark de Berg: MdB is supported by the Dutch Research Council (NWO) through Gravitation-grant NETWORKS-024.002.003.

FundersFunder number
Nederlandse Organisatie voor Wetenschappelijk Onderzoek
National Science FoundationCCF 20-08551

    Keywords

    • Computational geometry
    • intersection graphs
    • separator theorems

    Fingerprint

    Dive into the research topics of 'A Clique-Based Separator for Intersection Graphs of Geodesic Disks in ℝ²'. Together they form a unique fingerprint.

    Cite this