# On Hypergraph Supports

Rajiv Raman111Part of this work was done when the first author was at LIMOS,
Université Clermont Auvergne, and was partially supported by the French
government research program “Investissements d’Avenir” through the IDEX-ISITE
initiative 16-IDEX-0001 (CAP 20-25).
IIIT-Delhi, India.
<EMAIL_ADDRESS>Karamjeet Singh
IIIT-Delhi, India.
<EMAIL_ADDRESS>
###### Abstract

Let $\mathcal{H}=(X,\mathcal{E})$ be a hypergraph. A support is a graph $Q$ on
$X$ such that for each $E\in\mathcal{E}$, the subgraph of $Q$ induced on the
elements in $E$ is connected. In this paper, we consider hypergraphs defined
on a host graph. Given a graph $G=(V,E)$, with
$c:V\to\\{\mathbf{r},\mathbf{b}\\}$, and a collection of connected subgraphs
$\mathcal{H}$ of $G$, a primal support is a graph $Q$ on $\mathbf{b}(V)$ such
that for each $H\in\mathcal{H}$, the induced subgraph $Q[\mathbf{b}(H)]$ on
vertices $\mathbf{b}(H)=H\cap c^{-1}(\mathbf{b})$ is connected. A _dual
support_ is a graph $Q^{*}$ on $\mathcal{H}$ s.t. for each $v\in X$, the
induced subgraph $Q^{*}[\mathcal{H}_{v}]$ is connected, where
$\mathcal{H}_{v}=\\{H\in\mathcal{H}:v\in H\\}$. We present sufficient
conditions on the host graph and hyperedges so that the resulting support
comes from a restricted family.

We primarily study two classes of graphs: $(1)$ If the host graph has genus
$g$ and the hypergraphs satisfy a topological condition of being _cross-free_
, then there is a primal and a dual support of genus at most $g$. $(2)$ If the
host graph has treewidth $t$ and the hyperedges satisfy a combinatorial
condition of being _non-piercing_ , then there exist primal and dual supports
of treewidth $O(2^{t})$. We show that this exponential blow-up is sometimes
necessary. As an intermediate case, we also study the case when the host graph
is outerplanar. Finally, we show applications of our results to packing and
covering, and coloring problems on geometric hypergraphs.

##  1 Introduction

A hypergraph $(X,\mathcal{E})$ is defined by a set $X$ of elements and a
collection $\mathcal{E}$ of subsets of $X$. In this paper, we study the notion
of a _support_ for a hypergraph. A support is a graph $Q$ on $X$ s.t.
$\forall\;E\in\mathcal{E}$, the subgraph induced by $E$ in $Q$, $Q[E]$ is
connected. The notion of a support was introduced by Voloshina and Feinberg
[voloshina1984planarity] in the context of VLSI circuits. Since then, this
notion has found wide applicability in several areas, such as visualizing
hypergraphs [bereg2015colored, bereg2011red, brandes2010blocks,
brandes2012path, buchin2011planar, havet2022overlaying, hurtado2018colored],
in the design of networks [anceaume2006semantic, baldoni2007tera,
baldoni2007efficient, chand2005semantic, hosoda2012approximability,
korach2003clustering, onus2011minimum], and similar notions have been used in
the analysis of local search algorithms for geometric problems [Mustafa17,
BasuRoy2018, Cohen-AddadM15, krohn2014guarding, mustafa2010improved, RR18].

Any hypergraph clearly has a support - A complete graph on $X$ is a support.
The problem becomes interesting if we introduce a global constraint on the
graph that is in _tension_ with the _local_ connectivity requirement for each
hyperedge. In particular, we are interested in the restrictions on the
hypergraph that guarantees the existence of a support from a _sparse_ family
of graphs.

We can broadly classify sparse graphs into two categories - those that are
_easily decomposable_ , for example, graphs with sublinear sized balanced
separators222A graph has a sublinear sized balanced separator if there are
constants $\epsilon>0$, and $c>0$ and a set $S$ of size $O(|V|^{1-\epsilon})$
such that $G\setminus S$ contains two disconnected components $A$ and $B$ such
that $|A|,|B|\leq c|V|$. , and graphs that do not admit small separators, such
as _expanders_ [holberg1992decomposition]. Examples of the former are planar
graphs [lipton1979separator], graphs of bounded genus [gilbert1984separator],
graphs excluding a minor [alon1990separator], and more generally, graphs with
polynomially bounded $t$-shallow minors [nevsetvril2012sparsity]. The fact
that a family of graphs is _easily decomposable_ has been exploited to develop
faster algorithms, or algorithms with better approximation factors than in
general graphs. Some results that use this paradigm are [AW13,
DBLP:conf/focs/Arora97, Frederickson87, DBLP:journals/cpc/FoxP14,
lipton1980applications]. In a similar vein, one would like to develop a theory
of _easily decomposable_ hypergraphs, and exploit this notion algorithmically.
The existence of a sparse support for a hypergraph is such a notion.

In this paper, motivated by problems of packing and covering we study
hypergraphs defined on a sparse _host graph_. We show sufficient conditions
under which the hypergraph defined on this host graph has a sparse support,
and present applications of this result in the analysis of several packing,
covering and coloring problems.

##  2 Related Work

The notion of a planar analogue of a hypergraph was first suggested by Zykov
[zykov], who defined a hypergraph to be planar if there is a plane graph on
the elements of the hypergraph s.t. for each hyperedge, there is a bounded
face of the embedding containing only the elements of this hyperedge.
Equivalently, a hypergraph is _Zykov-planar_ iff its incidence bipartite graph
is planar. Voloshina and Feinberg [voloshina1984planarity] introduced the
notion of hypergraph planarity that is now called _a planar support_ in the
context of planarizing VLSI circuits (see the monograph by Feinberg et al.,
[feinberg2012vlsi] and references therein). Johnson and Pollak
[Johnson1987HypergraphPA] showed that the problem of deciding if a hypergraph
has a planar support is NP-hard.

Since then, several authors have studied the question of deciding if a
hypergraph admits a support from a restricted family of graphs. Tarjan and
Yannakakis [tarjan1984simple] showed that we can decide in linear time if a
hypergraph admits a tree support. Buchin et al. [buchin2011planar] showed
linear time algorithms to decide if a hypergraph admits a support that is a
path or a cycle, and a polynomial time algorithm to decide if a hypergraph
admits a support that is a tree with bounded degree. Further, the authors
sharpen the result of Johnson and Pollak [Johnson1987HypergraphPA] by showing
that deciding if a hypergraph admits a support that is a 2-outerplanar333A
graph is 2-outerplanar if the graph can be embedded in the plane such that the
vertices are on two concentric circles and removing all vertices of outer face
results in an outerplanar graph. graph is NP-hard. The notion of constructing
a support with the fewest number of edges, or with minimum maximum degree have
also been studied in [baldoni2007tera, onus2011minimum].

Another motivation for studying the existence of sparse supports, and the main
motivation for our work comes from the design and analysis of algorithms for
geometric hypergraphs. Chan and Har-Peled [ChanH12], and Mustafa and Ray
[mustafa2010improved] used the existence of a planar graph with a _simple
locality property_ to show that for pseudodisks (and more generally, simply
connected k-admissible regions444A set of connected bounded regions
$\mathcal{R}$ in the plane, each of whose boundary is a simple jordan curve is
$k$-admissible (for even $k$) if for any $R,R^{\prime}\in\mathcal{R}$,
$R\setminus R^{\prime}$ and $R^{\prime}\setminus R$ are connected, their
boundaries are in general position, and intersect each other at most $k$
times. If $k=2$, the regions are called pseudodisks.), a local search
algorithm yields a PTAS for the Independent Set problem, and the Hitting Set
problem, respectively. Their analyses rely on the existence of a graph that
satisfies the _simple locality property_ and is from a class that admits
sublinear separators. In such analysis, the main difficulty of showing whether
local search yields a PTAS lies in showing the existence of an appropriate
graph. The results of [ChanH12, mustafa2010improved] were extended by Basu-Roy
et al. [BasuRoy2018] who constructed the appropriate graphs corresponding to
the Set Cover, Dominating Set problem, and the Capacitated Packing problem.
Raman and Ray [RR18] generalized this further and gave a unified construction
which implied a planar support for general non-piercing regions in the plane
(not necessarily simply connected)555This includes disks, pseudodisks, unit
height-axis parallel rectangles, halfspaces, etc.. In
[DBLP:journals/dcg/RamanR22], it was shown that LP-rounding can be combined
with local search to obtain $(2+\epsilon)$-approximations for the problem of
hitting set and set cover with capacities for hypergraphs obtained from points
and pseudodisks. Besides packing and covering problems, the existence of a
planar support implies that the hypergraph is 4-colorable, a quesetion
considered by Keller and Smorodinsky [KellerS18] and Keszegh[Keszegh20].
Further hypergraph coloring questions were studied by Pálvölgyi and Kezegh
[DBLP:journals/jocg/KeszeghP19] and Ackerman et al. [ackerman2020coloring].
Ackerman et al. studied $ABAB$-free hypergraphs in [ackerman2020coloring] and
showed that these hypergraphs admit a representation with stabbed pseudodisks
and points in the plane. Their results are closely related to our results and
we discuss this connection in Section 11.

While there has been some progress on approximation algorithms for geometric
problems, the existing techniques are rather weak in that they can handle
basic questions in the plane, and the resulting algorithms are far from
practical. The two main motivations of this work are to extend the techniques
of [RR18] to higher dimensional surfaces, and to build techniques for proving
the existence of supports, an area that does is lacking in techniques
currently. Cabello and Gajser [CabelloG14] showed that Independent Set and
Vertex Cover admit a PTAS on graphs excluding a fixed minor, and Aschner et
al.,[DBLP:conf/walcom/AschnerKMY13] study some packing and covering problems
involving geometric non-planar graphs. In both these cases however, the
authors do not construct a support, and the existence of a graph satisfying
the desired locality properties is straightforward.

##  3 Preliminaries

A graph $G=(V,E)$ and a collection of subgraphs $\mathcal{H}$ of $G$ naturally
defines a hypergraph $(V(G),\\{V(H):H\in\mathcal{H}\\})$, where $V(H)=\\{v\in
V:v\in H\\}$. We call the tuple $(G,\mathcal{H})$ a _graph system_ , since we
will use the pair to define other hypergraphs. We primarily study two classes
of graphs: graphs that are 2-cell embedded in an orientable surface of genus
$g$ (i.e., each face of the embedding is homeomorphic to a disk), henceforth
called _embedded graphs_. We allow multi-edges and self-loops. The second
class of graphs we study are graphs of bounded treewidth. As an intermediate
case, we also study the setting where $G$ is an outerplanar graph.

For a vertex $v\in V(G)$, we use $N_{G}(v)$ to denote the neighbours of $v$ in
$G$ (or just $N(v)$ if $G$ is clear from context), and we use $N_{G}[v]$ (or
$N[v]$) to denote $N(v)\cup\\{v\\}$. We use $e\sim v$ to denote an edge $e$
incident on vertex $v$. For $S\subseteq V$, we use $G[S]$ to denote the
subgraph of $G$ induced on $S$. We use
$\mathcal{H}_{v}=\\{H\in\mathcal{H}:v\in H\\}$ to we let
$0pt(v)=|\mathcal{H}_{v}|$.

Let $c:V\to\\{\mathbf{r},\mathbf{b}\\}$ be an arbitrary coloring of the
vertices of $G$ with two colors. Let $\mathbf{b}(V)$ and $\mathbf{r}(V)$
denote respectively $c^{-1}(\mathbf{b})$ and $c^{-1}(\mathbf{r})$. We also
refer to the vertices in $\mathbf{b}(V)$ as _blue vertices_ and the vertices
in $\mathbf{r}(V)$ as _red vertices_.

A _primal support_ for $(G,\mathcal{H})$ is a graph $Q$ on $\mathbf{b}(V)$
s.t. $\forall\;H\in\mathcal{H}$, $Q[\mathbf{b}(H)]$ is connected666Note that
we cannot simply project each $H$ on $\mathbf{b}(V)$ as the resulting
subgraphs may not be connected in $G.$. The system $(G,\mathcal{H})$ also
defines a _dual hypergraph_ $(\mathcal{H},\\{\mathcal{H}_{v}\\}_{v\in V(G)})$.
A _dual support_ is a graph $Q^{*}$ on $\mathcal{H}$ s.t. $\forall\;v\in
V(G)$, $Q^{*}[\mathcal{H}_{v}]$ is connected777 To make the definition
symmetric, we could have considered a coloring
$c:\mathcal{H}\to\\{\mathbf{r},\mathbf{b}\\}$, and required that
$Q^{*}[\mathcal{H}^{\mathbf{b}_{v}}]$ be connected only for each $v\in V$,
where $\mathcal{H}^{\mathbf{b}_{v}}=\\{H\in\mathcal{H}:v\in H\mbox{ and
}c(H)=\mathbf{b}\\}$. However, this problem reduces to constructing a dual
support restricted to the hypergraphs
$\mathcal{H}^{\mathbf{b}}=\\{H\in\mathcal{H}:c(H)=\mathbf{b}\\}$. Therefore,
in the dual setting, it is sufficient to study the uncolored version of the
problem.. When constructing the dual support, we can assume without loss of
generality that there are no _containments_ , i.e.,
$\forall\;H,H^{\prime}\in\mathcal{H},\;H\setminus H^{\prime}\neq\emptyset$ and
$H^{\prime}\setminus H\neq\emptyset$.

######  Proposition 1.

For a system $(G,\mathcal{H})$ if $\mathcal{H}^{\prime}\subseteq\mathcal{H}$
is a maximal subset of $\mathcal{H}$ such that
$\forall\;H,H^{\prime}\in\mathcal{H}^{\prime}$, $H\setminus
H^{\prime}\neq\emptyset$ and $H^{\prime}\setminus H\neq\emptyset$, then from a
dual support $Q^{\prime}$ on $\mathcal{H}^{\prime}$, we can obtain a dual
support $Q^{*}$ on $\mathcal{H}$ s.t. $Q^{*}$ has the same genus as
$Q^{\prime}$, and $Q^{*}$ has the same treewidth as $Q^{\prime}$.

###### Proof.

Consider a partial order $(\mathcal{H},\prec)$, where $H\prec H^{\prime}$ if
$H\subseteq H^{\prime}$. If all elements in $\mathcal{H}$ are pairwise
incomparable, we are done. Otherwise, let $H\subseteq H^{\prime}$ for some
$H,H^{\prime}\in\mathcal{H}$. We can assume wlog that $H^{\prime}$ is the
immediate successor of $H$ wrt $\prec$. Let
$\mathcal{H}_{1}=\mathcal{H}\setminus\\{H\\}$. Then $\mathcal{H}^{\prime}$ is
also maximal for $\mathcal{H}_{1}$. By induction, the system
$(G,\mathcal{H}_{1})$ has a dual support $Q_{1}^{*}$ embedded in $\Sigma$ s.t.
$Q_{1}^{*}$ is obtained from a dual support $Q^{\prime}$ of
$\mathcal{H}^{\prime}$ and that $tw(Q_{1}^{*})=tw(Q^{\prime})$.

We claim that the graph $Q^{*}$ obtained from $Q_{1}^{*}$ by adding a vertex
for $H$ and attaching it to an arbitrary subgraph that is an immediate
successor of $H$, i.e., _a parent_ of $H$ in $\prec$ via a single edge yields
a support for $(G,\mathcal{H})$. For each vertex $v\in V(G)$, the induced
subgraph $Q_{1}^{*}[\mathcal{H}_{1_{v}}]$, on the subgraphs in
$\mathcal{H}_{1}$ containing $v$, is connected. Consider the parent
$H^{\prime}$ of $H$ in the partial order. For any vertex $v\in V(G)$ such that
$v\in H$, it follows that $v\in H^{\prime}$. Thus, adding the edge
$\\{H,H^{\prime}\\}$ guarantees that $Q^{*}[\mathcal{H}_{v}]$ is connected for
each $v\in V$. Clearly, $Q^{*}$ is also embeddable on $\Sigma$. A similar
argument implies that $Q^{*}$ has the same treewidth as $Q^{\prime}$. ∎

Let $\mathcal{H}$ and $\mathcal{K}$ be two sets of connected subgraphs of a
graph $G$, and let $(G,\mathcal{H},\mathcal{K})$ denote the _intersection
hypergraph_ $(\mathcal{H},\\{\mathcal{H}_{K}\\}_{K\in\mathcal{K}})$, where
$\mathcal{H}_{K}=\\{H\in\mathcal{H}:K\cap H\neq\emptyset\\}$. A support for
$(G,\mathcal{H},\mathcal{K})$ is then a graph $\tilde{Q}=(\mathcal{H},F)$ s.t.
$\forall K\in\mathcal{K}$, $\tilde{Q}[\mathcal{H}_{K}]$ is connected.
$\tilde{Q}$ is called the _intersection support_. The notion of an
intersection hypergraph generalizes both the primal and dual hypergraphs
defined above \- taking the vertices of $G$ as the singleton sets of
$\mathcal{H}$ for the primal, and taking the vertices of $G$ as the singleton
sets of $\mathcal{K}$ for the dual, respectively.

Our goal is to consider restrictions of hypergraphs so that the support is
guaranteed to be from a restricted family of graphs. To that end, we introduce
a notion of cross-free hypergraphs and non-piercing hypergraphs.

######  Definition 2 (Reduced graph).

Let $(G,\mathcal{H})$ be a graph system with $G$, an embedded graph. For any
two subgraphs $H,H^{\prime}\in\mathcal{H}$, the _reduced graph_
$R_{G}(H,H^{\prime})$ (or just $R(H,H^{\prime})$ if $G$ is clear from context)
is the graph obtained by contracting all edges, both of whose end-points lie
in $H\cap H^{\prime}$, where multi-edges and self-loops are retained.

Note that if $G$ can be embedded in a surface $\Sigma$, then so can be
$R_{G}(H,H^{\prime})$.

######  Definition 3 (Cross-free at $v$).

A graph system $(G,\mathcal{H})$ with $G$ embedded in an oriented surface, is
cross-free at a vertex $v\in V(G)$ if for any two subgraphs
$H,H^{\prime}\in\mathcal{H}_{v}$, the following holds: Let $\tilde{v}$ be the
image of $v$ in the reduced graph $R(H,H^{\prime})$. Then, there are no 4
edges $e_{i}=\\{\tilde{v},v_{i}\\}$ in $R(H,H^{\prime})$, $i=1,\ldots,4$
incident to $\tilde{v}$ in cyclic order around $\tilde{v}$, s.t.
$v_{1},v_{3}\in H\setminus H^{\prime}$, and $v_{2},v_{4}\in
H^{\prime}\setminus H$.

If there exist $H,H^{\prime}\in\mathcal{H}$ s.t. $H$ and $H^{\prime}$ are not
cross-free at $v$, we say that $H$ and $H^{\prime}$ are _crossing_ at $v$.
$(G,\mathcal{H})$ is _cross-free_ if there exists an embedding of $G$ s.t.
$(G,\mathcal{H})$ is cross-free at each $v\in V(G)$. Note that for cross-free
system, we implicitly assume $\mathcal{H}$ is a collection of connected
subgraphs.

