Clique-Based Separators for Geometric Intersection Graphs
OPEN ACCESS
Loading...
Author / Producer
Date
2021
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
Let F be a set of n objects in the plane and let G^x(F) be its intersection graph. A balanced clique-based separator of G^x(F) is a set S consisting of cliques whose removal partitions G^x(F) into components of size at most δn, for some fixed constant δ < 1. The weight of a clique-based separator is defined as ∑_{C ∈ S} log (|C|+1). Recently De Berg et al. (SICOMP 2020) proved that if S consists of convex fat objects, then G^x(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.
Permanent link
Publication status
published
External links
Book title
32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Volume
212
Pages / Article No.
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Computational geometry; intersection graphs; separator theorems; Theory of computation → Design and analysis of algorithms
Organisational unit
02889 - ETH Institut für Theoretische Studien / ETH Institute for Theoretical Studies
Notes
Conference lecture held on December 6, 2021