Constructing Planar Support for Non-Piercing Regions

Rajiv Raman, Saurabh Ray

Research output: Contribution to journalArticle

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 hypergraphHR(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 non-piercing regions in the plane and coloring of intersection hypergraph of non-piercing regions.

Original languageEnglish (US)
Pages (from-to)1098-1122
Number of pages25
JournalDiscrete and Computational Geometry
Volume64
Issue number3
DOIs
StatePublished - Oct 1 2020

Keywords

  • Geometric hypergraphs
  • Local search
  • Packing and covering
  • Planar support
  • Pseudodisks

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Constructing Planar Support for Non-Piercing Regions'. Together they form a unique fingerprint.

  • Cite this