An intersection hypergraph $(G,\mathcal{H},\mathcal{K})$ is cross-free if both
$(G,\mathcal{H})$ and $(G,\mathcal{K})$ are cross-free. Note that we can have
$H\in\mathcal{H}$, $K\in\mathcal{K}$ that are crossing. Finally, we use the
term $(G,\mathcal{H})$ is a cross-free system of genus $g$ or the term
$(G,\mathcal{H},\mathcal{K})$ is an intersection system of genus $g$ to mean
that the host graph $G$ has genus $g$.

We need one more definition, namely that of $abab$-free hypergraphs before we
move on to non-piercing subgraphs. An equivalent notion, namely $ABAB$-free
hypergraphs was studied by Ackerman et al. [ackerman2020coloring], where the
elements of the hypergraph are placed in a linear order instead of a cyclic
order.

######  Definition 4 ($abab$-free).

A hypergraph $(X,\mathcal{H})$ is said to be $abab$-free if there is a cycle
$C$ on $X$ s.t. there are no four vertices $x_{1},x_{2},x_{3},x_{4}$ in cyclic
order around $C$ s.t. $x_{1},x_{3}\in H\setminus H^{\prime}$, and
$x_{2},x_{4}\in H^{\prime}\setminus H$.

######  Definition 5 (Non-piercing).

A graph system $(G,\mathcal{H})$ with $\mathcal{H}$ a collection of subgraphs
of $G$ is non-piercing if each $H\in\mathcal{H}$ is connected and for any two
subgraphs $H,H^{\prime}\in\mathcal{H}$, $H\setminus H^{\prime}$ induces a
connected subgraph of $H$, and $H^{\prime}\setminus H$ induces a connected
subgraph of $H^{\prime}$.

We say $(G,\mathcal{H})$ is a non-piercing system of treewidth $t$ to mean it
is a non-piercing system defined on a host graph $G$ whose treewidth is $t$.

Note that non-piercing is a purely combinatorial notion, and unlike the cross-
free property above, it does not require an embedding of the graph. If
$\exists\;H,H^{\prime}\in\mathcal{H}$ s.t. either the indued subgraph
$H\setminus H^{\prime}$ of $H$ or the induced subrgaph $H^{\prime}\setminus H$
of $H^{\prime}$ is not connected, then $H$ and $H^{\prime}$ are _piercing_.
Otherwise, $(G,\mathcal{H})$ is a non-piercing system.

Given a graph $G=(V,E)$, a tree-decomposition of $G$ is a pair
$(T,\mathcal{B})$, where $T$ is a tree and $\mathcal{B}$ is a collection of
_bags_ \- subgraphs of $G$ indexed by the nodes of $T$888Throughout the paper,
we use the term _node_ to refer to the elements of $V(T)$ and _vertices_ to
refer to the elements of $V(G)$., that satisfies the following properties:
$(i)$ For each edge, $\\{u,v\\}\in E(G)$ there is a bag $B\in\mathcal{B}$ that
contains both $u$ and $v$. $(ii)$ For each vertex $v\in v(G)$, the set of bags
containing $v$ induce a connected sub-tree of $T$.

The _width_ of a tree-decomposition is defined as $\max_{x\in V(T)}|B_{x}|-1$.
The treewidth of $G$ is the minimum width of a tree-decomposition of $G$,
denoted by $tw(G)$. See [bodlaender1998partial] for additional properties of a
tree-decomposition.

An outerplanar graph is a graph that can be embedded in the plane such that
all vertices lie on the outer face. It is a well-known fact that an
outerplanar graph has treewidth at most 2 and that an embedding of an
outerplanar graph can be obtained in polynomial time. If $(G,\mathcal{H})$ is
a (cross-free/non-piercing) system where $G$ is an outerplanar graph, we call
it an _outerplanar (cross-free/non-piercing)_ system.

##  4 Contribution

The existence of a support from a family with sublinear sized balanced
separators has been at the heart of the analysis of PTASes for several packing
and covering problems with geometric hypergraphs starting with the work of
Chan and Har-Peled [ChanH12] and Mustafa and Ray [mustafa2010improved]. Raman
and Ray in [RR18] unified earlier constructions of a support for non-piercing
regions in the plane.

A natural question is whether we can extend these results from the plane to
surfaces of higher genus or general graphs. The main contribution of our paper
is a generalization of the results of [RR18]. We study two settings: When the
host graph has bounded genus, and when the host graph has bounded treewidth.
While the results for bounded genus graphs roughly follow the proof outline of
[RR18], several new ideas are required for the proofs to go through. In
particular, it turns out that for graphs of bounded genus, the non-piercing
condition is insufficient for the existence of sparse supports. We introduce
the notion of _cross-free_ subgraphs and show that if $(G,\mathcal{H})$ is a
cross-free system and $G$ has genus $g$, then the primal, dual and
intersection supports have genus at most $g$. Dealing with the cross-free
condition on graphs is more challenging than in the geometric case. In
particular, we show:

  1. 1.

If $(G,\mathcal{H})$ is a cross-free system of genus $g$, there exist primal
and dual supports of genus at most $g$.

  2. 2.

If $(G,\mathcal{H},\mathcal{K})$ is a cross-free intersection system of genus
$g$, there exists an intersection support of genus at most $g$.

Next, we study outerplanar graphs. Here, we show that there is a subtle
difference between the primal and dual settings:

  1. 1.

Let $(G,\mathcal{H})$ be a cross-free outerplanar system. Then, there exists
an outerplanar primal support on $V(G)$.

  2. 2.

Let $(G,\mathcal{H})$ be a _non-piercing_ outerplanar system. Then, there
exists an outerplanar dual support $Q^{*}$ on $\mathcal{H}$. In this case, we
show that the cross-free condition is insufficient.

Finally, we consider the case where the host graphs have bounded treewidth.
Here, we show the following:

  1. 1.

If $(G,\mathcal{H})$ is non-piercing system of treewidth $t$, it has both
primal and dual supports of treewidth $O(2^{t})$.

  2. 2.

There exist non-piercing systems of treewidth $t$ s.t. any primal or dual
support has treewidth $\Omega(2^{t})$.

The rest of the paper is organized as follows. In Section 5, we contrast non-
piercing graph systems with cross-free set systems. In Sections 6 and 7, we
present our results for cross-free systems of bounded genus. In Section 8 we
present our results for outerplanar host graphs. In Section 9, we present
results for non-piercing systems of bounded treewidth. We describe some
applications in Section 11, and conclude in Section 12 with open questions.

##  5 Non-piercing and Cross-free systems

The cross-free condition implies the non-piercing condition in the plane, but
they are incomparable in higher genus surfaces. We start with the following
result that shows that if a system is non-piercing in the plane, it is cross-
free.

######  Theorem 6.

Let $(G,\mathcal{H})$ be a planar non-piercing system Then, $(G,\mathcal{H})$
is cross-free.

###### Proof.

Consider an embedding of $G$ in the plane. Abusing notation, let $G$ also
denote the embedding of $G$ in the plane. If $(G,\mathcal{H})$ is crossing,
there are two subgraphs $H,H^{\prime}\in\mathcal{H}$ and a vertex $x$ in
$R_{G}(H,H^{\prime})$ that lies in $H\cap H^{\prime}$ and four neighbors
$x_{1},\ldots,x_{4}$ in cyclic order around $x$ s.t. $x_{1},x_{3}\in
H\setminus H^{\prime}$ and $x_{2},x_{4}\in H^{\prime}\setminus H$. It cannot
be that both $x_{1}=x_{3}$, and $x_{2}=x_{4}$ without violating planarity. So
assume without loss of generality that $x_{2}\neq x_{4}$.

Since $H$ is connected, there is an $x_{1}$-$x_{3}$ path in
$R_{G}(H,H^{\prime})$ that lies in $H$. Let $P$ be any $x_{1}$-$x_{3}$ path
lying in $H$. Similarly, let $P^{\prime}$ be any $x_{2}$-$x_{4}$ path that
lies in $H^{\prime}$. Observe that $P\cup\\{x_{1},x\\}\cup\\{x,x_{3}\\}$
induces a jordan curve with $x_{2}$ and $x_{4}$ on either side of it. Thus,
$P^{\prime}$ and $P$ cross at a vertex that lies in $H\cap H^{\prime}$, which
implies $H^{\prime}\setminus H$ is not connected and thus, $\mathcal{H}$ is
piercing. ∎

Note that the reverse implication does not hold. It is easy to construct
examples of graph systems in the plane that are cross-free, but are piercing.
Consider the graph system consisting of a graph $K_{1,4}$ embedded in the
plane, with central vertex $v$, and spokes $\\{a,b,c,d\\}$ in cyclic order.
Let $H$ and $H^{\prime}$ be two subgraphs where $H$ is the graph induced on
$\\{v,a,b\\}$ and $H^{\prime}$ is the graph induced on $\\{v,c,d\\}$. Then,
$H$ and $H^{\prime}$ are cross-free, but neither $H\setminus H^{\prime}$ nor
$H^{\prime}\setminus H$ is connected.

The proof of Theorem 6 relies on the Jordan curve theorem, and hence the
corresponding statement does not hold for surfaces of higher genus. For
example, let $G$ be the torus grid graph $T_{n,n}=C_{n}\Box
C_{n}$[weisstein2016torus]. The subgraphs are the $n$ non-contractible cycles
perpendicular to the hole, and the $n$ non-contractible cycles parallel to the
hole. Each vertex of the graph belongs to exactly two subgraphs forcing them
to be adjacent in the dual support, and thus the dual support is $K_{n,n}$
which is not embeddable on the torus for large enough $n$. However, we show in
Theorem 17 that non-crossing is a sufficient condition for a system
$(G,\mathcal{H})$ on a graphs of genus $g$ to have a
(primal/dual/intersection) support of genus at most $g$.

##  6 Bounded Genus graphs

In this section we consider the setting where the host graph has bounded
genus. We start in Section 6.1 where we define the Vertex Bypassing operation
that we require to obtain the primal, dual and intersection support.

###  6.1 Vertex Bypassing

Vertex Bypassing (VB$(v)$999Short for Vertex Bypassing) takes a cross-free
system $(G,\mathcal{H})$ as input and _simplifies_ the system around a vertex
$v$ of $G$. Since $(G,\mathcal{H})$ is cross-free, we assume that we are given
a cross-free embedding of $G$ on a surface of genus $g$. VB$(v)$ is defined as
follows:

######  Definition 7 (VB$(v)$).

Let $G$ be embedded in an oriented surface $\Sigma$. Let
$N(v)=(v_{1},\ldots,v_{k},v_{1})$ be the cyclic order of vertices around $v$.

  1. 1.

Subdivide each edge $\\{v,v_{i}\\}$ by a vertex $u_{i}$. By connecting
consecutive vertices $u_{i},u_{i+1}$ (with indices taken $\mod k$) by a simple
arc not intersecting the edges of $G$, construct a cycle
$C=(u_{1},\ldots,u_{k},u_{1})$ s.t. the resulting graph $G^{\prime\prime}$
remains embedded in $\Sigma$. Remove $v$.

  2. 2.

$\forall\;H\in\mathcal{H}_{v}$ s.t. $\\{v,v_{i}\\}\in H$, let $H^{\prime}$
denote the subgraph of $G^{\prime\prime}$ induced by
$(H\setminus\\{v\\})\cup\\{u_{i}\\}$. Let
$\mathcal{H}^{\prime}_{v}=\\{H^{\prime}:H\in\mathcal{H}_{v}\\}$. Let
$\mathcal{H}^{\prime}=(\mathcal{H}\setminus\mathcal{H}_{v})\cup\mathcal{H}^{\prime}_{v}$
(Note that the subgraphs in $\mathcal{H}^{\prime}_{v}$ may not be connected).

  3. 3.

Add a set $D$ of non-intersecting101010We use the term non-intersecting to
mean internally non-intersecting chords in $C$ so that
$\forall\;H\in\mathcal{H}^{\prime}$, $H$ induces a connected subgraph in
$C\cup D$, and $\mathcal{H}^{\prime}$ remains cross-free.

Let $(G^{\prime},\mathcal{H}^{\prime})$ be the resulting system.

It is easy to see that the graph $G^{\prime}$ obtained from $G$ is also
embedded in $\Sigma$ as each operation preserves the embedding. We show in
Lemmas 10 and Lemma 11 that we can implement Step 10 of VB$(.)$.

At the end of Step 1, since we remove vertex $v$, the subgraphs in
$\mathcal{H}^{\prime}_{v}$ in $G^{\prime\prime}$ may be disconnected. Each
$H\in\mathcal{H}^{\prime}_{v}$, $H\cap C$ is a set of one or more disjoint
_runs_ (a consecutive sequence) of vertices of $C$. Since $\mathcal{H}$ is
cross-free, the induced sub-hypergraph $(V(C),\\{H\cap
C:H\in\mathcal{H}^{\prime}_{v}\\})$ is $abab$-free.

We now show that we can add a set $D$ of non-intersecting chords in $C$ s.t.
$\forall\;H\in\mathcal{H}^{\prime}_{v}$, $H\cap(C\cup D)$ induces a connected
subgraph of $G^{\prime}$. By construction, the interior of $C$ is homeomorphic
to an open disk (after removing $v$), and therefore the vertices of $C$ can be
seen arranged on a circle with $u_{1},\ldots,u_{k},u_{1}$ in the clockwise
order. For a pair of vertices $u_{i},u_{j}$ with $i<j$ (indices $\mod k$) we
use $[u_{i},u_{j}]$ to denote the arc from $u_{i}$ to $u_{j}$ in the direction
of $C$. Thus, $[u_{i},u_{j}]$ consists of the vertices
$u_{i},u_{i+1},\ldots,u_{j-1},u_{j}$, and arc $[u_{j},u_{i}]$ consists of the
vertices $u_{j},u_{j+1},\ldots,u_{i-1},u_{i}$. We also use $(u_{i},u_{j})$ to
denote the open arc that does not include the end-vertices $u_{i}$ and
$u_{j}$. Similarly, we use $(u_{i},u_{j}]$ to denote the half-open arc that
does not include $u_{i}$, but includes $u_{j}$.

The addition of a chord $d=\\{u_{i},u_{j}\\}$ divides $C$ into two open arcs -
$(u_{i},u_{j})$ and $(u_{j},u_{i})$. The chord $d$ _blocks_ a subgraph
$H\in\mathcal{H}^{\prime}_{v}$ if both open arcs contain a run of $H$, and
neither end-point of $d$ is contained in $H$. Such a chord $d$ is called a
_blocking chord_. If $d$ does not block any subgraph in
$\mathcal{H^{\prime}}_{v}$, it is called a _non-blocking_ chord. We show in
Lemma 8 that there always exists a non-blocking chord $d$ that connects two
disjoint runs of some subgraph $H\in\mathcal{H}^{\prime}_{v}$. This is
sufficient to guarantee the existence of a set $D$ of non-blocking, non-
intersecting chords s.t. for each $H\in\mathcal{H}^{\prime}_{v}$, $H$ induces
a connected subgraph of $G^{\prime}$ in $C\cup D$, as we can recursively add
non-blocking chords to the two smaller cycles created by adding $d$ to $C$
until all subgraphs are connected. We show this in Lemma 9.

######  Lemma 8.

Let $C$ be a cycle and let $\mathcal{K}$ be a collection of $abab$-free
subgraphs on $C$. Then, for some $K\in\mathcal{K}$, there exists a non-
blocking chord joining two disjoint runs of $K$.

###### Proof.

Assume wlog that each subgraph $K\in\mathcal{K}$ induces at least two runs in
$C$, and no two subgraphs contain the same subset of vertices of $C$. Define a
partial order $\prec_{C}$ on $\mathcal{K}$, where for
$K,K^{\prime}\in\mathcal{K}$, $K\prec_{C}K^{\prime}$ iff $K\cap C\subset
K^{\prime}\cap C$. Let $K_{0}\in\mathcal{K}$ be a minimal subgraph with
respect to the order $\prec_{C}$.

Let $K_{0}^{0},\ldots,K_{0}^{q}$ denote the runs of $K_{0}$. We let $A$ denote
the run $K_{0}^{0}$ and let $B=\cup_{i=1}^{q}K_{0}^{i}$. Wlog, we assume $C$
is oriented such that $A$ lies in the lower semi-circle of $C$ and that $B$
lies in the upper semi-circle of $C$, where the runs
$K_{0}^{1},\ldots,K_{0}^{q}$ appear in counter-clockwise order. Let
$a_{0},\ldots,a_{r}$ denote the vertices of $A$ in clockwise order and let
$b_{0},\ldots,b_{s}$ denote the vertices of $B$ in counter-clockwise order.
See Figure 1(a).

We show that there is a chord $d$ from a vertex in $A$ to a vertex in $B$ that
is non-blocking. In order to do so, we start with the chord
$d_{0}=a_{0}b_{0}$, and construct a sequence of chords until we either find a
non-blocking chord, or we end up with the chord $d_{k}=a_{r}b_{s}$, which will
turn out to be non-blocking. Having constructed chords $d_{0},\ldots,d_{i-1}$,
where $d_{i-1}=a_{\ell}b_{j}$, $d_{i}$ will be either the chord
$a_{\ell}b_{j^{\prime}}$ or $a_{\ell^{\prime}}b_{j}$, where $j^{\prime}>j$ and
$\ell^{\prime}>\ell$.

Next, we describe the construction of the chords. Each chord $d$ we construct
satisfies the following invariant: If $K$ is a subgraph blocked by a chord
$d=a_{\ell}b_{j}$, then

  1. $(i)$

$K$ is contained in $K_{0}$ in the arc $(a_{\ell},b_{j})$, and

  2. $(ii)$

there is a vertex $k\in K\setminus K_{0}$ in the arc $(b_{j},a_{\ell})$.

Let $d_{0}$ denote the chord $a_{0}b_{0}$. If $d_{0}$ is non-blocking, we are
done. Otherwise, if $K\in\mathcal{K}$ is blocked by $d_{0}$, there is a vertex
$k\in K$ that lies in $(b_{0},a_{0})$. Since $(b_{0},a_{0})$ does not contain
a vertex of $K_{0}$, this implies $k\in K\setminus K_{0}$, and hence $d_{0}$
satisfies condition $(ii)$ of the invariant. Since we assumed the subgraphs
$\mathcal{K}$ are $abab$-free, this implies that any vertex of $K$ in arc
$(a_{0},b_{0})$ is contained in $K_{0}$. This ensures that condition $(i)$ of
the invariant is satisfied by $d_{0}$.

Having constructed $d_{0}=a_{0}b_{0},\ldots,d_{i-1}=a_{\ell}b_{j}$, each of
which satisfy conditions $(i)$ and $(ii)$ of the invariant, we construct
$d_{i}$ as follows: We simultaneously scan the vertices of $B$ in counter-
clockwise order from $b_{j}$, and the vertices of $A$ in clockwise order from
$a_{\ell}$ until we find the first vertex $x$ that belongs to a subgraph
blocked by $d_{i-1}$. Let $K_{i}$ denote this subgraph. If
$x=b_{j^{\prime}}\in B$, we set $d_{i}=a_{\ell}b_{j^{\prime}}$. Otherwise,
$x=a_{\ell^{\prime}}\in A$, and we set $d_{i}=a_{\ell^{\prime}}b_{j}$. Assume
without loss of generality that $d_{i}=a_{\ell}b_{j^{\prime}}$ (the other case
is similar).

((a)) Ordering the vertices of $K$ in sets $A$ and $B$. Here,
$A=\\{a_{0},\ldots,a_{r}\\}$ and $B=\\{b_{0},\ldots,b_{s}\\}$.

