Clique-based separators for geometric intersection graphs

DOI10.1007/s00453-022-01041-8arXiv2109.09874OpenAlexW3217451109MaRDI QIDQ6103521

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

Publication date: 5 June 2023

Published in: Algorithmica (Search for Journal in Brave)

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)

Related Items (1)

Faster algorithms for cycle hitting problems on disk graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the geodesic center of a simple polygon
• A bipartite strengthening of the crossing Lemma
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• A Helly-type theorem for intersections of compact connected sets in the plane
• Applications of random sampling in computational geometry. II
• Reduced constants for simple cycle graph separation
• Constructing planar support for non-piercing regions
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Approximation Algorithms for Independent Sets in Map Graphs
• Map graphs
• A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs
• Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
• A Separator Theorem for Planar Graphs
• Separators for sphere-packings and nearest neighbor graphs
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Separators in region intersection graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Decomposition of Map Graphs with Applications.
• Hyperbolic intersection graphs and (quasi)-polynomial time
• A Finite Family of Pseudodiscs Must Include a “Small” Pseudodisc
• Computing the visibility graph of points within a polygon
• Near-Optimal Separators in String Graphs
• Improved Bounds for the Union of Locally Fat Objects in the Plane
• How Does Object Fatness Impact the Complexity of Packing in d Dimensions
• Optimality program in segment and string graphs

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