Minimum cuts in geometric intersection graphs

DOI10.1016/J.COMGEO.2020.101720MaRDI QIDQ827339zbMATH OpenOpenAlexFDO

Authors S. Cabello, Wolfgang Mulzer

Publication date 7 January 2021

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

disk graphvertex-disjoint pathsgeometric intersection graphunit-disk graphbarrier resilience

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: Let $mathcalD$ be a set of $n$ disks in the plane. The disk graph $G_{m}athcalD$ for $mathcalD$ is the undirected graph with vertex set $mathcalD$ in which two disks are joined by an edge if and only if they intersect. The directed transmission graph $G_m^{ightarrow}athcalD$ for $mathcalD$ is the directed graph with vertex set $mathcalD$ in which there is an edge from a disk $D_{1}inmathcalD$ to a disk $D_{2}inmathcalD$ if and only if $D_1$ contains the center of $D_2$. Given $mathcalD$ and two non-intersecting disks $s,tinmathcalD$, we show that a minimum $s$-$t$ vertex cut in $G_{m}athcalD$ or in $G_m^{ightarrow}athcalD$ can be found in $O(n^{3/2}extpolylogn)$ expected time. To obtain our result, we combine an algorithm for the maximum flow problem in general graphs with dynamic geometric data structures to manipulate the disks. As an application, we consider the barrier resilience problem in a rectangular domain. In this problem, we have a vertical strip $S$ bounded by two vertical lines, $L_{e}ll$ and $L_r$, and a collection $mathcalD$ of disks. Let $a$ be a point in $S$ above all disks of $mathcalD$, and let $b$ a point in $S$ below all disks of $mathcalD$. The task is to find a curve from $a$ to $b$ that lies in $S$ and that intersects as few disks of $mathcalD$ as possible. Using our improved algorithm for minimum cuts in disk graphs, we can solve the barrier resilience problem in $O(n^{3/2}extpolylogn)$ expected time.

Recommendations

• Cuttings for Disks and Axis-Aligned Rectangles
• Cuttings for disks and axis-aligned rectangles in three-space
• Polynomial-time approximation schemes for geometric graphs
• Shortest paths in intersection graphs of unit disks
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs

Cites work

• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 3349645 (Why is no real title available?)
• A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
• Combinatorial optimization. Theory and algorithms
• Computational geometry. Algorithms and applications.
• Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
• Dynamic half-space range reporting and its applications
• Flows in Undirected Unit Capacity Networks
• Geometric algorithms for sensor networks
• Geometry helps in bottleneck matching and related problems
• Hardness of minimum barrier shrinkage and minimum installation path
• Minimum Cell Connection in Line Segment Arrangements
• Minimum shared‐power edge cut
• Multi-path algorithms for minimum-colour path problems with applications to approximating barrier resilience
• Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
• Network Flow and Testing Graph Connectivity
• On the complexity of barrier resilience for fat regions and bounded ply
• Optimal deterministic algorithms for 2-d and 3-d shallow cuttings

Cited in

(7)

• Computational complexity for the problem of optimal intersection of straight line segments by disks
• Minimum cut with the fewest number of arcs
• Triangles and girth in disk graphs and transmission graphs
• scientific article; zbMATH DE number 1333614 (Why is no real title available?)
• Cuttings for disks and axis-aligned rectangles in three-space
• Minimum Cuts in Surface Graphs
• Computing the Map of Geometric Minimal Cuts

This page was built for publication: Minimum cuts in geometric intersection graphs

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