Number of maximal planar subgraphs

Question

Suppose we have an undirected graph $G$ which is maximal planar, i.e. adding an edge results in $G$ not being planar anymore. How many subgraphs $G'$ does $G$ have such that $G'$ is also maximal planar?

Answer 1

There is not a simple answer like a formula with the number of vertices, edges and faces as variables. This is easily seen to be true by considering the octahedron and any Apollonian network with 6 vertices. Both have 8 faces, 12 edges and 6 vertices, but the octahedron has only 8 proper subgraphs that are maximal planar (exactly the faces), but the Apollonian network has more (e.g. the vertex that was added last in a recursive construction, together with its three neighbours, forms another one).

This does not mean that no "formula" is possible, but it must involve the structure of the graph. By adding restrictions simpler formula may be found. E.g. if you require that your graph has a planar drawing in which every sub-$K_3$ is a triangular face, then the number of maximal planar subgraphs is exactly the number of faces (the octahedron is an example of this).

[ADDED LATER]

Clearly $2^n$ is a (trivial) exponential upper bound (where $n$ is the number of vertices).

That the growth is indeed exponential can be seen with following construction: Start with $G_1=K_4$, for $G_2$: nest $G_1$ in the three bounded faces of $K_4$ (giving a graph with 7 vertices), for $G_3$: nest $G_2$ in the three bounded faces of $K_4$ (giving a graph with 16 vertices), etc.

The recursive relation is that $|G_{n+1}|=3(|G_n|-3)+4$, so the vertices of $G_n$ roughly grow as $3^n$.

In $G_2$ we see at least $2^3$ maximal planar subgraphs that still contain the outer boundary, so in $G_3$ we find at least $(2^3)^3=2^{(3^2)}$ and in general in $G_n$ we find at least $2^{(3^{n-1})}$.