((b)) Adding chords between $A$ and $B$. Crossing among $u,b_{j^{\prime}},v$
and $w$ if $K\setminus K_{0}\neq\emptyset$ in $(a_{\ell},b_{j^{\prime}}).$

Figure 1: All red vertices are in $K_{0}$ and no black vertex is in $K_{0}$.

If $d_{i}$ is a non-blocking chord, we are done. Otherwise, let $K$ denote a
subgraph blocked by $d_{i}$. Then, both the arcs $(a_{\ell},b_{j^{\prime}})$
and $(b_{j^{\prime}},a_{\ell})$ contain a run of $K$. We now show that $d_{i}$
satisfies the invariant. Most of the work will go in showing that $d_{i}$
satisfies condition $(i)$ of the invariant. We show this by contradiction - If
$d_{i}$ does not satisfy invariant $(i)$, we will exhibit a pair of subgraphs
violating the $abab$-free property.

Suppose $d_{i}$ does not satisfy condition $(i)$ of the invariant, there is a
vertex $u\in K\setminus K_{0}$ that lies in $(a_{\ell},b_{j^{\prime}})$. Since
$d_{i-1}$ satisfies both the conditions of the invariant, the subgraph $K_{i}$
blocked by $d_{i-1}$ is contained in $K_{0}$ in $(a_{\ell},b_{j})$. Since
$(a_{\ell},b_{j^{\prime}})\subset(a_{\ell},b_{j})$, it implies $u\not\in
K_{i}$, and thus $u\in K\setminus K_{i}$. By construction of $d_{i}$, the
vertex $b_{j^{\prime}}\in K_{i}$, and since $d_{i}$ blocks $K$,
$b_{j^{\prime}}\not\in K$. Thus, $b_{j^{\prime}}\in K_{i}\setminus K$.

Now, we claim that $K$ is not blocked by $d_{i-1}$. To see this, since
$d_{i-1}$ satisfies condition $(i)$ of the invariant, for any subgraph
$K^{\prime}$ blocked by $d_{i-1}$, we have that $K^{\prime}\subseteq K_{0}$ in
$(a_{\ell},b_{j})$. Since $(a_{\ell},b_{j^{\prime}})\subset(a_{\ell},b_{j})$,
combined with the facts that $u\in K\setminus K_{0}$ and that $u$ lies in
$(a_{\ell},b_{j^{\prime}})$ implies that $K$ is not blocked by $d_{i-1}$.
Since $K$ is blocked by $d_{i}$, it follows that there is a vertex $v$ of $K$
in the arc $(b_{j^{\prime}},b_{j}]$. However, no vertex in this arc lies in
$K_{i}$, since $b_{j^{\prime}}$ was the first vertex encountered that was
contained in a subgraph blocked by $d_{i-1}$ when traversing the vertices of
$B$ in counter-clockwise order from $b_{j}$. Therefore, $v\in K\setminus
K_{i}$.

Finally, since $d_{i-1}$ satisfies condition $(ii)$ of the invariant, it
implies that there is a vertex $w\in K_{i}\setminus K_{0}$ that lies in
$(b_{j},a_{\ell})$. However, since $u\in K\setminus K_{0}$, and $u$ lies in
$(a_{\ell},b_{j^{\prime}})$, $K\subseteq K_{0}$ in $(b_{j^{\prime}},a_{\ell})$
since the arrangement is $abab$-free. However, since
$(b_{j},a_{\ell})\subset(b_{j^{\prime}},a_{\ell})$, this implies $w\not\in K$.
Therefore, $w\in K_{i}\setminus K$. See Figure 1(b).

From the above arguments it follows that the subgraphs $K$ and $K_{i}$ are not
$abab$-free, as witnessed by the sequence of vertices $u,b_{j^{\prime}},v$ and
$w$, a contradiction. Thus, $d_{i}$ satisfies condition $(i)$ of the
invariant. The fact that $d_{i}$ satisfies condition $(ii)$ of the invariant
follows from the fact that $K_{0}$ is minimal. Otherwise, $K\subseteq K_{0}$
in $(a_{\ell},b_{j^{\prime}})$ and in $(b_{j^{\prime}},a_{\ell})$, and
therefore $K\subset K_{0}$.

Since the set of chords is finite, the sequence of chords constructed either
ends in a non-blocking chord, or we end up with the chord $d=a_{r}b_{s}$. We
claim that $d$ must be a non-blocking chord. Suppose $d$ blocks a subgraph
$K$. Then, $(a_{r},b_{s})$ contains a vertex $u\in K\cap K_{0}$, as $d$
satisfies invariant $(i)$ and $(ii)$. However, $(a_{r},b_{s})$ does not
contain a vertex in $K_{0}$. Therefore, $d$ must be a non-blocking chord. ∎

######  Lemma 9.

Let $C$ be a cycle and let $\mathcal{K}$ be an $abab$-free collection of
subgraphs of $C$. Then, we can add a set $D$ of non-intersecting chords to $C$
s.t. each $K\in\mathcal{K}$ induces a connected subgraph of $C\cup D$.

###### Proof.

Let $n_{K}$ denote the number of disjoint runs of $K$ on $C$. Let

$\displaystyle cost(C,\mathcal{K})=\sum_{K\in\mathcal{K}}(n_{K}-1)$

If $cost(C,\mathcal{K})=0$, then every subgraph $K\in\mathcal{K}$ consists of
one run, and therefore $C\cap K$ is connected for each $K\in\mathcal{K}$, and
$D=\emptyset$ suffices.

Suppose the lemma holds for all $(C^{\prime},\mathcal{K}^{\prime})$ with
$cost(C^{\prime},\mathcal{K}^{\prime})<N$. Given an instance with cost
$(C,\mathcal{K})=N$, by Lemma 8, there is a non-blocking chord $d=\\{x,y\\}$
joining two disjoint runs of some subgraph $K\in\mathcal{K}$.

The chord $d=\\{x,y\\}$ divides the cycle $C$ into two arcs, $[x,y]$, and
$[y,x]$. We construct two disjoint sub-problems on the cycles $C_{\ell}$ and
$C_{r}$ obtained from $C$, where $C_{\ell}$ is obtained by adding the edge
$\\{x,y\\}$ to the arc $[y,x]$, and $C_{r}$ is obtained by adding the edge
$\\{x,y\\}$ to the arc $[x,y]$. The subgraphs in $C_{\ell}$ and $C_{r}$ are
respectively those induced by $\mathcal{K}$, namely
$\mathcal{K}_{\ell}=\\{K\cap C_{\ell}:K\in\mathcal{K}\\}$, and
$\mathcal{K}_{r}=\\{K\cap C_{r}:K\in\mathcal{K}\\}$. Note that
$\mathcal{K}_{\ell}$ and $\mathcal{K}_{r}$ are $abab$-free on $C_{\ell}$ and
$C_{r}$, respectively. Let $n^{\ell}_{K}$ and $n^{r}_{K}$ denote respectively,
the number of runs of $K$ in $C_{\ell}$ and in $C_{r}$. Since
$n^{\ell}_{K}<n_{K}$ and $n^{r}_{K}<n_{K}$, it follows that
$cost(C_{r},\mathcal{K}_{r})<cost(C,\mathcal{K})$ and
$cost(C_{\ell},\mathcal{K}_{\ell})<cost(C,\mathcal{K})$.

Hence, by the inductive hypothesis on $C_{\ell},\mathcal{K}_{\ell}$ and
$C_{r},\mathcal{K}_{r}$ respectively, there exists a set of non-intersecting
chords $D_{\ell}$ s.t. each $K\in\mathcal{K}_{\ell}$ induces a connected
subgraph of $C_{\ell}\cup D_{\ell}$. Similarly, there exists a set of non-
intersecting chords $D_{r}$ s.t. for each $K\in\mathcal{K}_{r}$, induces a
connected subgraph of $C_{r}\cup D_{r}$. It follows that $D=D_{\ell}\cup
D_{r}\cup d$ is a set of non-crossing chords such that $K\in\mathcal{K}$
induces a connected subgraph of $(C\cup D)$. ∎

######  Lemma 10.

Let $(G,\mathcal{H})$ be a cross-free system with $G$ an embedded graph.
Suppose we apply VB$(v)$ to vertex $v\in V(G)$. Then, each subgraph $H$ in
$(G^{\prime},\mathcal{H}^{\prime})$ is connected.

###### Proof.

Let $C$ be the cycle added on the subdividing vertices around vertex $v$.
Since $(G,\mathcal{H})$ is cross-free, the subgraphs $\\{H\cap
C:H\in\mathcal{H}^{\prime}_{v}\\}$ satisfy the $abab$-free property on $C$.
Therefore, by Lemma 9, there is a collection $D$ of non-intersecting chords in
$D$ s.t. each subgraph in $\mathcal{H}^{\prime}_{v}$ induces a connected
subgraph of $C\cup D$. Hence, each subgraph $H\in\mathcal{H}^{\prime}$ is a
connected subgraph of $G^{\prime}$ since each $H\in\mathcal{H}_{v}$ is
modified only in the vertices of subdivision. ∎

######  Lemma 11.

Let $(G,\mathcal{H})$ be a cross-free system. Let
$(G^{\prime},\mathcal{H}^{\prime})$ be the system obtained after applying
vertex bypassing at a vertex $v\in V(G)$. Then,
$(G^{\prime},\mathcal{H}^{\prime})$ is cross-free.

###### Proof.

By Lemma 10, each subgraph $H^{\prime}\in(G^{\prime},\mathcal{H}^{\prime})$ is
connected. We will show that the system is cross-free. Let
$N(v)=\\{v_{1},\ldots,v_{k}\\}$. Let $S(v)=\\{u_{1},\ldots,u_{k}\\}$ where
$u_{i}$ subdivides edge $\\{v,v_{i}\\}$.

Assume $(G^{\prime},\mathcal{H}^{\prime})$ is crossing. Then, there are two
subgraphs $H_{1}$ and $H_{2}$ in $\mathcal{H}$ that correspond respectively,
to subgraphs $H^{\prime}_{1}$ and $H^{\prime}_{2}$ in $\mathcal{H}^{\prime}$,
and a crossing vertex $x_{C^{\prime}}$ of
$R_{G^{\prime}}(H^{\prime}_{1},H^{\prime}_{2})$. Here, $C^{\prime}$ is the
connected component of $G^{\prime}[H^{\prime}_{1}\cap H^{\prime}_{2}]$ that is
contracted to $x_{C^{\prime}}$ in
$R_{G^{\prime}}(H^{\prime}_{1},H^{\prime}_{2})$. Let $x_{1},x_{2},x_{3},x_{4}$
be the four neighbors encountered in cyclic order around $x_{C^{\prime}}$ s.t.
$x_{1},x_{3}\in H^{\prime}_{1}\setminus H^{\prime}_{2}$ and $x_{3},x_{4}\in
H^{\prime}_{2}\setminus H^{\prime}_{1}$.

Suppose $C^{\prime}\cap N(v)=\emptyset$. Since $G^{\prime}$ is obtained from
$G$ by modifying only $N(v)$, it implies $(G,\mathcal{H})$ is crossing. Hence,
we can assume that $C^{\prime}\cap N(v)\neq\emptyset$. Let $v_{1}\in
C^{\prime}$. Since
$\mathcal{H}_{e}\subseteq\mathcal{H}_{v_{1}}\cap\mathcal{H}_{v}$ in
$(G,\mathcal{H})$, where $e=\\{v,v_{1}\\}$, it follows that if $u_{1}\not\in
C^{\prime}$, then $v\not\in H_{1}\cap H_{2}$. Therefore, there does not exist
vertices $u$ and $u^{\prime}$ in $S(v)$ s.t. $u\in H^{\prime}_{1}$ and
$u^{\prime}\in H^{\prime}_{2}$. Since $x_{C^{\prime}}$ is a crossing vertex,
replacing each occurrence of a vertex in $\\{x_{1},\ldots,x_{4}\\}\cap S(v)$
by $v$ we obtain a crossing vertex in $R_{G}(H_{1},H_{2})$ implying
$(G,\mathcal{H})$ is crossing, a contradiction.

Finally, consider the case that $v\in H_{1}\cap H_{2}$. There are again two
cases to consider. If no neighbor of $v$ is contained in $H_{1}\cap H_{2}$.
Then, the component of $G[H_{1}\cap H_{2}]$ containing $v$ is a singleton.
This component is removed in $G^{\prime}[H^{\prime}_{1}\cap H^{\prime}_{2}]$
since $v$ is removed. So $v\in H_{1}\cap H_{2}$, and there is a vertex, say
$v_{1}\in N(v)$ s.t. $v_{1}\in C^{\prime}$. Since $H^{\prime}_{1}$ and
$H^{\prime}_{2}$ are crossing at $x_{C^{\prime}}$, if $N(x_{C^{\prime}})\cap
S(v)=\emptyset$, then if $C$ is the component containing $v_{1}$ in
$G[H_{1}\cap H_{2}]$, and $x_{C}$ is the vertex in $R_{G}(H_{1},H_{2})$
obtained by contracting $C$, then $H_{1}$ and $H_{2}$ are crossing at $v$.
Otherwise, if $S(v)\cap N(x_{C^{\prime}})\neq\emptyset$, then replacing each
occurrence of $u_{i}$ in $N(x_{C^{\prime}})$ by $v_{i}$ yields a crossing
vertex in $R_{G}(H_{1},H_{2})$, a contradiction. ∎

##  7 Construction of Supports

In this section, we show that for cross-free systems on a graph of genus $g$,
there exist primal, dual and intersection supports of genus at most $g$. While
the existence of an intersection support implies the existence of the primal
and dual supports, we use the dual support and techniques from the primal
support in order to construct the intersection support, and hence present
these first.

We obtain a polynomial time algorithm to construct a primal support when an
embedding of the graph system $(G,\mathcal{H})$ is given. However, we are
unable to prove a similar result for a dual support or intersection support,
and this is an intriguing open question.

###  7.1 Primal Support

In this section, we show that for a cross-free system $(G,\mathcal{H})$ with
$c:V\to\\{\mathbf{r},\mathbf{b}\\}$, where $G$ has genus $g$, there is a
primal support $Q$ of genus at most $g$, and that $Q$ can be constructed in
polynomial time in $|G|$ and $|\mathcal{H}|$ if a cross-free embedding of $G$
is given.

######  Theorem 12.

Let $(G,\mathcal{H})$ be a cross-free system of genus $g$, with
$c:V(G)\to\\{\mathbf{r},\mathbf{b}\\}$. Then, there exists a primal support
$Q$ of genus at most $g$ on $\mathbf{b}(V)$. Further, if a cross-free
embedding of $G$ is given, $Q$ can be constructed in time polynomial in $|G|$
and $|\mathcal{H}|$.

###### Proof.

If $\mathbf{r}(V)=\emptyset$, $G$ itself is a support. Since $(G,\mathcal{H})$
is cross-free, there exists a cross-free embedding of $G$ in a surface of
genus $g$. Consider such an embedding of $(G,\mathcal{H})$. We abuse notation
slightly, and use $G$ to also refer to an embedding of $G$. Let $v$ be a
maximal vertex in $\mathbf{r}(V)$, i.e., for each $v\in\mathbf{r}(V)$ s.t.
$e\sim v$, $0pt(e)<0pt(v)$. We apply VB$(v)$. For $i=1,\ldots,\deg(v)$, let
$u_{i}$ be the vertices added by VB$(v)$ subdividing edges incident on $v$.
Set $c(u_{i})=\mathbf{r}$, $\forall\;i=1,\ldots,\deg(v)$. Since $v$ was
maximal, it follows that $0pt(u_{i})<0pt(v)$, for all $i=1,\ldots,k$. Further,
no $u_{i}$ is maximal since $0pt(u_{i})\leq 0pt(v_{i})$, where $u_{i}$
subdivides the edge $\\{v,v_{i}\\}$, and they remain non-maximal when we
bypass other maximal vertices in $\mathbf{r}(V)$. To see this, note that if
$v_{i}$ is maximal, the vertex $u^{\prime}_{i}$ subdividing
$\\{v_{i},u_{i}\\}$ satisfies
$\mathcal{H}_{u^{\prime}_{i}}=\mathcal{H}_{u_{i}}$. Thus, by Lemmas 9 and 10,
the resulting system is cross-free and we have one fewer maximal red vertex in
the resulting system. We repeatedly apply vertex bypassing to each maximal
vertex in $\mathbf{r}(V)$ until we obtain the system
$(G^{\prime},\mathcal{H}^{\prime})$ where no vertex in
$\mathbf{r}(V(G^{\prime}))$ is maximal.

Since no vertex in $\mathbf{r}(V(G^{\prime}))$ is maximal in
$(G^{\prime},\mathcal{H}^{\prime})$, it follows that for each
$v\in\mathbf{r}(V(G^{\prime}))$ there is an edge $e=\\{v,u\\}$, $e\sim v$ s.t.
$\mathcal{H}_{e}=\mathcal{H}_{v}$, which implies
$\mathcal{H}_{v}\subseteq\mathcal{H}_{u}$. For each
$v\in\mathbf{r}(V(G^{\prime}))$, choose such a neighbor $u$ of $v$ arbitrarily
and orient the edge $\\{v,u\\}$ from $v$ to $u$.

Let $D$ denote the directed subgraph on $V(G^{\prime})$ induced by these
directed arcs. Observe that in $D$, each vertex has out-degree at most 1, and
for an arc $(v,u)$ in $D$, we have $\mathcal{H}_{v}\subseteq\mathcal{H}_{u}$,
which implies $D$ is acyclic. Thus, D is a forest. By construction, $D$
satisfies the following properties: In each tree $T$ of D, $(i)$ the arcs of
$T$ are directed towards the root of $T$, $(ii)$ all vertices in $T$ except
the root are red, and $(iii)$ the root of $T$ is blue. Further, for each arc
$(v,u)$ of $D$, we have $\mathcal{H}_{v}\subseteq\mathcal{H}_{u}$. Thus,
contracting each forest to its root yields the desired support $Q$.

Finally, to see that $Q$ can be constructed in polynomial time, note that
there are at most $|V(G)|$ maximal vertices in $\mathbf{r}(V)$. If a cross-
free embedding of $G$ is given, then for a maximal vertex
$v\in\mathbf{r}(V(G))$, VB$(v)$ can be implemented in polynomial time by Lemma
10, and moreover, we obtain a cross-free embedding of the resulting graph
system. Further, no new vertex added during VB$(v)$ becomes maximal on
applying further vertex bypassing operations. Thus, while the size of the
graph grows with each vertex bypassing operation, we apply the vertex
bypassing operation at most $|V(G)|$ times. Finally, constructing $D$ and
contracting the arcs in $D$ to obtain $Q$ can clearly be done in polynomial
time. ∎

###  7.2 Dual Support

In this section, we show that for a cross-free system on a graph of genus $g$,
there is a dual support of genus at most $g$. Unlike the primal case however,
we are unable to prove that the algorithm implied in the proof of Theorem 13
runs in polynomial time, even if a cross-free embedding of the system is
given.

######  Theorem 13.

Let $(G,\mathcal{H})$ be a cross-free system of genus $g$. Then, there exists
a dual support $Q^{*}$ on $\mathcal{H}$ of genus at most $g$.

###### Proof.

