Constructing Planar Support for Non-Piercing Regions
- PDF / 815,701 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 10 Downloads / 161 Views
Constructing Planar Support for Non-Piercing Regions Rajiv Raman1 · Saurabh Ray2 Received: 27 July 2018 / Revised: 29 February 2020 / Accepted: 10 May 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Given a hypergraph H = (X , S), a planar support for H is a planar graph G with vertex set X , such that for each hyperedge S ∈ S, the subgraph of G induced by the vertices in S is connected. Planar supports for hypergraphs have found several algorithmic applications, including several packing and covering problems, hypergraph coloring, and in hypergraph visualization. The main result proved in this paper is the following: given two families of regions R and B in the plane, each of which consists of connected, non-piercing regions, the intersection hypergraph H R (B) = (B, {Br }r ∈R ), where Br = {b ∈ B : b ∩ r = ∅} has a planar support. Further, such a planar support can be computed in time polynomial in |R|, |B|, and the number of vertices in the arrangement of the regions in R ∪ B. Special cases of this result include the setting where either the family R, or the family B is a set of points. Our result unifies and generalizes several previous results on planar supports, PTAS’s for packing and covering problems on nonpiercing regions in the plane and coloring of intersection hypergraph of non-piercing regions. Keywords Pseudodisks · Planar support · Geometric hypergraphs · Packing and covering · Local search
Dedicated to the memory of Ricky Pollack Editor in Charge: János Pach A preliminary version has appeared in ESA 2018 [23] Rajiv Raman [email protected] Saurabh Ray [email protected] 1
Department of Computer Science, IIIT, Delhi, India
2
Computer Science, New York University, Abu Dhabi, United Arab Emirates
123
Discrete & Computational Geometry
1 Introduction For hypergraphs, which arise naturally in many applications, it is often helpful to capture their structure using a sparse graph. One popular way to do this is to construct a planar support, which is a planar graph G with the same vertex set as the hypergraph such that every hyperedge induces a connected subgraph of G. In this paper, we study hypergraphs that arise in several, primarily geometric settings. For example, a set of points P and a family of disks D in the plane define a hypergraph, H(P, D), where each disk d ∈ D defines a hyperedge P ∩ d. This is a widely studied hypergraph, and it is well known that the Delaunay graph of the points is a planar support for this hypergraph. Another hypergraph on the same objects is H(D, P), where the vertices are the disks, and each point p ∈ P defines a hyperedge {d ∈ D : d p}. We refer to H(P, D) as the primal hypergraph, and to H(D, P) as the dual hypergraph. A hypergraph that generalizes both these hypergraphs is the following: Given a family R of red disks, and a family B of blue disks, we define the intersection hypergraph H(B, R) as follows: the disks B are the vertices, and there is a hyperedge corresponding to each disk r ∈ R, Br = {b ∈ B : r ∩ b = ∅}. Note
Data Loading...
