In the research I am currently involved in, I am given a planar, maximal graph $G$ of $n$ vertices, and its embedding. I require to find a structure, which I call a "triangle hierarchy" of $G$, in deterministic time $O(n)$. Informally, this structure is a tree rooted at the outer face of $G$ (which is a triangle, and by triangle I mean any $K_3$ in $G$), which we can traverse down, to the "inner triangles" of $G$. Two triangles $t$ and $s$ are connected in that tree ($t$ is a parent of $s$), if $s$ is contained in $t$ (in the given embedding) and there is no triangle $r$ such that $r$ is contained in $t$ but not in $s$. This looks like a useful structure for many algorithms, but I failed to find any reference about it. I am hoping someone from this community can point me to some paper.
Here is the formal definition with the example:
[inner trinagles] A triangle in the planar graph embedding that is not a face we call an inner triangle.
[pivotal triangles] A triangle in a maximal, planar graph embedding of $G$ is called pivotal, if it is an inner triangle in $G$ or an outer face of $G$.
[triangle inside] Let $t$ be a triangle in a maximal, planar graph $G$. The inside of $t$ is a plane fragment bounded by the edges of $t$ in the embedding of $G$. Edges and vertices of the triangle are not part of its inside.
[contains relation] A triangle $t$ contains a triangle $s$ iff the inside of $s$ is a proper subset of the inside of $t$. We say that a triangle $t$ contains a vertex $v$, if $v$ belongs to the inside of $t$. Let $G$ be a maximal, planar graph, embedded on a plane, and let $A$ be the set of its pivotal triangles. We define a relation $\sqsubset$ on $A$, such that for any $t,s \in A$, $s \sqsubset t$ if and only if $t$ contains $s$.
By the abuse of notation we will write $v \sqsubset t$, where $v$ is a vertex, to say that a triangle $t$ contains $v$. Let $A$ be the set of triangles of the embedding of some maximal, planar graph. Observe that $(\sqsubset, A)$ is a partially ordered set.
[triangle hierarchy] Let $G$ be a maximal, planar graph, embedded on a plane, and let $A$ be the set of its pivotal triangles. Let $D=(A,F)$ be a directed graph, with vertices corresponding to the set of pivotal triangles $A$, and the set of edges $F$ defined as follows: for each $t,s \in A$, $\langle t,s \rangle \in F$ iff $s \sqsubset t$ and there is no $r \in A \setminus \{t,s\}$ such that $s \sqsubset r \sqsubset t$. We call graph $D$ a triangle hierarchy of $G$.
In any planar graph embedding, edges do not intersect (except at endpoints) and every triangle consists of three vertices, therefore any two triangle insides are either disjoint or one contains the other. Therefore a triangle hierarchy of $G$ is a tree rooted at the outer face of $G$.
Let $D=(A,F)$ be a triangle hierarchy of some maximal, planar graph $G=(V,E)$. For each triangle $t \in A$ we define $\lambda(t)$ to be the set of vertices forming $t$, and $\sigma(t)=\{ v \in V \, : \, v \sqsubset t \wedge \forall_{s\in A}(s \sqsubset t \Rightarrow v \not \sqsubset s) \}$. Informally, $\sigma(t)$ is the set of vertices, such that $t$ contains them, but no triangle lower in the hierarchy contains them.
The example:
Sample graph
Its triangle hierarchy
As a starting point, here is an $O(n^2)$ algorithm. I have no strong reason to think that this is optimal.
First, we can find all the triangles in $O(n^2)$ time. If $xy$ is an edge, there are at most $n-2$ possibilities for a third vertex $z$ such that $(x,y,z)$ form a triangle, so we can check them all in $O(n)$ time (by checking if $xz$ and $yz$ are also edges). There are $3n-6$ edges, which is also $O(n)$.
It took us $O(n^2)$ time to find the triangles, but in reality there are only $O(n)$ triangles. We can prove a bound of $10n$ by induction: let $G$ be any planar graph, and let $v$ be a vertex of degree less than $6$, which is known to exist. Then there are at most $\binom{\deg v}{2} \le 10$ triangles containing $v$, and by the inductive hypothesis at most $10(n-1)$ triangles in $G-v$.
To find the triangle hierarchy, start with a partial hierarchy that initially only contains the exterior triangle. To add a triangle $t$ into the hierarchy:
Add the triangles into the hierarchy one at a time as you find them. This will also include the triangles which are faces, and you didn't want those, but they will all be leaves of the tree, and we can pluck them at the end if we need to.
This will certainly take at most $O(n^2)$ time, because we compare any two triangles at most once in each direction. It may take $O(n^2)$ time if there is a chain of $O(n)$ nested triangles and we add them to the hierarchy in a bad order. Regardless, even if there is a better way to do this, there is no point improving it unless we can also find the triangles more quickly.