Clique-Based Separators for Geometric Intersection Graphs

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
Date
2023-06
Major/Subject
Mcode
Degree programme
Language
en
Pages
27
1652–1678
Series
Algorithmica, Volume 85, issue 6
Abstract
Let F be a set of n objects in the plane and let G×(F) be its intersection graph. A balanced clique-based separator of G×(F) is a set S consisting of cliques whose removal partitions G×(F) into components of size at most δn, for some fixed constant δ< 1. The weight of a clique-based separator is defined as ∑ C∈Slog (| C| + 1). Recently De Berg et al. (SIAM J. Comput. 49: 1291-1331. 2020) proved that if S consists of convex fat objects, then G×(F) admits a balanced clique-based separator of weight O(n). We extend this result in several directions, obtaining the following results. (i) Map graphs admit a balanced clique-based separator of weight O(n), which is tight in the worst case. (ii) Intersection graphs of pseudo-disks admit a balanced clique-based separator of weight O(n2 / 3log n). If the pseudo-disks are polygonal and of total complexity O(n) then the weight of the separator improves to O(nlogn). (iii) Intersection graphs of geodesic disks inside a simple polygon admit a balanced clique-based separator of weight O(n2 / 3log n). (iv) Visibility-restricted unit-disk graphs in a polygonal domain with r reflex vertices admit a balanced clique-based separator of weight O(n+rlog(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.
Description
Funding Information: The work in this paper is supported by the Dutch Research Council (NWO) through Gravitation-grant NETWORKS-024.002.003. Publisher Copyright: © 2022, The Author(s).
Keywords
Computational geometry, Intersection graphs, Separator theorems
Other note
Citation
de Berg , M , Kisfaludi-Bak , S , Monemizadeh , M & Theocharous , L 2023 , ' Clique-Based Separators for Geometric Intersection Graphs ' , Algorithmica , vol. 85 , no. 6 , pp. 1652–1678 . https://doi.org/10.1007/s00453-022-01041-8