Clique-Based Separators for Geometric Intersection Graphs
Loading...
Access rights
openAccess
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal
View/Open full text file from the Research portal
Other link related to publication
View publication in the Research portal
View/Open full text file from the Research portal
Other link related to publication
Date
2023-06
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
27
1652–1678
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
