Total: 1
Let (X,E) be a hypergraph. A support is a graph Q on X such that for each E∈E, the subgraph of Q induced on the elements in E is connected. We consider the problem of constructing a support for hypergraphs defined by connected subgraphs of a host graph. For a graph G=(V,E), let H be a set of connected subgraphs of G. Let the vertices of G be partitioned into two sets the \emph{terminals} b(V) and the \emph{non-terminals} r(V). We define a hypergraph on b(V), where each H∈H defines a hyperedge consisting of the vertices of b(V) in H. We also consider the problem of constructing a support for the \emph{dual hypergraph} - a hypergraph on H where each v∈b(V) defines a hyperedge consisting of the subgraphs in H containing v. In fact, we construct supports for a common generalization of the primal and dual settings called the \emph{intersection hypergraph}. As our main result, we show that if the host graph G has bounded genus and the subgraphs in H satisfy a condition of being \emph{cross-free}, then there exists a support that also has bounded genus. Our results are a generalization of the results of Raman and Ray (Rajiv Raman, Saurabh Ray: Constructing Planar Support for Non-Piercing Regions. Discret. Comput. Geom. 64(3): 1098-1122 (2020)). Our techniques imply a unified analysis for packing and covering problems for hypergraphs defined on surfaces of bounded genus. We also describe applications of our results for hypergraph colorings.