Clique-based separators for geometric intersection graphs

DOI10.1007/S00453-022-01041-8MaRDI QIDQ6103521zbMATH OpenOpenAlexFDO

Authors Mark de Berg, Sándor Kisfaludi-Bak, Morteza Monemizadeh, Leonidas Theocharous

Publication date 5 June 2023

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2109.09874

zbMATH Keywords

computational geometryintersection graphsseparator theorems

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Abstract: 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 $deltan$, for some fixed constant $delta<1$. The weight of a clique-based separator is defined as $su{m}_{CinS}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(sqrtn)$. We extend this result in several directions, obtaining the following results. Map graphs admit a balanced clique-based separator of weight $O(sqrtn)$, which is tight in the worst case. Intersection graphs of pseudo-disks admit a balanced clique-based separator of weight $O(n^{2/3}logn)$. If the pseudo-disks are polygonal and of total complexity $O(n)$ then the weight of the separator improves to $O(sqrtnlogn)$. Intersection graphs of geodesic disks inside a simple polygon admit a balanced clique-based separator of weight $O(n^{2/3}logn)$. Visibility-restricted unit-disk graphs in a polygonal domain with $r$ reflex vertices admit a balanced clique-based separator of weight $O(sqrtn+rlog(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.

Cites work

• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 2145241 (Why is no real title available?)
• A Helly-type theorem for intersections of compact connected sets in the plane
• A Separator Theorem for Planar Graphs
• A bipartite strengthening of the crossing Lemma
• A finite family of pseudodiscs must include a ``small pseudodisc
• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• Applications of random sampling in computational geometry. II
• Approximation algorithms for independent sets in map graphs
• Approximation algorithms for polynomial-expansion and low-density graphs
• Computational geometry. Algorithms and applications.
• Computing the geodesic center of a simple polygon
• Computing the visibility graph of points within a polygon
• Constructing planar support for non-piercing regions
• Decomposition of Map Graphs with Applications.
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• How Does Object Fatness Impact the Complexity of Packing in d Dimensions
• Hyperbolic intersection graphs and (quasi)-polynomial time
• Improved bounds for the union of locally fat objects in the plane
• Map graphs
• Near-optimal separators in string graphs
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Optimality program in segment and string graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Reduced constants for simple cycle graph separation
• Separators for sphere-packings and nearest neighbor graphs
• Separators in region intersection graphs

Cited in

(6)

• Faster algorithms for cycle hitting problems on disk graphs
• Sparse outerstring graphs have logarithmic treewidth
• Shortest path separators in unit disk graphs
• Computing diameter+2 in truly-subquadratic time for unit-disk graphs
• A clique-based separator for intersection graphs of geodesic disks in \(\mathbb{R}^2\)
• A clique-based separator for intersection graphs of geodesic disks in \(\mathbb{R}^2\)

This page was built for publication: Clique-based separators for geometric intersection graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6103521)