A connected, simple, undirected planar graph $G(V, E)$ is given where $V$ denotes the set of vertices and E denotes the set of edges. In $V$, there is a designated source vertex $s$ and a designated destination vertex $t$. Let $P(v)$ denote the shortest path (may contain repetition of nodes/edges) from $s$ to $t$ that passes through $v$, and let $l(v)$ denote the path length (i.e., the number of edges) of $P(v)$.
- Describe an $O(|V|)$ time algorithm that determines the value of $\mathcal{T}$ where $\mathcal{T} = max_{\forall \: v \in V} l(v)$. Justify your analysis.
- Propose a data structure that supports your algorithm.
For example, in the graph shown in the above figure, $\mathcal{T}$ = 10, which corresponds to $P(6) : s \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 7 \rightarrow 6 \rightarrow 7 \rightarrow 4 \rightarrow 14 \rightarrow 13 \rightarrow t$.]