We assume by Proposition 1 that there are no containments in $\mathcal{H}$.
Since $(G,\mathcal{H})$ is cross-free, there exists a cross-free embedding of
$G$ in a surface of genus $g$. Consider such an embedding of
$(G,\mathcal{H})$. We abuse notation slightly and also refer to the embedded
graph by $G$. We prove by induction on $(d,n_{d})$, where $d$ is the maximum
depth of a vertex in $G$ and $n_{d}$ is the number of vertices of depth $d$.
We need the following definition: An edge $\\{u,v\\}\in E(G)$ is said to be a
_special edge_ if $\mathcal{H}_{u}\cap\mathcal{H}_{v}=\emptyset$. Let
$Spl_{\mathcal{H}}(E)$ be the set of special edges in $E(G)$. We need a
stronger inductive hypothesis, namely given $(G,\mathcal{H})$ there is a
support with the _special edge property_ , i.e., there is a dual support
$Q^{*}$ on $\mathcal{H}$ s.t. for each $e=\\{u,v\\}\in Spl_{\mathcal{H}}(E)$,
there is an edge between some $H\in\mathcal{H}_{u}$ and
$H^{\prime}\in\mathcal{H}_{v}$ in $Q^{*}$.

If $d=1$, i.e., the maximum depth of a vertex is 1, then, no two subgraphs
$H,H^{\prime}\in\mathcal{H}$ share a vertex of $G$. Therefore, contracting
each $H\in\mathcal{H}$ to a vertex, we obtain a support $Q^{*}$ of genus $g$
satisfying the special edge property, and we are done.

So suppose $d>1$. Let $v$ be a vertex of maximum depth in $G$. Then, we claim
$v$ must be a maximal vertex, i.e., $0pt(v)>0pt(e)$ $\forall\;e\sim v$. If
not, there is an edge $e=\\{u,v\\}\in E_{v}$ such that
$\mathcal{H}_{e}=\mathcal{H}_{v}$. Since $v$ has maximum depth, the other end-
point of $e$, namely $u$ satisfies $\mathcal{H}_{u}=\mathcal{H}_{v}$. Hence,
contracting $e$, we obtain a system $(G/e,\mathcal{H})$ with smaller $n_{d}$.
It is easy to see that $(G/e,\mathcal{H})$ is cross-free. Thus, by the
inductive hypothesis there is a support $Q^{*}$ for $(G/e,\mathcal{H})$ since
we assumed there are no containments in $\mathcal{H}$. It is easy to check
that $Q^{*}$ is a support for $(G,\mathcal{H})$.

Therefore, we can assume that for each $e\sim v$,
$\mathcal{H}_{e}\subset\mathcal{H}_{v}$. Now, we apply VB$(v)$ to obtain the
system $(G^{\prime},\mathcal{H}^{\prime})$. By Lemmas 10 and 11,
$(G^{\prime},\mathcal{H}^{\prime})$ is cross-free, and
$(d^{\prime},n^{\prime}_{d})\prec(d,n_{d})$, where $d^{\prime}$ and
$n^{\prime}_{d}$ are respectively, the depth of a maximum depth vertex, and
the number of vertices of maximum depth in
$(G^{\prime},\mathcal{H}^{\prime})$. By the inductive hypothesis, there is a
support $Q_{1}^{*}$ for $(G^{\prime},\mathcal{H}^{\prime})$ satisfying the
special edge property. We show that $Q_{1}^{*}$ is also a support for
$(G,\mathcal{H})$. For each $u\neq v\in V(G)$, it follows from the inductive
hypothesis that the support property is satisfied. For
$i=1,\ldots,u_{\deg(v)}$, let $u_{i}$ be the vertex subdividing the edges
$\\{v,v_{i}\\}$ in $G$ added in VB$(v)$ and let $C$ denote the cycle on
$u_{1},\ldots,u_{\deg(v)}$ added in VB$(v)$.

Since we assumed $\mathcal{H}$ as no containments, we have
$\cup_{i=1}^{\deg(v)}\mathcal{H}^{\prime}_{u_{i}}=\mathcal{H}_{v}$. If none of
the edges of $C$ are in $Spl_{\mathcal{H}^{\prime}}(E)$, then
$\mathcal{H}_{v}$ is connected since adjacent vertices of $C$ share at least
one subgraph. On the other hand, if an edge $e=\\{u_{i},u_{i+1}\\}$ of $C$ is
in $Spl_{\mathcal{H}^{\prime}}(E)$, by the inductive hypothesis, at least one
subgraph of $\mathcal{H}^{\prime}_{u_{i}}$ and one subgraph of
$\mathcal{H}^{\prime}_{u_{i+1}}$ is connected. It follows that
$\mathcal{H}_{v}$ is connected and thus $Q^{*}=Q^{*}_{1}$ is the desired
support. ∎

###  7.3 Intersection Support

We now show that the intersection system $(G,\mathcal{H},\mathcal{K})$ has an
intersection support of genus at most $g$ if $G$ has genus $g$. The proof
builds on the construction of primal and dual supports, but is more involved.

Given the system $(G,\mathcal{H},\mathcal{K})$, we define the _intersection
graph_ $G_{K}$ for each $K\in\mathcal{K}$ as the graph with vertex set
$\mathcal{H}_{K}$, i.e., the subgraphs in $\mathcal{H}$, intersecting $K$, and
an edge between two subgraphs $H,H^{\prime}\in\mathcal{H}_{K}$ if and only if
they share a vertex in $K$. We start with the special case where $G_{K}$ is
connected for each $K\in\mathcal{K}$.

######  Lemma 14.

Let $(G,\mathcal{H},\mathcal{K})$ be a cross-free intersection system. If
$\forall\;K\in\mathcal{K}$, the intersection graph
$G_{K}=(\mathcal{H}_{K},E_{K})$ is connected, then a dual support for
$(G,\mathcal{H})$ is an intersection support for
$(G,\mathcal{H},\mathcal{K})$.

###### Proof.

Let $Q^{*}$ denote a dual support for $(G,\mathcal{H})$. Consider an arbitrary
subgraph $K\in\mathcal{K}$. Since $G_{K}$ is connected, for any two subgraphs
$H,H^{\prime}\in\mathcal{H}_{K}$ there is a path
$P=H=H_{0},H_{1},H_{2},\ldots,H_{k}=H^{\prime}$ in $G_{K}$ from $H$ to
$H^{\prime}$. By definition of $G_{K}$, for $i=0,\ldots,k-1$, there is a
vertex $v\in K\cap H_{i}\cap H_{i+1}$. Since $Q^{*}$ is a dual support for
$(G,\mathcal{H})$, there is a path from $H_{i}$ to $H_{i+1}$ in $Q^{*}$ that
consists of only the subgraphs containing $v$, and hence in $\mathcal{H}_{K}$.
The concatenation of these paths yields a path from $H$ to $H^{\prime}$ in
$Q^{*}$. Since $H$ and $H^{\prime}$ were arbitrary subgraphs from
$\mathcal{H}_{K}$ for any $K\in\mathcal{K}$, it follows that $Q^{*}$ is a
support for $(G,\mathcal{H},\mathcal{K})$. ∎

If the intersection graph $G_{K}$ is not connected for some $K\in\mathcal{K}$,
we modify the arrangement and augment $\mathcal{H}$ with _dummy_ subgraphs
$\mathcal{F}$ such that the intersection graph $G_{K}$ with subgraphs
$\mathcal{H}\cup\mathcal{F}$ is connected. We then construct a support
$Q^{\prime}$ on $\mathcal{H}\cup\mathcal{F}$, and then carefully remove the
vertices of $\mathcal{F}$ to obtain a graph on $\mathcal{H}$ that is a support
for the original intersection system. But before we can add dummy subgraphs,
we need to simplify the arrangement. We show how this is done in Lemma 15. In
Lemma 16, we show how we can add dummy subgraphs to satisfy the conditions of
Lemma 14, and then we show how to construct a support for the original system.

A vertex of $G$ that is contained only in subgraphs in $\mathcal{K}$ but not
in any subgraph in $\mathcal{H}$ is called a $\mathcal{K}$-vertex. Recall that
a vertex $v$ is maximal if $\mathcal{K}_{e}\subset\mathcal{K}_{v}$ for all
${e}\sim v$. In the following, we repeatedly apply vertex bypassing to a
maximal $\mathcal{K}$-vertex of maximum depth. Note that a maximum depth
$\mathcal{K}$-vertex need not be maximal in this case.

######  Lemma 15.

Let $(G,\mathcal{H},\mathcal{K})$ be a cross-free intersection system of genus
$g$. Then, we can modify the arrangement to a cross-free arrangement
$(G^{\prime},\mathcal{H},\mathcal{K}^{\prime})$ so that $G^{\prime}$ has genus
$g$, no $\mathcal{K}$-vertex of $G^{\prime}$ is maximal, and a support
$Q^{\prime}$ for $(G^{\prime},\mathcal{H},\mathcal{K}^{\prime})$ is a support
for $(G,\mathcal{H},\mathcal{K})$.

###### Proof.

We assume a cross-free embedding of $(G,\mathcal{H})$ is given, and with a
slight abuse of notation use $G$ to also refer to the embedded graph. Let $d$
denote the maximum depth of a maximal $\mathcal{K}$-vertex, and let $n_{d}$
denote the number of maximal $\mathcal{K}$-vertices of depth $d$. We
repeatedly choose a maximal $\mathcal{K}$-vertex $v$ of maximum depth and
apply VB$(v)$. The operation VB$(v)$ modifies the graph $G$ and the subgraphs
in $\mathcal{K}$, but does not modify any subgraph in $\mathcal{H}$, as $v$ is
a $\mathcal{K}$-vertex. Let $(G^{\prime},\mathcal{H},\mathcal{K}^{\prime})$
denote the new arrangement. Let $d^{\prime}$ and $n^{\prime}_{d^{\prime}}$
denote respectively, the maximum depth of a maximal $\mathcal{K}$-vertex, and
the number of maximal $\mathcal{K}$-vertices in
$(G^{\prime},\mathcal{H},\mathcal{K}^{\prime})$ of depth $d^{\prime}$. It
follows that $(d^{\prime},n^{\prime}_{d^{\prime}})$ is lexicographically
smaller than $(d,n_{d})$. Since the newly added vertices and edges are not
contained in any subgraph $H\in\mathcal{H}$, it follows that $\mathcal{H}$
remains cross-free in $G^{\prime}$. Further, the fact that
$\mathcal{K}^{\prime}$ remains cross-free follows from Lemmas 10 and 11. Thus,
$(G^{\prime},\mathcal{H},\mathcal{K}^{\prime})$ remains cross-free. Since the
underlying hypergraph $(\mathcal{H},\\{\mathcal{H}_{K}\\}_{K\in\mathcal{K}})$
is not modified, a support $Q^{\prime}$ for
$(G^{\prime},\mathcal{H},\mathcal{K}^{\prime})$ is also a support for
$(G,\mathcal{H},\mathcal{K})$. ∎

######  Lemma 16.

Let $(G,\mathcal{H},\mathcal{K})$ be a cross-free intersection system of genus
$g$ s.t. no $\mathcal{K}$-vertex is maximal. Then, we can add a collection of
_dummy subgraphs_ $\mathcal{F}$ s.t. $\mathcal{H}\cup\mathcal{F}$ remains
cross-free, and a support $\tilde{Q}$ for $(G,\mathcal{H},\mathcal{K})$ can be
obtained from the dual support $Q^{*}$ for the system
$(G,\mathcal{H}\cup\mathcal{F})$.

###### Proof.

Given the system $(G,\mathcal{H},\mathcal{K})$ such that no
$\mathcal{K}$-vertex is maximal, we first describe how we modify the
arrangement and add dummy subgraphs to obtain the arrangement
$(G^{\prime},\mathcal{H}^{\prime},\mathcal{K}^{\prime})$. As before, we assume
a cross-free embedding of $G$ is given, i.e., an embedding where both
$\mathcal{H}$ and $\mathcal{K}$ are simultaneously cross-free. While
constructing the new arrangement, we also construct an auxiliary graph $D$ on
the vertices of $G^{\prime}$ that will be helpful in constructing a support
for $(G,\mathcal{H},\mathcal{K})$.

An edge $e\in E(G)$ is a $\mathcal{K}$-edge if $\mathcal{K}_{e}\neq\emptyset$
and $\mathcal{H}_{e}=\emptyset$. For each $\mathcal{K}$-edge $e=\\{u,v\\}$, we
can assume that either $u$ or $v$ is a $\mathcal{K}$-vertex. Otherwise, we can
subdivide $e$ with a vertex $v_{e}$. Since
$\mathcal{K}_{v_{e}}=\mathcal{K}_{e}\subseteq\mathcal{K}_{u}\cap\mathcal{K}_{v}$,
it follows that $v_{e}$ is not a maximal $\mathcal{K}$-vertex. Thus, in the
following, we assume that for each $\mathcal{K}$-edge, one of its end-points
is a $\mathcal{K}$-vertex.

We first subdivide each $\mathcal{K}$-edge $e=\\{u,v\\}$ with a vertex
$v_{e}$. Note that either $u$ or $v$ is a $\mathcal{K}$-vertex. Let
$G^{\prime}$ denote the resulting graph. Observe that for each
$\mathcal{K}$-vertex $v$, each edge incident on $v$ is subdivided. For each
$\mathcal{K}$-vertex $v$, let $N(v)$ denote its neighbors in $G$, and let
$S(v)$ be the set of vertices subdividing edges incident on $v$. Next, we add
a dummy subgraph $F_{v}$ corresponding to each $\mathcal{K}$-vertex $v$ in $G$
spanning $\\{v\\}\cup S(v)$. Finally, for each edge $\\{v,v^{\prime}\\}$
incident on $v$ in $G$, we extend the subgraphs in $\mathcal{H}_{v^{\prime}}$
to contain the vertex subdividing the edge $\\{v,v^{\prime}\\}$. Let
$\mathcal{F}$ denote the dummy subgraphs added and let
$\mathcal{H}^{\prime\prime}$ denote the modified subgraphs in $\mathcal{H}$,
and let $\mathcal{H}^{\prime}=\mathcal{H}^{\prime\prime}\cup\mathcal{F}$.

By construction, there is no $\mathcal{K}$-vertex and no $\mathcal{K}$-edge in
$(G,\mathcal{H}^{\prime},\mathcal{K})$. Hence, for each $K\in\mathcal{K}$ the
graph $G_{K}$ is connected. Therefore, by Theorem 13, there is a dual support
$Q^{*}$ on $\mathcal{H}^{\prime}$ for $(G^{\prime},\mathcal{H}^{\prime})$. By
Lemma 14, $Q^{*}$ is also a support for
$(G^{\prime},\mathcal{H}^{\prime},\mathcal{K})$.

We obtain a support for $(G,\mathcal{H},\mathcal{K})$ from $Q^{*}$ as follows:
We maintain a directed graph $D$ on $\mathcal{H}^{\prime}$. Since we assumed
that no $\mathcal{K}$-vertex in $G$ is maximal, each $\mathcal{K}$-vertex $v$
is adjacent to a _full edge_ $e=\\{v,v^{\prime}\\}\sim v$, i.e.,
$\mathcal{K}_{e}=\mathcal{K}_{v}$. Let $u_{e}$ be the vertex subdividing $e$
in $G^{\prime}$. Since $Q^{*}$ is a dual support for
$(G^{\prime},\mathcal{H}^{\prime})$, the subgraphs containing $u_{e}$ is
connected. Since
$\mathcal{H}^{\prime}_{e}\subseteq\mathcal{H}^{\prime}_{v^{\prime}}$, $F_{v}$
is adjacent to a subgraph $H$ in $\mathcal{H}^{\prime}$ containing
$v^{\prime}$. We add an arc in $D$ from $F_{v}$ to $H$.

By construction, each dummy subgraph in $D$ has out-degree 1. If
$(F_{v},F_{v^{\prime}})$ is an arc in $D$, then
$\mathcal{K}_{v}\subseteq\mathcal{K}_{v^{\prime}}$. Thus, $D$ is acyclic, and
hence a forest s.t. each tree in the forest is rooted at a subgraph of
$\mathcal{H}^{\prime\prime}$, and all other vertices correspond to dummy
subgraphs. We obtain a support $\tilde{Q}$ on $\mathcal{H}$ by contracting the
subgraphs corresponding to each tree in $D$ to its root. We claim that
$\tilde{Q}$ is the desired support. Let $F$ be a dummy subgraph. For any
$K\in\mathcal{K}$, if $F$ intersects $K$ and $(F,F^{\prime})$ is an arc in
$D$, then $K$ intersects $F^{\prime}$ and thus the root of the tree containing
$F$ intersects $K$. Hence, $\tilde{Q}$ is the desired support. ∎

We are now ready to prove the main theorem of this section.

######  Theorem 17.

Let $(G,\mathcal{H},\mathcal{K})$ be an intersection system of genus $g$.
Then, there exists an intersection support $\tilde{Q}$ on $\mathcal{H}$ of
genus at most $g$.

###### Proof.

If for each $K\in\mathcal{K}$, the intersection graph
$G_{K}=(\mathcal{H}_{K},E_{K})$ is connected, from Lemma 14, we obtain a
support of genus at most $g$. Otherwise, by Lemma 15, we obtain a cross-free
system $(G^{\prime},\mathcal{H},\mathcal{K}^{\prime})$ such that no
$\mathcal{K}$-vertex is maximal, and a support for
$(G^{\prime},\mathcal{H},\mathcal{K}^{\prime})$ is a support for the original
system. Finally, by Lemma 16, we obtain a support for
$(G^{\prime},\mathcal{H},\mathcal{K}^{\prime})$, and thus a support for
$(G,\mathcal{H},\mathcal{K})$, and the resulting support has genus at most
$g$. ∎

##  8 Outerplanar Graphs

In this section, consider the case when $G$ is outerplanar. We assume $G$ is
embedded in the plane in the natural manner with $C$ denoting the outer face.

######  Theorem 18.

Let $(G,\mathcal{H})$ be an outerplanar cross-free system, with
$c:V\to\\{\mathbf{r},\mathbf{b}\\}$. Then, there is a support $Q$ on
$\mathbf{b}(V)$ i.e. $Q[\mathbf{b}(H)]$ is connected for each
$H\in\mathcal{H}$. If a cross-free embedding is given, then an outerplanar
support can be computed in time polynomial in $|V(G)|,|\mathcal{H}|$.

###### Proof.

If $\mathbf{r}(V)=\emptyset$, $G$ itself is the desired support. Otherwise,
let $C^{\prime}$ be a cycle on $\mathbf{b}(V)$ in the same order as in the
outer face of $G$. Wlog, let each $H\in\mathcal{H}$ induce a disjoint
collection of runs on $C^{\prime}$. It is easy to see that the collection of
induced subgraphs $\\{H\cap C^{\prime}\\}_{H\in\mathcal{H}}$ is _abab-free_ on
$C^{\prime}$. By Lemma 9, there is a collection of non-intersecting chords $D$
connecting all the runs of $H$ for each subgraph $H\in\mathcal{H}$. Then
$Q=C^{\prime}\cup D$ is the desired support.

The proof of Lemma 8, gives a polynomial time algorithm to add a non-blocking
diagonal. For a fixed subgraph $H\in\mathcal{H}$, we try adding one of at most
$\binom{n}{2}$ diagonals, where $n=|V(G)|$. For each choice, to check that it
is non-blocking, we take $(|\mathcal{H}|)$ time to check if the given diagonal
blocks a subgraph. Hence, we find a non-blocking diagonal in
$O(n^{2}|\mathcal{H}|)$. A maximal outerplanar graph has $n-3$ diagonals, and
therefore the running time is $O(n^{3}|\mathcal{H}|)$. ∎

