Number of "one neighbourhood" search trees in a graph

Question

Consider the following algorithm: We are given a planar graph $G$. We initialise a set of vertices $S$ to an empty set. We randomly pick a vertex $v$ in $G$ and insert it in $S$. Now we keep including in $S$ vertices from the neighbourhood of $S$ such that the vertex we include is adjacent to exactly one vertex in $S$. We stop expanding $S$ when there is no vertex in the neighbourhood of $S$ which is adjacent to exactly one vertex in $S$. Just like BFS produces a breath first tree and DFS produces a depth first tree, the "one neighbourhood" search above also produces a tree. Give a tight upper bound on the number of such trees in $G$.

I expect the number of such trees to be asymptotically lower than O($2^n$), where $n$ is the number of vertices in $G$.

The illustration below shows such a tree in a graph.

Answer 1

Consider the following planar graph $G$. There are $n+2$ vertices: $\{x,y,u_1,\dotsc,u_n,v_1,\dotsc,v_n\}$. The edge set is $\{(x,y),(x,u_1),\dotsc,(x,u_n),(y,v_1),\dotsc,(y,v_n),(u_1,v_1),\dotsc,(u_n,v_n)\}$.

Suppose your algorithm initially picks $x$ and $y$ in $S$. Then, the algorithm can construct $2^n$ possible search trees depending on whether $u_i$ or $v_i$ is included in the serach tree for each $i \in \{1,\dotsc,n\}$. Therefore, there are $2^{\Omega(|V|)}$ possible search trees for this graph.

Note that this is asymptotically tight bound in the exponent since in a planar graph, the number of edges are linearly bounded by the number of vertices, i.e., $|E| = O(|V|)$ (see here for the properties of a planar graph). Therefore, the number of subgraphs of any planar graph are at most $2^{O(|V|)}$.