License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.22
URN: urn:nbn:de:0030-drops-154556
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15455/
de Berg, Mark ;
Kisfaludi-Bak, Sándor ;
Monemizadeh, Morteza ;
Theocharous, Leonidas
Clique-Based Separators for Geometric Intersection Graphs
Abstract
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.
BibTeX - Entry
@InProceedings{deberg_et_al:LIPIcs.ISAAC.2021.22,
author = {de Berg, Mark and Kisfaludi-Bak, S\'{a}ndor and Monemizadeh, Morteza and Theocharous, Leonidas},
title = {{Clique-Based Separators for Geometric Intersection Graphs}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {22:1--22:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-214-3},
ISSN = {1868-8969},
year = {2021},
volume = {212},
editor = {Ahn, Hee-Kap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15455},
URN = {urn:nbn:de:0030-drops-154556},
doi = {10.4230/LIPIcs.ISAAC.2021.22},
annote = {Keywords: Computational geometry, intersection graphs, separator theorems}
}
|
Keywords: |
|
Computational geometry, intersection graphs, separator theorems |
|
Collection: |
|
32nd International Symposium on Algorithms and Computation (ISAAC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
30.11.2021 |