We show an example of a cross-free system $(G,\mathcal{H})$ that does not
admit an outerplanar dual support. Let $G$ be an asteroidal triple graph with
vertex set $\\{1,2,\ldots 6\\}$. Let $\mathcal{H}$ be a family of cross-free
subgraphs induced by the vertex sets $\\{1,2,3\\},\\{3,4,5\\},\\{5,6,1\\}$ and
$\\{2,4,6\\}$, as shown in Figure 2(a). The support for the dual hypergraph is
$K_{4}$ which is not outerplanar. A natural question is the following: If
$(G,\mathcal{H})$ is a non-piercing system, and $G$ is a tree, is there a
support that is a tree? We show that the answer to this question is negative
in both the primal and dual settings. For the primal setting, consider the
graph $K_{1,3}$ with $v$ being the central vertex colored red, with spokes
$v_{1},v_{2},v_{3}$ colored blue. We put three subgraphs $H_{1},H_{2},H_{3}$,
where $H_{i}=\\{v_{i},v,v_{i+1}\mod 3\\}$. It is easy to see that the primal
support is a triangle. The same example without colors on the vertices shows
that the dual support is also a triangle.

We now show that if $\mathcal{H}$ is non-piercing and $G$ is an outerplanar
graph, then $(G,\mathcal{H})$ admits an outerplanar dual support. We start
with the following definition:

######  Definition 19 ($axax$-free).

Let $(C,\mathcal{H})$ be a graph system where $C$ is a cycle and $\mathcal{H}$
is a collection of (not necessarily connected) subgraphs of $C$. Then,
$(C,\mathcal{H})$ is $axax$-fee if for any two subgraphs
$H,H^{\prime}\in\mathcal{H}$, there are no four vertices
$a_{1},x_{1},a_{2},x_{2}$ in cyclic order around $C$ s.t. $a_{1},a_{2}\in
H\setminus H^{\prime}$ and $x_{1},x_{2}\in H^{\prime}$.

######  Lemma 20.

Let $(G,\mathcal{H})$ be a non-piercing outerplanar graph system. Then,
$(C,\mathcal{H})$ is $axax$-free, where $C$ is the cycle defining the outer
face of $G$.

###### Proof.

Since $H^{\prime}$ is connected, $G$ contains a path between $x_{1}$ and
$x_{2}$ that lies in $H^{\prime}$. Consider any path $P^{\prime}$ in
$H^{\prime}$ between $x_{1}$ and $x_{2}$. Since $a_{1},a_{2}\not\in
H^{\prime}$, $P^{\prime}$ does not contain $a_{1}$ or $a_{2}$. Since $H$ is
connected, there is a path between $a_{1}$ and $a_{2}$ that lies in $H$. By
the Jordan curve theorem, any path $P$ in $H$ between $a_{1}$ and $a_{2}$
intersects any path $P^{\prime}$ in $H^{\prime}$ between $x_{1}$ and $x_{2}$
as shown in Figure 2(b). Since $G$ is outerplanar, $P$ and $P^{\prime}$
intersect at a vertex of $G$. But, this implies that $P$ does not lie in
$H\setminus H^{\prime}$, or equivalently, that $H\setminus H^{\prime}$ is not
connected, violating the assumption that the subgraphs are non-piercing. ∎

######  Corollary 21.

Let $(G,\mathcal{H})$ be a non-piercing outerplanar system. Then, for any
$H\in\mathcal{H}$, any chord $d$ whose end-points are in $H$ is non-blocking.

###### Proof.

This follows directly from Lemma 20. ∎

((a)) Cross-free Asteroidal with the only dual support $K_{4}$.

((b)) Crossing caused by $a_{1},x_{1},a_{2},x_{2}$ sequence in outerplanar
graph. Here, $a$ and $x$ are some vertices of $H\setminus H^{\prime}$ and
$H^{\prime}$ respectively.

Figure 2:

Now we can obtain the result for the dual support.

######  Theorem 22.

Let $(G,\mathcal{H})$ be a non-piercing outerplanar system. Then, there is an
outerplanar dual support $Q^{*}$ on $\mathcal{H}$. Further, an outerplanar
support can be computed in time polynomial in $|\mathcal{H}|$ and $|V(G)|$.

###### Proof.

By Proposition 1, we can assume there is no containment in $\mathcal{H}$. By
Lemma 20, $(C,\mathcal{H})$ is $axax$-free. For $H\in\mathcal{H}$, let $n_{H}$
denote the number of runs of $H$ on $C$, and let
$N(C,\mathcal{H})=\sum_{H\in\mathcal{H}}(n_{H}-1)$. We prove by induction on
$N(C,\mathcal{H})$ that if $(C,\mathcal{H})$ is $axax$-free, there is an
outerplanar support on $\mathcal{H}$.

If $N(C,\mathcal{H})=0$, each subgraph consists of a single run. We claim that
a cycle on $\mathcal{H}$ yields a support: Let $v_{1},\ldots,v_{n}$ be the
cyclic order of vertices on $C$. Traversing $C$ in clockwise order, we obtain
a cyclic order on the subgraphs ordered on the last vertex of their run. Let
$Q^{*}$ be the cycle on $\mathcal{H}$ in this order. Since we assumed there is
no containment in $\mathcal{H}$, for any $v\in V(C)$, the subgraphs in
$\mathcal{H}_{v}$ appear consecutively in $Q^{*}$, and thus induce a connected
subgraph of $Q^{*}$. Hence, $Q^{*}$ is a support.

Suppose for any cycle $C^{\prime}$ and subgraphs $\mathcal{H}^{\prime}$ such
that $(C^{\prime},\mathcal{H}^{\prime})$ is $axax$-free and
$N(C^{\prime},\mathcal{H}^{\prime})<N$, there is an outerplanar support on
$\mathcal{H}^{\prime}$. Consider $(C,\mathcal{H})$ with $N(C,\mathcal{H})=N$.
For $H\in\mathcal{H}$ with $n_{H}>1$, a chord $d$ is a _good chord_ if it
connects the last vertex of a run of $H$ with the first vertex of the next run
of $H$ along $C$. Its length $\ell(d)$ is the number of vertices along $C$
between its end-points. A good chord of minimum length, denoted $d_{H}$ is the
_critical chord_ of $H$.

Let $H=\arg\min_{H\in\mathcal{H}}\ell(d_{H})$, breaking ties arbitrarily. Let
$d_{H}=\\{u_{1},u_{2}\\}$. $d_{H}$ partitions $C$ into two open arcs
$\alpha_{1}=(u_{1},u_{2})$, and $\alpha_{2}=(u_{2},u_{1})$. Since $d_{H}$ is a
critical chord of $H$, either $\alpha_{1}\cap H=\emptyset$, or $\alpha_{2}\cap
H=\emptyset$. Assume the former. We obtain two induced sub-problems on
$C_{R}=\alpha_{1}\cup d_{H}$ and $C_{L}=\alpha_{2}\cup d_{H}$. By Corollary
21, $d$ is non-blocking. A subgraph $H^{\prime}\in\mathcal{H}$ s.t. there is a
vertex $v\in\alpha_{1}\cap H^{\prime}$ is said to _appear_ in $C_{R}$. It
follows from Lemma 20 and Corollary 21 that if $H^{\prime}$ appears in
$C_{R}$, then $(H^{\prime}\cap\alpha_{2})\subseteq(H\cap\alpha_{2})$ and if
$(H^{\prime}\cap\alpha_{2})\neq\emptyset$, then $H^{\prime}$ contains $u_{1}$
or $u_{2}$. Thus, in the sub-problem induced on $C_{L}$, we can remove any
$H^{\prime}$ that appears in $C_{R}$. Since $d_{H}$ joins two disjoint runs of
$H$, $N(C_{L},\mathcal{H}_{C_{L}})<N$, where $\mathcal{H}_{C_{L}}$ are the
subgraphs $H\cap C_{L}$ for $H\in\mathcal{H}$ with containments removed. By
the inductive hypothesis, there is a support $Q_{L}$ on $\mathcal{H}_{C_{L}}$.

Now, consider the induced problem on $C_{R}$. By the minimality of $d_{H}$,
each subgraph contributes at most one run to the outer face $C_{R}$. By the
base case of the induction hypothesis, there is a support $Q^{\prime}$ on
$\mathcal{H}_{C_{R}}$ that is a cycle, where $\mathcal{H}_{C_{R}}$ are the
subgraphs $H\cap C_{R}$ for $H\in\mathcal{H}$. Since the original system did
not have any containments, it follows that each subgraph in
$\mathcal{H}\setminus H$ is in $\mathcal{H}_{C_{R}}$ or $\mathcal{H}_{C_{L}}$.

We obtain a graph $Q_{R}$ from the support $Q^{\prime}$ of
$\mathcal{H}_{C_{R}}$ by adding a chord from $H$ to each
$H^{\prime}\in\mathcal{H}_{C_{R}}$. By construction,
$\mathcal{H}_{C_{R}}\cap\mathcal{H}_{C_{L}}=\\{H\\}$. We obtain the desired
support $Q^{*}$ by identifying $H$ in $Q_{L}$ and $Q_{R}$. It follows that
$Q^{*}$ is outerplanar. Let $v$ be a vertex in $C_{L}$ that is contained in a
subgraph $H^{\prime}$ that appears in $C_{R}$. Since
$(H^{\prime}\cap\alpha_{2})\subseteq(H\cap\alpha_{2})$, it follows from the
induction hypothesis and the fact that $H$ and $H^{\prime}$ are adjacent in
$Q_{R}$ that $Q^{*}[\mathcal{H}_{v}]$ is connected. Finally, by Lemma 20, for
any subgraph $H^{\prime}\in\mathcal{H}\setminus H$ having a vertex in
$\alpha_{1}$ and $\alpha_{2}$, contains $u_{1}$ or $u_{2}$, and thus is
adjacent to $H$ in $Q_{R}$. The theorem follows.

Finding a subgraph with a critical chord of minimal length can be done in
$O(|V(G)||\mathcal{H}|)$ time. Since the two sub-problems are smaller, the
overall running time is upper bounded by $O(|V(G)|^{2}|\mathcal{H}|)$. ∎

##  9 Graphs of bounded treewidth

In this section, we show that if $(G,\mathcal{H})$ is a non-piercing system,
then there exist both a primal and dual support of treewidth $O(2^{tw(G)})$.
Further, the supports can be computed in polynomial time if $G$ has bounded
treewidth.

###  9.1 Basic Tools for bounded treewidth graphs

Let $G$ be a graph of treewidth $t$ and $\mathcal{H}$ be a collection of
connected non-piercing subgraphs of $G$. Throughout this section, we use
$(T,\mathcal{B})$ to denote a tree decomposition, where we assume without loss
of generality that $T$ is a binary tree rooted at a node $\rho$.

Let $CC(G)$ denote the _chordal completion_ of $G$, i.e., for each bag
$B\in\mathcal{B}$, we add edges between non-adjacent vertices such that each
bag induces a complete subgraph. It is well-known that a chordal completion
does not increase the treewidth of the underlying graph. It is easy to check
that the subgraphs $\mathcal{H}$ remain non-piercing in $CC(G)$ if they were
non-piercing in $G$. Further, in both the primal and dual settings, a support
for the subgraphs defined on $CC(G)$ is also a support for the subgraphs
defined on $G$. Therefore, we assume without loss of generality in this
section that $G$ is a chordal graph of treewidth $t$.

We use the following notation in this section: for a node $u$ of $T$, let
$T_{u}$ denote the sub-tree rooted at $u$, and let $G_{u}$ denote the subgraph
induced by the bags associated with nodes in $T_{u}$ and let $G^{\prime}_{u}$
denote the graph induced by the bags in $T\setminus T_{u}$. Let
$A_{uv}=B_{u}\cap B_{v}$ denote the adhesion set between the bag $B_{u}$ at
$u$ and the bag $B_{v}$ at its parent $v$ in $T$. $A_{uv}$ is a separator of
$G$, and $G\setminus A_{uv}$ yields two disjoint induced subgraphs:
$G_{u}\setminus A_{uv}$ and $G^{\prime}_{u}\setminus A_{uv}$. Let
$\mathcal{H}_{A_{uv}}=\\{H\in\mathcal{H}:H\cap A_{uv}\neq\emptyset\\}$.

######  Lemma 23.

Let $(G,\mathcal{H})$ be a non-piercing system with tree-decomposition
$(T,\mathcal{B})$ of $G$. Then, for any adhesion set $A_{uv}=B_{u}\cap B_{v}$,
$(G_{u},\mathcal{H}_{u})$ and $(G^{\prime}_{u},\mathcal{H}^{\prime}_{u})$ are
non-piercing systems, where $\mathcal{H}_{u}=\\{H\cap
G_{u}\neq\emptyset:H\in\mathcal{H}\\}$ and $\mathcal{H}_{u^{\prime}}=\\{H\cap
G^{\prime}_{u}\neq\emptyset:H\in\mathcal{H}\\}$.

###### Proof.

We show that $\mathcal{H}_{u}$ is a collection of non-piercing subgraphs. An
identical argument shows that $\mathcal{H}^{\prime}_{u}$ is also a collection
of non-piercing subgraphs. Let $H^{\prime}_{1}$ and $H^{\prime}_{2}$ be two
arbitrary subgraphs in $\mathcal{H}_{u}$ corresponding respectively, to
subgraphs $H_{1}$ and $H_{2}$ in $\mathcal{H}$. Since $\mathcal{H}$ is a non-
piercing family, it follows that $H_{1}\setminus H_{2}$ and $H_{2}\setminus
H_{1}$ are connected subgraphs of $G$. If $H_{1}\setminus H_{2}$ does not
intersect $A_{uv}$, then $H_{1}\setminus H_{2}$, and therefore
$H^{\prime}_{1}\setminus H^{\prime}_{2}$ lies entirely in either $G_{u}$ or
$G^{\prime}_{u}$ and is connected since $H_{1}\setminus H_{2}$ is connected.

Otherwise, $H^{\prime}_{1}\setminus H^{\prime}_{2}$ intersects $A_{uv}$. By
assumption, $G$ is a chordal graph, and hence $A_{uv}$ is a complete subgraph.
It follows that $H^{\prime}_{1}\setminus H^{\prime}_{2}$ is connected. ∎

We next show the following lemma that will be crucial for the construction of
both the primal support and the dual support. For two sets $A$ and $B$ on the
same ground set, we say that $A$ and $B$ properly intersect if $A\setminus
B\neq\emptyset$ and $B\setminus A\neq\emptyset$.

######  Lemma 24.

Let $(G,\mathcal{H})$ be a non-piercing system with $(T,\mathcal{B})$, a tree-
decomposition of $G$. Let $A_{uv}=B_{u}\cap B_{v}$ be an adhesion set
corresponding to edge $e=(u,v)\in E(T)$ and let
$H,H^{\prime}\in\mathcal{H}_{A_{uv}}$. Suppose $(H\cap
G_{u})\subset(H^{\prime}\cap G_{u})$ and $H\cap A_{uv}=H^{\prime}\cap A_{uv}$,
then $(H^{\prime}\cap G^{\prime}_{u})\subseteq(H\cap G^{\prime}_{u})$. Suppose
$H\cap G_{u}$ and $H^{\prime}\cap G_{u}$ properly intersect, and $H\cap
A_{uv}=H^{\prime}\cap A_{uv}$, then $H\cap G^{\prime}_{u}=H^{\prime}\cap
G^{\prime}_{u}$. If $H\cap G_{u}$ and $H^{\prime}\cap G_{u}$ properly
intersect and $(H\cap A_{uv})\subset(H^{\prime}\cap A_{uv})$, then $(H\cap
G^{\prime}_{u})\subseteq(H^{\prime}\cap G^{\prime}_{u})$.

###### Proof.

Consider $(H\cap G_{u})\subset(H^{\prime}\cap G_{u})$ and let
$x\in(H^{\prime}\setminus H)\cap G_{u}$. If $\exists y\in(H^{\prime}\setminus
H)\cap G^{\prime}_{u}$ then $H^{\prime}\setminus H$ has $x$ and $y$ in two
different components since $H\cap A_{uv}=H^{\prime}\cap A_{uv}$ will form a
separator in $H^{\prime}$. This contradicts the fact that $H$ and $H^{\prime}$
are non-piercing.

Secondly, let $h\in(H\setminus H^{\prime})\cap G_{u}$ and
$h^{\prime}\in(H^{\prime}\setminus H)\cap G_{u}$ so that $H\cap G_{u}$ and
$H^{\prime}\cap G_{u}$ intersect properly. If $\exists\;y\in(H\setminus
H^{\prime})\cap G^{\prime}_{u}$, then $h$ and $y$ are not connected in
$H\setminus H^{\prime}$ since $H\cap A_{uv}=H^{\prime}\cap A_{uv}$. Hence,
$(H\cap G^{\prime}_{u})\subseteq(H^{\prime}\cap G^{\prime}_{u})$. A symmetric
argument shows $(H^{\prime}\cap G^{\prime}_{u})\subseteq(H\cap
G^{\prime}_{u})$.

Finally, $(H\setminus H^{\prime})\cap
G_{u}\neq\emptyset\neq(H^{\prime}\setminus H)\cap G_{u}$ since $H\cap G_{u}$
and $H^{\prime}\cap G_{u}$ intersect properly. Given that $(H\cap
A_{uv})\subset(H^{\prime}\cap A_{uv})$. Now, if $(H\setminus H^{\prime})\cap
G^{\prime}_{u}\neq\emptyset$, then $H^{\prime}\cap A_{uv}$ forms a separator
for $H$; the result follows. ∎

###  9.2 Primal Support

Let $(G,\mathcal{H})$ be a non-piercing system, and let
$c:V(G)\to\\{\mathbf{r},\mathbf{b}\\}$. We show that there is a primal support
$Q$ on $\mathbf{b}(V)$ of treewidth $O(2^{tw(G)})$. The proof is algorithmic
and yields a polynomial time algorithm if $tw(G)$ is bounded.

Suppose the tree-decomposition $(T,\mathcal{B})$ of $G$ enjoys the additional
property that for each adhesion set $A$, and each subgraph
$H\in\mathcal{H}_{A}$, we have that $H\cap\mathbf{b}(A)\neq\emptyset$, i.e.,
for each adhesion set $A$ and each subgraph $H$ intersecting $A$, $H$
intersects $A$ in a blue vertex. Then, $(T,\mathcal{B})$ is said to be an
_easy_ tree-decomposition. If $(T,\mathcal{B})$ is an easy tree-decomposition,
it is straightforward to obtain the desired support $Q$, and in fact
$tw(Q)\leq tw(G)$.

######  Lemma 25.

Let $(G,\mathcal{H})$ be a non-piercing system with
$c:V(G)\to\\{\mathbf{r},\mathbf{b}\\}$. Let $(T,\mathcal{B})$ be an easy tree-
decomposition of width $t$. Then, there is a support $Q$ on $\mathbf{b}(V)$ of
treewidth at most $t$.

###### Proof.

Given $(T,\mathcal{B})$, we obtain a tree-decomposition of $Q$ on
$\mathbf{b}(V)$ by removing vertices of $\mathbf{r}(V)$ from each bag
$B\in\mathcal{B}$. To see that $Q$ is a support, consider a subgraph
$H\in\mathcal{H}$. Note that $H\cap\mathbf{b}(B)$ is connected as each
$B\in\mathcal{B}$ induces a complete graph and $(T,\mathcal{B})$ is an easy
tree decomposition. ∎

