2026-08-04T09:13:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15455 2024-03-06T10:55:20Z ddc:004 open_access

Clique-Based Separators for Geometric Intersection Graphs de Berg, Mark Kisfaludi-Bak, Sándor Monemizadeh, Morteza Theocharous, Leonidas Computational geometry intersection graphs separator theorems Let F be a set of n objects in the plane and let 𝒢^{×}(F) be its intersection graph. A balanced clique-based separator of 𝒢^{×}(F) is a set 𝒮 consisting of cliques whose removal partitions 𝒢^{×}(F) into components of size at most δ n, for some fixed constant δ < 1. The weight of a clique-based separator is defined as ∑_{C ∈ 𝒮}log (|C|+1). Recently De Berg et al. (SICOMP 2020) proved that if S consists of convex fat objects, then 𝒢^{×}(F) admits a balanced clique-based separator of weight O(√n). We extend this result in several directions, obtaining the following results. - Map graphs admit a balanced clique-based separator of weight O(√n), which is tight in the worst case. - Intersection graphs of pseudo-disks admit a balanced clique-based separator of weight O(n^{2/3} log n). If the pseudo-disks are polygonal and of total complexity O(n) then the weight of the separator improves to O(√n log n). - Intersection graphs of geodesic disks inside a simple polygon admit a balanced clique-based separator of weight O(n^{2/3} log n). - Visibility-restricted unit-disk graphs in a polygonal domain with r reflex vertices admit a balanced clique-based separator of weight O(√n + r log(n/r)), which is tight in the worst case. These results immediately imply sub-exponential algorithms for MAXIMUM INDEPENDENT SET (and, hence, VERTEX COVER), for FEEDBACK VERTEX SET, and for q-Coloring for constant q in these graph classes. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mark de Berg and Sándor Kisfaludi-Bak and Morteza Monemizadeh and Leonidas Theocharous 2021 Is Part Of LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2021.22 urn:nbn:de:0030-drops-154556 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.22 eng https://creativecommons.org/licenses/by/4.0/legalcode