Computational complexity of finding a spanning tree in planar hybergraphs

Question

Using a bipartite graph to represent hypergraphs as described by Wikipedia :

A hypergraph $H$ may be represented by a bipartite graph $BG$ as follows: the sets $X$ and $E$ are the partitions of $BG$, and ($x_1$, $e_1$) are connected with an edge if and only if vertex $x_1$ is contained in edge $e_1$ in H. Conversely, any bipartite graph with fixed parts and no unconnected nodes in the second part represents some hypergraph in the manner described above. This bipartite graph is also called incidence graph.

Now if we assume that a hybergraph is planar if and only if it can be represented by a planar bipartite graph. What is the complexity of finding a spanning tree in planar hybergraphs? It is also ok if you can provide any source on how to approach this problem.

---

Note: It is known that the spanning tree problem of general hybergraphs is $NP$-complete, while spanning tree of $3$-uniform hypergraphs, where all hyperedges are of size $3$, has a polynomial algorithm using matroid matching [ref].

Note: Under the bipartite representation of hypergraphs the problem of spanning tree becomes equivalent to the problem of finding a subset of vertices that induces a tree such that the tree contains all vertices of one of the bipartitions of the bipartite graph. The problem is a bit similar to the Induced-Tree problem defined in this paper, but in this problem the induced tree must contain any set $S$ of vertices as part of the problem input. The Induced-Tree problem is $NP$-complete even for planar bipartite cubic graphs.

Answer 1

The answer is in this paper "Tree-Residue Vertex-Breaking: a new tool for proving hardness"

The Hypergraph Spanning Tree problem in $k$-uniform $2$-regular hypergraphs is $NP$-complete for any $k≥4$, even when the incidence graph of the hypergraph is planar.

Basically, they define a new problem:

Tree-Residue Vertex-Breaking (TRVB): given a multigraph $G$ some of whose vertices are marked "breakable," is it possible to convert $G$ into a tree via a sequence of "vertex-breaking" operations (replacing a degree-$k$ breakable vertex by $k$ degree-$1$ vertices, disconnecting the k incident edges)?

Proving this:

For any k≥4, TRVB is NP-complete when the given multigraph is restricted to be planar and consists entirely of degree-k breakable vertices.

You can see that solving TRVB for the incidence graph of a hypergraph corresponds to solving SPANING TREE in hypergraphs. Where the incidence graph of a hypergraph is isomorphic to the bipartite representation of the hypergraph described above.