Number of maximal induced trees in a connected planar graph

Question

An induced subgraph $G’$ of a graph $G$ is a subset of its vertices along with all the edges that are present in $G$ among those vertices. For $G’$ to be a tree, all vertices of a cycle in $G$ cannot be in $G’$. The tree composed of bold edges in the illustration given below shows an induced tree $T$. Vertex $u$ cannot be included in $T$ because u brings with itself edges $(u, v)$ and $(u, w)$ which completes a cycle $u-v-w-u$ and $T$ no longer remains a tree. $T$ is also a maximal induced tree because no more vertices can be included in $T$ without violating it being a tree.

The question is, what is a tight upper bound on the number of maximal induced trees in a connected triangulated planar graph.

Answer 1

Consider the following planar triangulated 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),(u_1,u_2),\dotsc,(u_{n-1},u_n),(v_1,v_2),\dotsc,(v_{n-1},v_n), (y,u_1),(v_1,u_2),\dotsc,(v_{n-1},u_n)\}$.

Suppose your algorithm initially picks $x$ and $y$ in $S$. Thereafter, suppose the algorithm picks the even numbered vertices $u_{2i}$ and $v_{2i}$ for $i \in \{1,\dotsc,\lfloor n/2 \rfloor\}$. Then, the algorithm can construct $2^{\lfloor n/2 \rfloor}$ possible induced trees depending on whether $u_{2i}$ or $v_{2i}$ is included in the induced tree for each $i \in \{1,\dotsc,\lfloor n/2 \rfloor\}$. Therefore, there are $2^{\Omega(|V|)}$ possible induced 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|)}$.