## Samenvatting

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
^{P}
_{C∈S} log(|C| + 1). Recently De Berg et al. (SICOMP 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. 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.

Originele taal-2 | Engels |
---|---|

Pagina's | 22:1-22:15 |

DOI's | |

Status | Gepubliceerd - 1 dec. 2021 |

Evenement | 32nd International Symposium on Algorithms and Computation, ISAAC 2021 - Fukuoka, Japan Duur: 6 dec. 2021 → 8 dec. 2021 |

### Congres

Congres | 32nd International Symposium on Algorithms and Computation, ISAAC 2021 |
---|---|

Land/Regio | Japan |

Stad | Fukuoka |

Periode | 6/12/21 → 8/12/21 |