If $(T,\mathcal{B})$ is not an easy tree-decomposition, we modify it to obtain
an easy tree-decomposition of width $O(2^{t})$, where $t$ is the width of the
tree-decomposition $(T,\mathcal{B})$. We then obtain a support by applying
Lemma 25.

Let $T$ be rooted at $\rho$. The algorithm to modify $(T,\mathcal{B})$ into an
easy tree-decomposition consists of two phases: In the first phase, we go
bottom-up adding carefully chosen vertices of $\mathbf{b}(V)$ to the bags such
that the resulting structure is a legal tree-decomposition. At the end of the
first phase, for each adhesion set $A$, only a subset of the subgraphs
intersecting $A$ do so at a blue vertex. In the second phase, we go top-down
from $\rho$, again adding carefully chosen vertices of $\mathbf{b}(V)$. At the
end of the second phase, we end up with an easy tree-decomposition of width at
most $3\cdot 2^{t}$.

Let $e=(u,v)$ be an edge in $T$ where $v$ is a parent of $u$. Consider a non-
empty set $S\subseteq A_{e}$ such that $S\cap\mathbf{b}(V)=\emptyset$. We
define $\mathcal{H}^{\prime}_{S}=\\{H\in\mathcal{H}_{A}:H\cap
A=S,\;H\cap\mathbf{b}(G_{u})\neq\emptyset\;\mbox{ and
}\;H\cap\mathbf{b}(G^{\prime}_{u})\neq\emptyset\\}$. We want to add vertices
in $\mathbf{b}(V)$ to $A$ so that the subgraphs in $\mathcal{H}^{\prime}_{S}$
intersect $A$ at a blue vertex. In the rest of this section, we make the
following assumptions: when we consider an adhesion set $A_{uv}$ corresponding
to edge $(u,v)$ of $T$, we assume that $v$ is the parent of $u$. When we
consider subsets $S$ of an adhesion set $A$, we implicitly assume that
$\mathcal{H}^{\prime}_{S}\neq\emptyset$. Further, we use
$\mathcal{M}_{S}\subseteq\mathcal{H}^{\prime}_{S}$ to denote the set of
minimal subgraphs in the containment order $\preceq_{G_{u}}$ defined on
$\\{H\cap G_{u}:H\in\mathcal{H}^{\prime}_{S}\\}$, i.e., for
$H,H^{\prime}\in\mathcal{H}^{\prime}_{S}$,
$H\preceq_{G_{u}}H^{\prime}\Leftrightarrow(H\cap
G_{u})\subseteq(H^{\prime}\cap G_{u})$. We use
$(\preceq_{G_{u}},\mathcal{H}^{\prime}_{S})$ to denote this partial order.

For a tree-decomposition $(T,\mathcal{B})$ of $(G,\mathcal{H})$, we say that a
tree-decomposition $(T,\mathcal{B}^{\prime\prime})$ for $(G,\mathcal{H})$
satisfies the _bottom-up property with respect to_ $(T,\mathcal{B})$ at an
adhesion set $A_{uv}$ if $\forall S\subseteq A_{uv}$, $\exists
H\in\mathcal{M}_{S}$ s.t.
$H\cap\mathbf{b}(A^{\prime\prime}_{uv})\neq\emptyset$, where
$A^{\prime\prime}_{uv}$ is the adhesion set in
$(T,\mathcal{B}^{\prime\prime})$ corresponding to $A_{uv}$.
$(T,\mathcal{B}^{\prime\prime})$ satisfies the bottom-up property with respect
to $(T,\mathcal{B})$ if it satisfies the bottom-up property at each adhesion
set in $(T,\mathcal{B})$.

######  Lemma 26.

Let $(T,\mathcal{B})$ be a tree-decomposition of width $t$ of a non-piercing
system $(G,\mathcal{H})$. Then, there is a tree-decomposition
$(T,\mathcal{B}^{\prime\prime})$ of width at most $2\cdot 2^{t}$ that
satisfies the bottom-up property with respect to $(T,\mathcal{B})$.

###### Proof.

To construct $(T,\mathcal{B}^{\prime\prime})$ we proceed bottom-up from the
leaves of $T$. If an adhesion set $A_{uv}=B_{u}\cap B_{v}$ satisfies the
following condition:

  * $(*)$

For each $S\subseteq A_{uv}$, $\exists\;H\in\mathcal{M}_{S}$ s.t.
$H\cap\mathbf{b}(B_{u})\neq\emptyset$

Then adding $\beta\in H\cap\mathbf{b}(B_{u})$ to $B_{v}$ for each $S\subseteq
A_{uv}$ ensures that the bottom-up property is satisfied in the resulting
adhesion set $A^{\prime\prime}_{uv}$. We say $B_{v}$ satisfies the bottom-up
property if each adhesion set $A_{wv}$ satisfies the bottom-up property where
$w$ is a child of $v$ in $T$.

By definition of $\mathcal{H}^{\prime}_{S}$, condition $(*)$ is satisfied for
each adhesion set $A_{uv}$ where $u$ is a leaf of $T$. For a node $u$ with
children $x$ and $y$, and parent $v$, we claim that if $A_{xu}$ and $A_{yu}$
satisfy the bottom-up property, then the adhesion set
$B^{\prime\prime}_{u}\cap B_{v}$ satisfies the property $(*)$. This is
sufficient to prove the lemma as we can process the adhesion sets bottom-up.

Thus, suppose the bottom-up property is satisfied at $A_{xu}$ and $A_{yu}$.
Let $S\subseteq B^{\prime\prime}_{u}\cap B_{v}$. If there is a subgraph $H$ in
$\mathcal{M}_{S}$ s.t. $H\cap A_{xu}=\emptyset$ and $H\cap A_{yu}=\emptyset$,
then, $\mathbf{b}(H)\cap B^{\prime\prime}_{u}\neq\emptyset$ by definition of
$\mathcal{H}^{\prime}_{S}$. So, we can assume that $H\cap A_{xu}\neq\emptyset$
or $H\cap A_{yu}\neq\emptyset$ for each $H\in\mathcal{M}_{S}$. Assume wlog the
former holds for some $H\in\mathcal{M}_{S}$. Then, $\exists
H\in\mathcal{M}_{S}$ s.t. $H\cap A_{xu}=S^{\prime}$. Since
$A^{\prime\prime}_{xu}$ satisfies the bottom-up property, there is a subgraph
$H^{\prime}\in\mathcal{M}_{S^{\prime}}$ s.t. $H^{\prime}\cap
A_{xu}=S^{\prime}$ and
$H^{\prime}\cap\mathbf{b}(A^{\prime\prime}_{xu})\neq\emptyset$. If
$H^{\prime}\preceq_{G_{x}}H$ in the partial order
$(\preceq_{G_{x}},\mathcal{H}^{\prime}_{S^{\prime}})$, then,
$\mathbf{b}(H)\cap B^{\prime\prime}_{u}\neq\emptyset$. Otherwise, if
$H^{\prime}$ and $H$ are incomparable in
$(\preceq_{G_{x}},\mathcal{H}^{\prime}_{S^{\prime}})$, then by Lemma 24
$H^{\prime}\cap G^{\prime}_{x}=H\cap G^{\prime}_{x}$ since $H\cap
A_{xu}=S^{\prime}=H^{\prime}\cap A_{xu}$. Therefore,
$H^{\prime}\in\mathcal{M}_{S}$, and
$H^{\prime}\cap\mathbf{b}(B^{\prime\prime}_{u})\neq\emptyset$, since $x$ is a
child of $u$. ∎

######  Lemma 27.

Let $(G,\mathcal{H})$ be a non-piercing system with a tree-decomposition
$(T,\mathcal{B})$ of width $t$ that is not an easy tree-decomposition. Then,
there exists an easy tree-decomposition $(T,\mathcal{B}^{\prime})$ of width at
most $3\cdot 2^{t}$.

###### Proof.

By Lemma 26, we obtain a tree-decomposition $(T,\mathcal{B}^{\prime\prime})$
of width at most $2\cdot 2^{t}$ that satisfies the bottom-up property with
respect to $(T,\mathcal{B})$.

For an adhesion set $A_{uv}$ in $(T,\mathcal{B})$ and $S\subseteq A_{uv}$, $S$
is said to be satisfied if for all $H\in\mathcal{H}^{\prime}_{S}$,
$H\cap\mathbf{b}(A^{\prime\prime}_{uv})\neq\emptyset$, where
$A^{\prime\prime}_{uv}$ is the adhesion set corresponding to $A_{uv}$ in
$(T,\mathcal{B}^{\prime\prime})$. An adhesion set $A_{uv}$ in
$(T,\mathcal{B})$ is said to be _satisfied_ if $S$ is satisfied for all
$S\subseteq A_{uv}$. We say $A_{uv}$ is _nearly satisfied_ if for all edges
$e$ closer to the root $\rho$ of $T$ than $uv$, $A_{e}$ is satisfied.

We claim that if $A_{uv}$ is nearly satisfied, then for each $S\subseteq
A_{uv}$ and each $H\in\mathcal{H}^{\prime}_{S}$,
$H\cap\mathbf{b}(B^{\prime\prime}_{v})\neq\emptyset$. Further, it is
sufficient to pick one vertex in $\mathbf{b}(B^{\prime\prime}_{v})$ and add it
to $B^{\prime\prime}_{u}$ to ensure that all subgraphs in
$\mathcal{H}^{\prime}_{S}$ intersect $A^{\prime\prime}_{uv}$ in a blue vertex.

Suppose there is a subgraph $H\in\mathcal{H}^{\prime}_{S}$ such that
$H\cap\mathbf{b}(A^{\prime\prime}_{uv})=\emptyset$. Since
$(T,\mathcal{B}^{\prime\prime})$ satisfies the bottom-up property, there is a
subgraph $H^{\prime}\in\mathcal{M}_{S}$ s.t.
$H^{\prime}\cap\mathbf{b}(A^{\prime\prime}_{uv})\neq\emptyset$. Since
$H^{\prime}$ is a minimal subgraph in $\mathcal{H}^{\prime}_{S}$, it follows
that $H$ and $H^{\prime}$ are incomparable in
$(\mathcal{H}^{\prime}_{S},\preceq_{G_{u}})$.

Suppose $A_{uv}$ is nearly satisfied and $w\neq u$ is the other child of $v$.
Further, by definition of $\mathcal{H}^{\prime}_{S}$, $H$ contains a blue
vertex in $G^{\prime}_{u}$. Therefore, $H$ contains a vertex in the adhesion
set $A_{vx}$ where $x$ is the parent of $v$ in $T$, or $H$ intersects $A_{wv}$
or $H$ intersects $B^{\prime\prime}_{v}$ only. In the third case,
$H\cap\mathbf{b}(B^{\prime\prime}_{v})\neq\emptyset$. In the first case,
$H\in\mathcal{H}^{\prime}_{S^{\prime}}$ for some $S^{\prime}\subseteq A_{vx}$.
Since $A_{uv}$ is nearly satisfied,
$H\cap\mathbf{b}(A^{\prime\prime}_{vx})\neq\emptyset$ and therefore
$H\cap\mathbf{b}(B^{\prime\prime}_{v})\neq\emptyset$.

So suppose $H\cap A^{\prime\prime}_{vx}=\emptyset$, and $H\cap
A_{wv}=S^{\prime}$. Since $(T,\mathcal{B}^{\prime\prime})$ satisfies the
bottom-up property, there is a subgraph
$H^{\prime\prime}\in\mathcal{M}_{S^{\prime}}$ s.t.
$H^{\prime\prime}\cap\mathbf{b}(A^{\prime\prime}_{wv})\neq\emptyset$ and
therefore $H^{\prime\prime}\cap\mathbf{b}(B^{\prime\prime}_{v})\neq\emptyset$.
If $H\cap\mathbf{b}(B^{\prime\prime}_{v})=\emptyset$, it must be that $H$ and
$H^{\prime\prime}$ are incomparable in $G_{w}$. By Lemma 24, therefore, $H\cap
G^{\prime}_{w}=H^{\prime\prime}\cap G^{\prime}_{w}$. Since $H$ and
$H^{\prime}$ are incomparable in $G_{u}$, it follows again by Lemma 24 that
$H\cap G^{\prime}_{u}=H^{\prime}\cap G^{\prime}_{u}$. This implies
$H^{\prime}\cap G_{w}$ and $H^{\prime\prime}\cap G_{w}$ are also incomparable.
But, it is impossible for $H^{\prime\prime}\cap G_{u}$ to be equal to $H\cap
G_{u}$ and $H^{\prime}\cap G_{u}$ which are incomparable. Therefore,
$H\cap\mathbf{b}(B^{\prime\prime}_{v})\neq\emptyset$ and since the argument
above holds for any subgraph in $\mathcal{H}^{\prime}_{S}$ incomparable with
$H^{\prime}$, it follows that there is a single vertex in
$\mathbf{b}(B^{\prime\prime}_{v})$ that is contained in all subgraphs in
$\mathcal{H}^{\prime}_{S}$ not comparable with $H^{\prime}$. Adding such a
vertex $\beta\in H\cap\mathbf{b}(B^{\prime\prime}_{u})$ to
$B^{\prime\prime}_{u}$ ensures that $S$ is satisfied. Repeating this process
for each $S\subseteq A_{uv}$ ensures that $A_{uv}$ is satisfied.

$A_{u\rho}$ is clearly nearly satisfied, where $\rho$ is the root of $T$. By
the argument above, we can add a single blue node from
$B^{\prime\prime}_{\rho}$ to $B^{\prime\prime}_{u}$ for each $S\subseteq
A_{u\rho}$, where $u$ is a child of $\rho$. This ensures that
$A^{\prime\prime}_{yu}$ is nearly satisfied for each child $y$ of $u$.
Repeating this process top-down till the leaves of $T$ ensures that the
resulting tree-decomposition $(T,\mathcal{B}^{\prime})$ is easy. For each
subset of an adhesion set $A_{uv}$ we add at most one blue vertex from
$B^{\prime\prime}_{v}$ to $B^{\prime\prime}_{u}$. Therefore the treewidth of
$(T,\mathcal{B}^{\prime})$ is at most $3\cdot 2^{t}$. ∎

######  Theorem 28.

Let $(G,\mathcal{H})$ be a non-piercing system. Let
$c:V(G)\to\\{\mathbf{r},\mathbf{b}\\}$. Then, there is a support $Q$ on
$\mathbf{b}(V)$ s.t. $tw(Q)\leq 3\cdot 2^{tw(G)}$. Further, $Q$ can be
computed in time polynomial in $|G|,|H|$ if $G$ has bounded treewidth.

###### Proof.

If $(T,\mathcal{B})$ is an easy tree-decomposition, then by Lemma 25, we
obtain a support $Q=(\mathbf{b}(V),F)$ of treewidth at most $tw(G)\leq 3\cdot
2^{tw(G)}$. Otherwise, we apply Lemma 27 to obtain an easy tree-decomposition
$(T,\mathcal{B}^{\prime})$ of width at most $3\cdot 2^{t}$. Applying Lemma 25
to $(T,\mathcal{B}^{\prime})$ yields a support $Q=(\mathbf{b}(V),F)$ of the
treewidth at most $3\cdot 2^{t}$ for $(G,\mathcal{H})$.

If $G$ has treewidth bounded above by $t$, then an optimal tree-decomposition
of $G$ can be computed in $O(2^{t}poly(n))$ time [korhonen2022single]. Now,
Lemma 25, Lemma 26 and Lemma 27 suggest a natural two phase-algorithm: Going
bottom-up in $T$ and for each adhesion set $A$ and each $S\subseteq A$, adding
a blue subgraph corresponding to a minimal subgraph to a bag, and then doing a
similar operation top-down. Therefore, the time required to process an
adhesion set is $O(2^{t}poly(\mathcal{|}H|))$. Thus, the overall running time
is $O(poly(|G|,|\mathcal{H}|)2^{t})$, which is polynomial for bounded $t$. ∎

###  9.3 Dual Support

Let $(G,\mathcal{H})$ be a non-piercing system. We show in this section that
the system admits a dual support $Q^{*}$ s.t. $tw(Q^{*})\leq
4.c\dot{2}^{tw(G)}$. Further, if $tw(G)$ is bounded above by a constant, then
$Q^{*}$ can be computed in time polynomial in $|V(G)|,|\mathcal{H}|$. We start
with a special case where it is easy to construct a support and then show how
the general case can be reduced to this simple case. For a graph system
$(G,\mathcal{H})$, where $\mathcal{H}$ is a collection of (possibly piercing)
induced subgraphs of $G$, if a tree-decomposition $(T,\mathcal{B})$ of $G$ is
such that for each bag $B\in\mathcal{B}$, $|\mathcal{H}\cap B|\leq k$, then,
we call the system $(G,\mathcal{H})$ $k$-sparse.

######  Lemma 29.

Let $(G,\mathcal{H})$ be a (possibly piercing) system where $tw(G)=t$ and each
$H\in\mathcal{H}$ induces a connected induced subgraph of $G$. Let
$(T,\mathcal{B})$ be a nice tree-decomposition of $G$ that is $k$-sparse. Then
there is a dual support $Q^{*}=(\mathcal{H},F)$ of treewidth at most $k$.

###### Proof.

We obtain a tree-decomposition $(T^{\prime},\mathcal{B}^{\prime})$ of
$Q^{*}=(\mathcal{H},F)$ as follows: the tree $T^{\prime}$ is isomorphic to
$T$. Corresponding to each bag $B\in\mathcal{B}$, we construct a bag
$B^{\prime}\in\mathcal{B}^{\prime}$ such that $B^{\prime}$ consists of a
vertex $v_{H}$ for each subgraph $H\in\mathcal{H}$ such that $H\cap
B\neq\emptyset$. Since each subgraph is connected $G$, each vertex $v_{H}$
corresponding to a subgraph $H\in\mathcal{H}$ lies in a connected subset of
bags of $T^{\prime}$. Further, since $|B\cap\mathcal{H}|\leq k$, it follows
that the resulting tree-decomposition has width at most $k$. Finally, we claim
that adding an edge between each pair of vertices $u_{H}$, and
$v_{H^{\prime}}$ such that $u_{H}$ and $v_{H^{\prime}}$ lie in the same bag
results in a dual support for $(G,\mathcal{H})$. To see this, consider a
vertex $v\in V(G)$ and a bag $B\in\mathcal{B}$ containing $v$. The bag
$B^{\prime}\in\mathcal{B}^{\prime}$ corresponding to $B$ contains the
subgraphs $\mathcal{H}_{v}$ by construction. Adding edges between all pairs of
subgraphs in $B^{\prime}$ ensures that $\mathcal{H}_{v}$ is connected. The
result follows. ∎

To obtain a dual support, we sparsify the input graph so that it satisfies the
conditions of Lemma 29 and such that a support for the original system can be
obtained from the support for the new system. We proceed bottom-up in the
tree-decomposition of $G$, and for each adhesion set $A_{uv}=B_{u}\cap B_{v}$,
and for each $S\subseteq A_{uv}$, we choose a minimal subgraph in
$\mathcal{H}_{S}$ and use it to _push out_ a collection of subgraphs. This
sparsification will ensure that at the end, there are at most $O(2^{t})$
distinct subgraphs (subgraphs $H$ and $H^{\prime}$ are distinct if $(H\cap
V(G))\neq(H^{\prime}\cap V(G))$) intersecting each bag as there are at most
$2^{t}$ distinct subsets intersecting each adhesion set. In the following, for
an adhesion set $A$ and $S\subseteq A$, we let
$\mathcal{H}^{\prime}_{S}=\\{H\in\mathcal{H}:H\cap A=S\\}$.

