TY - GEN

T1 - Planar support for non-piercing regions and applications

AU - Raman, Rajiv

AU - Ray, Saurabh

PY - 2018/8/1

Y1 - 2018/8/1

N2 - 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 sub-graph 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 HR(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, PTASs for packing and covering problems on non-piercing regions in the plane and coloring of intersection hypergraph of non-piercing regions.

AB - 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 sub-graph 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 HR(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, PTASs for packing and covering problems on non-piercing regions in the plane and coloring of intersection hypergraph of non-piercing regions.

KW - Geometric optimization

KW - Non-piercing regions

KW - Packing and covering

UR - http://www.scopus.com/inward/record.url?scp=85052498853&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85052498853&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2018.69

DO - 10.4230/LIPIcs.ESA.2018.69

M3 - Conference contribution

AN - SCOPUS:85052498853

SN - 9783959770811

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 26th European Symposium on Algorithms, ESA 2018

A2 - Bast, Hannah

A2 - Herman, Grzegorz

A2 - Azar, Yossi

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 26th European Symposium on Algorithms, ESA 2018

Y2 - 20 August 2018 through 22 August 2018

ER -