文章基本信息

标题：Clique-Based Separators for Geometric Intersection Graphs
本地全文：下载
作者：de Berg, Mark ; Kisfaludi-Bak, Sándor ; Monemizadeh, Morteza 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：212
DOI：10.4230/LIPIcs.ISAAC.2021.22
语种：English
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 δ < 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.
关键词：Computational geometry;intersection graphs;separator theorems