######  Lemma 30.

Let $(G,\mathcal{H})$ be a non-piercing system with tree-decomposition
$(T,\mathcal{B})$ of width $t$. Then, we can obtain a system
$(G,\mathcal{H}^{\prime})$ of (possibly piercing) connected induced subgraphs
such that each bag of $(T,\mathcal{B})$ intersects at most $4\cdot 2^{t}$
distinct subgraphs.

###### Proof.

We process the adhesion sets bottom-up from the leaves of $T$. Let $A_{uv}$ be
an adhesion set with $v$ the parent of $u$ in $T$. Having processed the
adhesion sets below $A_{uv}$, we do the following at $A_{uv}$: For each
$S\subseteq A_{uv}$, choose a subgraph $H\in\mathcal{H}^{\prime}_{S}$ that is
_minimal_ in $(\mathcal{H}^{\prime}_{S},\preceq_{G_{u}})$. For each subgraph
$H^{\prime}\in\mathcal{H}_{A_{uv}}$ s.t. $(H^{\prime}\cap
G_{u})\setminus(H\cap G_{u})\neq\emptyset$ and $(H^{\prime}\cap
A_{uv})\subseteq S$, replace $H^{\prime}$ by $H^{\prime\prime}=(H^{\prime}\cap
G_{u})\setminus(H\cap G_{u})$. We say that $H^{\prime}$ is _pushed out_ by
$H$. The collection $\mathcal{H}^{\prime\prime}$ of subgraphs is obtained by
replacing each subgraph in $\mathcal{H}$ by its pushed out copy. Observe that
$\mathcal{H}^{\prime\prime}$ may contain identical subgraphs even if
$\mathcal{H}$ did not. Let $unique(\mathcal{H}^{\prime\prime})$ denote the
subgraphs obtained by keeping a unique copy of each set of identical
subgraphs.

We claim that at the end of this process, each subgraph is pushed out at most
once, each subgraph in $\mathcal{H}^{\prime\prime}$ is a connected induced
subgraph of $G$, and that the resulting system
$(G,unique(\mathcal{H}^{\prime\prime}))$ is $4\cdot 2^{t}$ sparse.

For the first part, observe that since a subgraph $H^{\prime}$ is connected,
it belongs to a connected subset of bags of $T$. Once $H^{\prime}$ is pushed
out at an adhesion set $A_{uv}$, $H^{\prime}$ does not intersect any adhesion
set in $T^{\prime}_{u}$. Thus, each subgraph is pushed out at most once since
we process the adhesion sets bottom-up.

The second part follows from the fact that the system $(G,\mathcal{H})$ is
non-piercing, and therefore $H^{\prime\prime}=(H^{\prime}\cap
G_{u})\setminus(H\cap G_{u})$ is a connected induced subgraph of $G_{u}$. The
fact that $\mathcal{H}^{\prime\prime}$ consists of connected induced subgraphs
of $G$ follows from the fact that each subgraph is pushed out at most once.

For the third part, Once we have pushed out subgraphs at an adhesion set $A$,
observe that for each adhesion set $A$ and each $S\subseteq A$, there is at
most one subgraph $H\in unique(\mathcal{H}^{\prime\prime})$ s.t. $H\cap A=S$.
Since $T$ is a binary tree, each bag intersects at most 3 adhesion sets and
each adhesion set is intersected by at most $2^{t}$ subgraphs in
$unique(\mathcal{H}^{\prime\prime})$. Therefore, there are at most $3\cdot
2^{t}$ subgraphs intersecting a bag $B\in\mathcal{B}$, and an additional at
most $2^{t}$ distinct subgraphs intersecting $B$ at vertices of $B$ not
contained in any adhesion set intersecting $B$. The result follows. ∎

######  Theorem 31.

Let $(G,\mathcal{H})$ be a non-piercing system. There is a dual support
$Q^{*}$ on $\mathcal{H}$ s.t. $tw(Q^{*})\leq 4\cdot 2^{t}$ where $t$ is the
treewidth of $G$. Further, $Q^{*}$ can be computed in time polynomial in
$|G|,|\mathcal{H}|$ if $G$ has bounded treewidth.

###### Proof.

