Constructing Planar Support for Non-Piercing Regions

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 hypergraphHR(B)=(B,{Br}r∈R), where B_r= { 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 non-piercing regions in the plane and coloring of intersection hypergraph of non-piercing regions.