Planar support for non-piercing regions and applications

Rajiv Raman, Saurabh Ray

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 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.

Original languageEnglish (US)
Title of host publication26th European Symposium on Algorithms, ESA 2018
EditorsHannah Bast, Grzegorz Herman, Yossi Azar
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Print)9783959770811
DOIs
StatePublished - Aug 1 2018
Event26th European Symposium on Algorithms, ESA 2018 - Helsinki, Finland
Duration: Aug 20 2018Aug 22 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume112
ISSN (Print)1868-8969

Other

Other26th European Symposium on Algorithms, ESA 2018
CountryFinland
CityHelsinki
Period8/20/188/22/18

Keywords

  • Geometric optimization
  • Non-piercing regions
  • Packing and covering

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Planar support for non-piercing regions and applications'. Together they form a unique fingerprint.

Cite this