If $(T,\mathcal{B})$ is at most $4\cdot 2^{t}$-sparse, we obtain a support
$Q^{*}$ by Lemma 29. Otherwise, we apply Lemma 30 to obtain a system
$(G,unique(\mathcal{H}^{\prime\prime}))$ s.t.
$(G,unique(\mathcal{H}^{\prime\prime})$ is $4\cdot 2^{t}$ sparse. Now, by
Lemma 29, we obtain a support $Q$ for $(G,unique(\mathcal{H}^{\prime\prime}))$
of width at most $4\cdot 2^{t}$.

To obtain a support $Q^{*}$ for $(G,\mathcal{H})$, for each $H\in
unique(\mathcal{H}^{\prime\prime})$, we add a new vertex $v_{H^{\prime}}$ for
each $H^{\prime}\in\mathcal{H}^{\prime\prime}$ identical to $H$ and add the
edges $\\{v_{H}^{\prime},v_{H}\\}$ to $Q$. Since this operation does not
increase the treewidth, $tw(Q^{*})\leq 4\cdot 2^{t}$.

We show that $Q^{*}$ is a support for $(G,\mathcal{H})$. If $H^{\prime}$ was
pushed out by $H$, it follows that $(H^{\prime}\cap
G^{\prime}_{u})\subseteq(H\cap G^{\prime}_{u})$ by Lemma 24. Further, since
$H^{\prime}$ is connected, there is an edge $e=\\{u,v\\}$ in $G$ s.t. $u\in
H^{\prime}\setminus H$ and $v\in H\cap H^{\prime}$. Hence, there is a bag
$B\in\mathcal{B}$ containing $e$. By the way we construct a support in Lemma
29, it follows that $H$ and $H^{\prime}$ are connected. Let $v\in V(G)$. The
subgraphs in $unique(\mathcal{H}^{\prime\prime})$ containing $v$ induce a
connected subgraph of $Q^{*}$. If $H^{\prime}\ni v$ was pushed out, there is a
subgraph $H\in unique(\mathcal{H}^{\prime\prime})$ that contains $v$. By the
argument above, it follows that there is a path from $H^{\prime}$ to $H$ in
$Q^{*}$ containing only subgraphs in $\mathcal{H}_{v}$.

If $G$ has treewidth $t$, bounded above by a constant, then by the result of
Korhonen [korhonen2022single], a tree-decomposition of $G$ of width $t$ can be
computed in time $O(2^{t}poly(n))$. Lemma 29 and Lemma 30 suggest a natural
bottom-up algorithm. The algorithm works by iterating over all subsets of each
adhesion set and pushes out a subset of subgraphs. It is easy to see that the
time taken to process an adhesion set is $O(2^{t}poly(|\mathcal{H}|)$, and the
overall algorithm runs in $O(poly(|G|,|\mathcal{H}|2^{t})$, which is
polynomial for bounded $t$. ∎

One may wonder if the non-piercing condition is necessary to obtain a support
of bounded treewidth. The following examples show that this is indeed the
case. For the primal, consider a star $K_{1,n}$ with the leaves colored blue,
and the central vertex red. Consider a collection of induced subgraphs defined
by all pairs of leaves. It is easy to see that the support is a complete graph
$K_{n}$ on the blue vertices. For the dual, consider a star
$K_{1,\binom{n}{2}}$. Each leaf of a star is labelled by a unique pair of
$\\{1,\ldots,n\\}$. There are $n$ subgraphs. The subgraph $i$ contains the
central vertex and the leaves that contain the label $i$. The subgraphs are
piercing, and the dual support is $K_{n}$.

##  10 Lower Bounds

In this section, we show that there exist graphs of treewidth $t$ whose
(primal or dual) support requires treewidth $\Omega(2^{t})$.

######  Theorem 32.

For any $\epsilon>0$, there exists a graph $G=(V,E)$ with
$c:V\to\\{\mathbf{r},\mathbf{b}\\}$, and a collection of connected non-
piercing induced subgraphs $\mathcal{H}$ such that any primal support
$Q=(\mathbf{b}(V),F)$ of $(G,\mathcal{H})$ has treewidth
$\Omega(2^{t/8(1+\epsilon)})$.

###### Proof.

For any $t$, let $N=2^{t}$. We construct the following graph $G(V,E)$: We
start with an $N\times N$ grid of blue points $b_{i,j}$ for $i,j=1,\ldots,N$.
We construct four sets $U,D,L,R$ of $2n$ red points each, where $n=c\log N$,
for $c>0$ chosen s.t. $\binom{2n}{n}\geq N$. Since $\binom{2n}{n}\geq
2^{n}/(n+1)$, for any $\epsilon>0$, choosing $c=1+\epsilon$ satisfies the
condition for $N$ sufficiently large.

((a)) $H_{3,2}$ and $H^{\prime}_{3,2}$ are shown on $5\times 5$ gird.

((b)) The subgraphs $H_{ij}$ and $H_{k\ell}$ are shown non-piercing.

Figure 3: Construction of primal hypergraph with support containing a grid
minor.

Let $U_{1},\ldots,U_{N-1}$ and $L_{1},\ldots,L_{N-1}$ denote $N-1$ distinct
subsets of $U$ and $L$, respectively, each of size $n$. Similarly, let
$D_{1},\ldots,D_{N}$ and $R_{1},\ldots,R_{N}$ denote $N$ distinct subsets of
$D$ and $L$, respectively, each of size $n$. Since we assume that
$\binom{2n}{n}\geq N$, this can indeed be done.

For each pair $b_{i,j},b_{i,j+1}$ for $i=1,\ldots,N$ and $j=1,\ldots,N-1$, we
make $b_{i,j}$ and $b_{i,j+1}$ adjacent to all vertices in the set $U_{j}$ and
all vertices in the set $R_{i}$. Next, for each pair $b_{i,j},b_{i+1,j}$ for
$i=1,\ldots,N-1$, $j=1,\ldots,N$ we make $b_{i,j}$ and $b_{i+1,j}$ adjacent to
all vertices in the set $D_{j}$ and the set $L_{i}$. This completes the
construction of the graph (see Figure 3(a)).

Since there are no edges between any pair of blue vertices or between any pair
of red vertices, it follows that $G$ is bipartite. Further, $|r(V)|=8c\log N$
and $|b(V)|=N^{2}$. Thus, $tw(G)\leq 8c\log N$.

Now we add a collection of non-piercing subgraphs to $G$ that will force the
treewidth of the support to be $\Omega(N)$. For each pair $b_{i,j},b_{i,j+1}$,
$i=1,\ldots,N,j=1,\ldots,N-1$ we add the subgraph $H_{ij}$ induced by the
vertices $b_{i,j}\cup b_{i,j+1}\cup U_{j}\cup R_{i}$. Similarly, for each pair
$b_{i,j},b_{i+1,j}$, $i=1,\ldots,N-1$ and $j=1,\ldots,N$ we add a subgraph
$H^{\prime}_{ij}$ induced on the vertices
$\\{b_{i,j}\\}\cup\\{b_{i+1,j}\\}\cup D_{j}\cup L_{i}$. Let
$\mathcal{H}=\\{H_{ij}:i=1,\ldots,N,j=1,\ldots,N-1\\}\cup\\{H^{\prime}_{ij}:i=1,\ldots,N-1,j=1,\ldots,N\\}$.

We claim that $\mathcal{H}$ is a non-piercing collection of connected induced
subgraphs of $G$. By definition, each subgraph in $\mathcal{H}$ is a connected
induced subgraph of $G$. It only remains to show that the subgraphs are non-
piercing. Consider two subgraphs $H_{ij}$ and $H_{k\ell}$ in $\mathcal{H}$ (as
shown in Figure 3(b)). $H_{ij}$ is the graph induced on the vertices
$b_{i,j}\cup b_{i,j+1}\cup U_{j}\cup R_{i}$ and $H_{k\ell}$ is the graph
induced on the vertices $b_{k,\ell}\cup b_{k,\ell+1}\cup U_{\ell}\cup R_{k}$.
Thus, $H_{ij}\setminus H_{k\ell}$ consists of the graph induced on the
vertices $b_{i,j}\cup b_{i,j+1}\cup(U_{j}\setminus
U_{\ell})\cup(R_{i}\setminus R_{k})$. If $j\neq\ell$, $U_{j}\setminus
U_{\ell}$ is non-empty, and if $i\neq k$, $R_{i}\setminus R_{k}$ is non-empty.
Since $b_{i,j}$ and $b_{i,j+1}$ are adjacent to each vertex in $U_{j}$ and
$R_{i}$, it follows that $H_{ij}\setminus H_{k\ell}$ is connected. A symmetric
argument shows that $H_{k\ell}\setminus H_{ij}$ is connected. A similar
argument shows that subgraphs $H_{ij}$ and $H^{\prime}_{k\ell}$ are non-
piercing for any choice of $i,j,k$ and $\ell$.

Each subgraph in $\mathcal{H}$ consists of exactly two blue vertices in
consecutive rows or two blue vertices in consecutive columns. Therefore, any
support $Q(\mathbf{b}(G),F)$ for the system $(G,\mathcal{H})$ must have an
$N\times N$ grid as a subgraph. Therefore, $tw(Q)\geq N\geq 2^{tw(G)/8c}$. ∎

######  Theorem 33.

For any $\epsilon>0$ there exists a graph $G=(V,E)$ and a collection of
connected non-piercing induced subgraphs $\mathcal{H}$ such that any dual
support $Q=(\mathcal{H},F)$ has treewidth $\Omega(2^{tw(G)})$.

###### Proof.

Our construction of $G$ is similar to the construction for the primal support
in Theorem 32. We start with a grid of $(2N+1)\times(2N+1)$ points $b_{ij}$,
$i,j=1,\ldots,2N+1$. At each point $b_{2i,2j+1},i=1,\ldots,N,j=0,\ldots,N$ add
a vertex $g_{2i,2j+1}$ (See Figure 4(a)). Similarly, at each point
$b_{2i+1,2j},i=0,\ldots,N,j=1,\ldots,N$ add a vertex $g_{2i+1,2j}$. Let $K$
denote this set of vertices added. Let $A$ and $B$ be two sets of vertices of
size $2n$ each, where $n=c\log N$ such that $\binom{2n}{n}\geq N$. Let
$A_{1},\ldots,A_{N}$ be distinct subsets of $A$ of size $n$ each, and let
$B_{1},\ldots,B_{N}$ be distinct subsets of $B$ of size $n$ each. Each point
$g_{2i,2j+1}$ is adjacent to each vertex in $A_{i},B_{j}$ and $B_{j+1}$ where
$B_{0}$ and $B_{N+1}$ are empty sets. Similarly, each vertex in $g_{2i+1,2j}$
is adjacent to each vertex in $A_{i},A_{i+1}$ and $B_{j}$ where $A_{0}$ and
$A_{N+1}$ are empty sets. This completes the construction of the graph. $G$ is
a bipartite graph with bipartition $K$ and $A\cup B$, as the vertices in $K$
are pairwise non-adjacent, and so are the vertices in $A\cup B$. Further,
$|K|=N^{2}$ and $|A\cup B|=4n$. Thus, $tw(G)\leq 4n=4c\log N$.

((a)) $H_{11}$ (blue) and $H_{22}$ (orange) are shown on a $5\times 5$ gird.

((b)) The subgraphs $H_{ij}$ and $H_{k\ell}$ are shown non-piercing.

Figure 4: Construction of dual hypergraph with support containing a grid as a
subgraph.

For each point $b_{2i,2j},i,j=1,\ldots,N$ we construct a subgraph $H_{ij}$
induced on the vertices $g_{2i-1,2j},g_{2i+1,2j},g_{2i,2j-1},g_{2i,2j+1}\cup
A_{i}\cup B_{j}$. It is easy to see that the subgraphs
$\mathcal{H}=\cup_{i,j\in\\{1,\ldots,N\\}}H_{ij}$ are non-piercing: For
$H_{ij}$ and $H_{k\ell}$, it follows that $H_{ij}\setminus H_{k\ell}$ contains
as a subset, the vertices in $(A_{i}\setminus A_{k})\cup(B_{j}\setminus
B_{\ell})$ as shown in Figure 4(b). Since $H_{ij}$ and $H_{k\ell}$ differ in
at least one index, at least one of the sets $A_{i}\setminus A_{k}$, or
$B_{j}\setminus B_{\ell}$ are non-empty, and the vertices in
$K\cap(H_{ij}\setminus H_{k\ell})$ are adjacent to all vertices in
$(A_{i}\setminus A_{k})\cup(B_{j}\setminus B_{\ell})$. By the construction of
$\mathcal{H}$, the set $K\cap(H_{ij}\setminus H_{k\ell})$ contains at least
one vertex. Hence $H_{ij}\setminus H_{k\ell}$ is connected.

By construction, the vertex $g_{2i,2j+1}$ is contained only in the subgraphs
$H_{ij}$ and $H_{i,j+1}$. This pair of subgraphs must be adjacent in any dual
support $Q$. Similarly, the vertex $g_{2i+1,2j}$ is contained only in
subgraphs $H_{ij}$ and $H_{i+1,j}$ and this pair of subgraphs should also be
adjacent in $Q$. Therefore, $Q$ contains an $N\times N$ grid as an induced
subgraph. It follows that $tw(Q)=\Omega(N)=\Omega(2^{tw(G)/4c})$. For any
$\epsilon>0$, setting $c=1+\epsilon$, there is an $N$ large enough so that
$\binom{2n}{n}\geq N$. Therefore, $tw(Q)=\Omega(2^{tw(G)/4(1+\epsilon)})$. ∎

##  11 Applications

In this section, we describe some applications of the existence of supports.
Raman and Ray [RR18] showed that for an intersection hypergraph defined on a
set of _non-piercing regions_ 111111A set of path connected regions
$\mathcal{R}$ in the plane is non-piercing if for any $A,B\in\mathcal{R}$,
$A\setminus B$ and $B\setminus A$ are path connected. in the plane, there is a
planar support (See [RR18] for precise definitions), which implies a support
for both the primal and dual settings for the hypergraph defined by points and
non-piercing regions in the plane.

Since graphs of genus $g$ admit separators of size $O(\sqrt{gn})$
[gilbert1984separator], all the algorithmic consequence of [RR18] generalize
to cross-free systems on bounded genus graphs. We highlight three results that
follow as a consequence of Theorem 17.

######  Theorem 34.

Let $(G,\mathcal{H})$ be a cross-free system of genus $g$, then there exists

  1. 1.

a PTAS for the Dominating Set problem, which is a problem to find
$\mathcal{H}^{\prime}\subseteq\mathcal{H}$ of minimum cardinality s.t. for
each $H\in\mathcal{H}$, either $H\in\mathcal{H}^{\prime}$ or $H\cap
H^{\prime}\neq\emptyset$ for some $H^{\prime}\in\mathcal{H}^{\prime}$.

  2. 2.

a PTAS for the problem of packing points when each subgraph $H\in\mathcal{H}$
has capacity $D_{H}$ bounded by a constant, i.e., find $V^{\prime}\subseteq V$
of maximum cardinality s.t. $|H\cap V^{\prime}|\leq D_{H}$ for each
$H\in\mathcal{H}$.

  3. 3.

a PTAS for the problem of packing subgraphs when each vertex $v\in V$ has
capacity $D_{v}$ bounded by a constant, i.e., find
$\mathcal{H}^{\prime}\subseteq\mathcal{H}$ of maximum cardinality s.t.
$|\\{H\in\mathcal{H}^{\prime}:H\ni v\\}|\leq D_{v}$ for each $v\in V$.

We believe that the cross-free condition is essential to obtain PTASes for
packing and covering problems when the host graph has bounded genus. Chan and
Grant [DBLP:journals/comgeo/ChanG14] proved that for a hypergraph defined by a
set of horizontal and vertical slabs in the plane and a set of points $P$, the
Hitting Set problem and the Set Cover problems are APX-hard. A simple
modification of their result implies the following.

######  Theorem 35.

There exist crossing non-piercing systems $(G,\mathcal{H})$ with $G$ embedded
in the torus such that the hitting set or set cover problems are APX-hard.

Keller and Smorodinsky [KellerS18] showed that the intersection hypergraph of
disks in the plane can be colored with 4 colors, and this was generalized by
Keszegh [Keszegh20] for pseudodisks, which was further generalized in [RR18]
to show that the intersection hypergraph of non-piercing regions is
4-colorable. As a consequence of Theorem 17, we obtain the following.

######  Theorem 36.

Let $(G,\mathcal{H},\mathcal{K})$ be a cross-free intersection system where
$G=(V,E)$ is embedded in an orientable surface of genus $g$. Then,
$\mathcal{H}$ can be colored with at most $\frac{7+\sqrt{1+24g}}{2}$ colors
such that no hyperedge ${\mathcal{H}_{K}}$ is monochromatic.

###### Proof.

By Theorem 17, $(G,\mathcal{H},\mathcal{K})$ has a support $\tilde{Q}$ of
genus at most $g$. Now, $\chi(\tilde{Q})\leq\frac{7+\sqrt{1+24g}}{2}$
[diestel2005graph]. Since $\tilde{Q}$ is a support, for each
$K\in\mathcal{K}$, there is an edge between some two subgraphs
$H,H^{\prime}\in{\mathcal{H}_{K}}$. Therefore, no hyperedge
${\mathcal{H}_{K}}$ is monochromatic. ∎

Ackerman et al. [ackerman2020coloring] considered a notion of $ABAB$-free
hypergraphs, which is defined as follows: a hypergraph $(X,\mathcal{S})$ is
$ABAB$-free if there exists a linear ordering $x_{1}<\ldots<x_{n}$ of $X$ such
that for any pair of subgraphs $A,B\in\mathcal{S}$, there are no four elements
$x_{i}<x_{j}<x_{k}<x_{\ell}$ s.t. $x_{i},x_{k}\in A\setminus B$ and
$x_{j},x_{\ell}\in B\setminus A$. The notion of $ABAB$-free hypergraphs is
equivalent to the notion of $abab$-free hypergraphs (See Defn. 4). Indeed, if
there exists a linear ordering $x_{1}<\ldots<x_{n}$ that is $ABAB$-free, then
the cyclic order $x_{1}<\ldots<x_{n}<x_{1}$ is $abab$-free, and similarly, if
$x_{1}<\ldots,x_{n}<x_{1}$ is a cyclic order that is $abab$-free, then
$x_{1}<\ldots<x_{n}$ is an $ABAB$-free linear order.

The authors show that $ABAB$-free hypergraphs are equivalent to hypergraphs
with a _stabbed pseudo-disk representation_ , i.e., each $S\in\mathcal{S}$ is
mapped to a closed and bounded region $D_{S}$ containing the origin whose
boundary is a simple Jordan curve, each $x\in X$ is mapped to a point $p_{x}$
in $\mathbb{R}^{2}$ s.t. $p_{x}\in D_{S}$ iff $x\in S$. The regions
$\mathcal{D}=\\{D_{S}:S\in\mathcal{S}\\}$ form a stabbed pseudodisk
arrangement, i.e., the boundaries of any two of them are either disjoint or
intersect exactly twice. Let $(P,\mathcal{D})$ denote the embedding of the
hypergraph where $P=\\{p_{x}:x\in X\\}$.

The authors show that to any stabbed pseudodisk arrangement $\mathcal{D}$ and
a set $P$ of points, we can add additional pseudodisks $\mathcal{D}^{\prime}$
s.t. $(i)$ each $D^{\prime}\in\mathcal{D}^{\prime}$ contains exactly 2 points
of $P$, $(ii)$ $\mathcal{D}\cup\mathcal{D}^{\prime}$ is a pseudodisk
arrangement, and $(iii)$ Each $D\in\mathcal{D}$ s.t. $|D\cap P|\geq 3$
contains a pseudodisk $D^{\prime}\in\mathcal{D}^{\prime}$. The graph on $P$
whose edges are defined by $\mathcal{D}^{\prime}$ is called the _delaunay
graph_ of the arrangement.

Our result, namely Theorem 18 in Section 8 is stronger. A delaunay graph
ensures that for each pseudodisk $D\in\mathcal{D}$, the induced subgraph on
the elements in $D$ is non-empty, while a support implies that the induced
subgraph of the support on the elements in $D$ is connected. At the outset, it
seems like the results of Ackerman et al. [ackerman2020coloring], especially
the proof of Lemma $2.1$ can be used to prove Lemma 10. However, there is a
subtle difference between the two. The authors show that there is a 2-element
hyperedge, or equivalently a non-blocking diagonal can be added between two
elements of a hyperedge, but in the vertex bypassing operation we require this
diagonal to be between two disjoint runs of a hyperedge which is a more
stringent condition.

The authors show that for a stabbed pseudodisk arrangement, the delaunay graph
as constructed above is outerplanar, and hence is 3-colorable. This implies
that $ABAB$-free hypergraphs, and thus hypergraphs induced by stabbed
pseudodisks can be colored with 3 colors so that no hypergedge with $\geq 2$
elements is mono-chromatic. This result also follows directly from Theorem 18.

Ackerman et al., [ackerman2020coloring] ask if we can 3 color the elements of
the dual of an $ABAB$-free hypergraph s.t. no hyperedge of the dual with at
least two elements is monochromatic. In Figure 5(a) we show that this is not
true - even if the regions are defined by unit disks in the plane. The dual
hypergraph contains four elements corresponding to the four unit disks, and
six hyperedges corresponding to the six points. Each hyperedge defined by a
point is a pair of disks containing that point. The intersection of the disks
is non-empty, and therefore the hypergraph is $ABAB$-free. Each point is of
depth 2, and therefore the delaunay graph is $K_{4}$, which is not
3-colorable. However, by Theorem 22, it follows that if a hypergraph
$(X,\mathcal{S})$ admits a representation as non-piercing subgraphs on a host
outerplanar graph, then the hyperedges can be 3-colored so that no point is
monochromatic.

Consider the following natural extension of the result of Ackerman et al.
[ackerman2020coloring]: Given a collection of stabbed non-piercing regions in
the plane, does there exist a coloring of the points with 3 colors s.t. no
region is monochromatic? We answer this question again in the negative by
giving a counter-example (see Figure 5(b)). It is easy to check that in this
case again, the delaunay graph is $K_{4}$ and therefore the arrangement is not
$3$-colorable. The reason why hypergraphs defined by stabbed pseudodisks is 3
colorable, but stabbed non-piercing regions is not is the following: Let
$\overrightarrow{H}$ denote the directed graph obtained from the dual
arrangement graph where each edge is directed from a cell to its adjacent
cells of lower depth. If $(P,\mathcal{D})$ is a stabbed pseudodisk
arrangement, then we can show that every cell is reachable from $o$, where $o$
is the cell in the intersection of all pseudodisks (marked by $\times$ in
Figure 5(b)). This is not true for example, in the graph $\overrightarrow{H}$
corresponding to the arrangement in Figure 5(b). In particular, the cell
containing $d$ is not reachable in $\overrightarrow{H}$ from the cell $o$ in
the intersection of all the regions.

((a)) Dual: Every point $a,b,\ldots,f$ is contained in two disks.

((b)) Primal: Every region contains two points.

Figure 5: Stabbed hypergraphs of disks (dual) and non-piercing regions
(primal) requiring four colors.

##  12 Conclusion

In this paper, we studied the problem of construction of supports for systems
$(G,\mathcal{H})$ defined on a host graph $G$. We primarily studied two
settings, namely when $G$ has bounded genus, and when $G$ has bounded
treewidth. We showed that if $G$ has bounded genus, then the cross-free
property is sufficient to obtain a support of genus at most that of $G$. If
$G$ has bounded treewidth, we showed that the non-piercing condition on
$\mathcal{H}$ is a sufficient condition to obtain a support of bounded
treewidth in the primal and dual settings. However, an exponential blow-up of
the treewidth of the support is sometimes necessary. Along the way, we also
studied the setting of outerplanar graphs. There are several intriguing open
questions and research directions and we mention a few: We do not know if the
algorithm to construct a dual or intersection support in the bounded-genus
case runs in polynomial time. Settling this will be a very interesting
question. A broader line of research is to obtain necessary and sufficient
conditions for a hypergraph to have a _sparse support_ \- where sparsity could
be a graph with sublinear-sized separators or even just a graph with a linear
number of edges.

## References

  * [1] Eyal Ackerman, Balázs Keszegh, and Dömötör Pálvölgyi.  Coloring hypergraphs defined by stabbed pseudo-disks and abab-free hypergraphs.  SIAM Journal on Discrete Mathematics, 34(4):2250–2269, 2020.
  * [2] Anna Adamaszek, Sariel Har-Peled, and Andreas Wiese.  Approximation schemes for independent set and sparse subsets of polygons.  Journal of the ACM (JACM), 66(4):1–40, 2019.
  * [3] Noga Alon, Paul Seymour, and Robin Thomas.  A separator theorem for nonplanar graphs.  Journal of the American Mathematical Society, 3(4):801–808, 1990\.
  * [4] Emmanuelle Anceaume, Maria Gradinariu, Ajoy Kumar Datta, Gwendal Simon, and Antonino Virgillito.  A semantic overlay for self-peer-to-peer publish/subscribe.  In 26th IEEE International Conference on Distributed Computing Systems (ICDCS’06), pages 22–22. IEEE, 2006.
  * [5] Daniel Antunes, Claire Mathieu, and Nabil H. Mustafa.  Combinatorics of local search: An optimal 4-local hall’s theorem for planar graphs.  In 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, pages 8:1–8:13, 2017.
  * [6] Sanjeev Arora.  Nearly linear time approximation schemes for euclidean TSP and other geometric problems.  In 38th Annual Symposium on Foundations of Computer Science, FOCS ’97, Miami Beach, Florida, USA, October 19-22, 1997, pages 554–563. IEEE Computer Society, 1997.  doi:10.1109/SFCS.1997.646145.
  * [7] Rom Aschner, Matthew J. Katz, Gila Morgenstern, and Yelena Yuditsky.  Approximation schemes for covering and packing.  In Subir Kumar Ghosh and Takeshi Tokuyama, editors, WALCOM: Algorithms and Computation, 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings, volume 7748 of Lecture Notes in Computer Science, pages 89–100. Springer, 2013.  doi:10.1007/978-3-642-36065-7\\_10.
  * [8] Roberto Baldoni, Roberto Beraldi, Vivien Quema, Leonardo Querzoni, and Sara Tucci-Piergiovanni.  Tera: topic-based event routing for peer-to-peer architectures.  In Proceedings of the 2007 inaugural international conference on Distributed event-based systems, pages 2–13, 2007.
  * [9] Roberto Baldoni, Roberto Beraldi, Leonardo Querzoni, and Antonino Virgillito.  Efficient publish/subscribe through a self-organizing broker overlay and its application to siena.  The Computer Journal, 50(4):444–459, 2007.
  * [10] Aniket Basu Roy, Sathish Govindarajan, Rajiv Raman, and Saurabh Ray.  Packing and covering with non-piercing regions.  Discrete & Computational Geometry, 2018.
  * [11] Sergey Bereg, Krzysztof Fleszar, Philipp Kindermann, Sergey Pupyrev, Joachim Spoerhase, and Alexander Wolff.  Colored non-crossing euclidean steiner forest.  In Algorithms and Computation: 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings, pages 429–441. Springer, 2015.
  * [12] Sergey Bereg, Minghui Jiang, Boting Yang, and Binhai Zhu.  On the red/blue spanning tree problem.  Theoretical computer science, 412(23):2459–2467, 2011.
  * [13] Hans L Bodlaender.  A partial k-arboretum of graphs with bounded treewidth.  Theoretical computer science, 209(1-2):1–45, 1998.
  * [14] Ulrik Brandes, Sabine Cornelsen, Barbara Pampel, and Arnaud Sallaberry.  Blocks of hypergraphs: applied to hypergraphs and outerplanarity.  In Combinatorial Algorithms: 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers 21, pages 201–211. Springer, 2011.
  * [15] Ulrik Brandes, Sabine Cornelsen, Barbara Pampel, and Arnaud Sallaberry.  Path-based supports for hypergraphs.  Journal of Discrete Algorithms, 14:248–261, 2012.
  * [16] Kevin Buchin, Marc J van Kreveld, Henk Meijer, Bettina Speckmann, and KAB Verbeek.  On planar supports for hypergraphs.  Journal of Graph Algorithms and Applications, 15(4):533–549, 2011\.
  * [17] Sergio Cabello and David Gajser.  Simple ptas’s for families of graphs excluding a minor.  CoRR, abs/1410.5778, 2014.
  * [18] Timothy M. Chan and Elyot Grant.  Exact algorithms and apx-hardness results for geometric packing and covering problems.  Comput. Geom., 47(2):112–124, 2014.  doi:10.1016/j.comgeo.2012.04.001.
  * [19] Timothy M. Chan and Sariel Har-Peled.  Approximation algorithms for maximum independent set of pseudo-disks.  Discrete & Computational Geometry, 48(2):373–392, 2012.  doi:10.1007/s00454-012-9417-5.
  * [20] Raphaël Chand and Pascal Felber.  Semantic peer-to-peer overlays for publish/subscribe networks.  In Euro-Par 2005 Parallel Processing: 11th International Euro-Par Conference, Lisbon, Portugal, August 30-September 2, 2005. Proceedings 11, pages 1194–1204. Springer, 2005.
  * [21] Vincent Cohen-Addad and Claire Mathieu.  Effectiveness of local search for geometric optimization.  In Proceedings of the Thirty-first International Symposium on Computational Geometry, SoCG ’15, pages 329–343, Dagstuhl, Germany, 2015. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [22] Reinhard Diestel.  Graph theory 3rd ed.  Graduate texts in mathematics, 173(33):12, 2005.
  * [23] Greg N Federickson.  Fast algorithms for shortest paths in planar graphs, with applications.  SIAM Journal on computing, 16(6):1004–1022, 1987.
  * [24] VZ Feinberg, AG Levin, and EB Rabinovich.  VLSI planarization: methods, models, implementation, volume 399\.  Springer Science & Business Media, 2012.
  * [25] Jacob Fox and János Pach.  Applications of a new separator theorem for string graphs.  Comb. Probab. Comput., 23(1):66–74, 2014.  doi:10.1017/S0963548313000412.
  * [26] John R Gilbert, Joan P Hutchinson, and Robert Endre Tarjan.  A separator theorem for graphs of bounded genus.  Journal of Algorithms, 5(3):391–407, 1984.
  * [27] Frédéric Havet, Dorian Mazauric, Viet-Ha Nguyen, and Rémi Watrigant.  Overlaying a hypergraph with a graph with bounded maximum degree.  Discrete Applied Mathematics, 319:394–406, 2022.
  * [28] Walter Holberg.  The decomposition of graphs into k-connected components.  Discrete mathematics, 109(1-3):133–145, 1992.
  * [29] Jun Hosoda, Juraj Hromkovič, Taisuke Izumi, Hirotaka Ono, Monika Steinová, and Koichi Wada.  On the approximability and hardness of minimum topic connected overlay and its special instances.  Theoretical Computer Science, 429:144–154, 2012.
  * [30] Ferran Hurtado, Matias Korman, Marc van Kreveld, Maarten Löffler, Vera Sacristán, Akiyoshi Shioura, Rodrigo I Silveira, Bettina Speckmann, and Takeshi Tokuyama.  Colored spanning graphs for set visualization.  Computational Geometry, 68:262–276, 2018.
  * [31] David S Johnson and Henry O Pollak.  Hypergraph planarity and the complexity of drawing venn diagrams.  Journal of graph theory, 11(3):309–325, 1987.
  * [32] Chaya Keller and Shakhar Smorodinsky.  Conflict-free coloring of intersection graphs of geometric objects.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2397–2411, 2018.
  * [33] Balázs Keszegh.  Coloring intersection hypergraphs of pseudo-disks.  Discret. Comput. Geom., 64(3):942–964, 2020.  doi:10.1007/s00454-019-00142-6.
  * [34] Balázs Keszegh and Dömötör Pálvölgyi.  An abstract approach to polychromatic coloring: shallow hitting sets in aba-free hypergraphs and pseudohalfplanes.  J. Comput. Geom., 10(1):1–26, 2019.  doi:10.20382/jocg.v10i1a1.
  * [35] Ephraim Korach and Michal Stern.  The clustering matroid and the optimal clustering tree.  Mathematical Programming, 98:385–414, 2003.
  * [36] Tuukka Korhonen.  A single-exponential time 2-approximation algorithm for treewidth.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 184–192. IEEE, 2022.
  * [37] Erik Krohn, Matt Gibson, Gaurav Kanade, and Kasturi Varadarajan.  Guarding terrains via local search.  Journal of Computational Geometry, 5(1):168–178, 2014.
  * [38] Richard J Lipton and Robert Endre Tarjan.  A separator theorem for planar graphs.  SIAM Journal on Applied Mathematics, 36(2):177–189, 1979.
  * [39] Richard J Lipton and Robert Endre Tarjan.  Applications of a planar separator theorem.  SIAM journal on computing, 9(3):615–627, 1980.
  * [40] Nabil H Mustafa and Saurabh Ray.  Improved results on geometric hitting set problems.  Discrete & Computational Geometry, 44(4):883–895, 2010.
  * [41] Jaroslav Neetil and Patrice Ossona de Mendez.  Sparsity: graphs, structures, and algorithms.  Springer Publishing Company, Incorporated, 2012.
  * [42] Melih Onus and Andréa W Richa.  Minimum maximum-degree publish–subscribe overlay network design.  IEEE/ACM Transactions on Networking, 19(5):1331–1343, 2011.
  * [43] Rajiv Raman and Saurabh Ray.  Constructing planar support for non-piercing regions.  Discrete & Computational Geometry, 64(3):1098–1122, 2020.
  * [44] Rajiv Raman and Saurabh Ray.  On the geometric set multicover problem.  Discret. Comput. Geom., 68(2):566–591, 2022.  doi:10.1007/s00454-022-00402-y.
  * [45] Robert E Tarjan and Mihalis Yannakakis.  Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs.  SIAM Journal on computing, 13(3):566–579, 1984.
  * [46] AA Voloshina and VZ Feinberg.  Planarity of hypergraphs.  In DOKLADY AKADEMII NAUK BELARUSI, volume 28, pages 309–311. ACADEMII NAUK BELARUSI F SCORINA PR 66, ROOM 403, MINSK, BYELARUS 220072, 1984\.
  * [47] Eric W Weisstein.  Torus grid graph.  https://mathworld. wolfram. com/, 2016.
  * [48] Alexander Aleksandrovich Zykov.  Hypergraphs.  Russian Mathematical Surveys, 29(6):89, 1974.