de Berg, Mark ;
KisfaludiBak, Sándor ;
Monemizadeh, Morteza ;
Theocharous, Leonidas
CliqueBased 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 cliquebased 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 cliquebased 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 cliquebased separator of weight O(√n). We extend this result in several directions, obtaining the following results.
 Map graphs admit a balanced cliquebased separator of weight O(√n), which is tight in the worst case.
 Intersection graphs of pseudodisks admit a balanced cliquebased separator of weight O(n^{2/3} log n). If the pseudodisks 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 cliquebased separator of weight O(n^{2/3} log n).
 Visibilityrestricted unitdisk graphs in a polygonal domain with r reflex vertices admit a balanced cliquebased separator of weight O(√n + r log(n/r)), which is tight in the worst case. These results immediately imply subexponential algorithms for MAXIMUM INDEPENDENT SET (and, hence, VERTEX COVER), for FEEDBACK VERTEX SET, and for qColoring for constant q in these graph classes.
BibTeX  Entry
@InProceedings{deberg_et_al:LIPIcs.ISAAC.2021.22,
author = {de Berg, Mark and KisfaludiBak, S\'{a}ndor and Monemizadeh, Morteza and Theocharous, Leonidas},
title = {{CliqueBased Separators for Geometric Intersection Graphs}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {22:122:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772143},
ISSN = {18688969},
year = {2021},
volume = {212},
editor = {Ahn, HeeKap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15455},
URN = {urn:nbn:de:0030drops154556},
doi = {10.4230/LIPIcs.ISAAC.2021.22},
annote = {Keywords: Computational geometry, intersection graphs, separator theorems}
}
30.11.2021
Keywords: 

Computational geometry, intersection graphs, separator theorems 
Seminar: 

32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Issue date: 

2021 
Date of publication: 

30.11.2021 