Planar Supports for Non-piercing regions with Applications

A set S of compact, connected regions in the plane is said to be
non-piercing if for any pair of regions A,B in S, the sets A\B, 
and B\A are both connected. Examples of non-piercing regions 
include disks, unit-height rectangles, homothets of convex sets, 
etc. In our setting, we additionally allow regions that are not 
necessarily simply connected.

Given a hypergraph H=(X,E), a planar support is a planar graph G 
on the vertices X, such that for each hyperedge e in E, the induced 
subgraph of G on the vertices of e is connected.
Given two families of non-piercing regions R and B, the intersection
hypergraph is a hypergraph whose vertex set is the family B of 
non-piercing regions, and each region r in R defines a hyperedge
consisting of all regions in B intersecting the region r.

In this talk, I will present a polynomial time algorithm to construct
a planar support for the intersection hypergraph of two families of 
non-piercing regions in the plane. This result also has several 
applications, including unified PTASs for several packing and covering 
problems on non-piercing regions, as well as coloring hypergraphs 
of non-piercing regions.