Input: Planar graph $G$ and its embedding in sphere $\Pi$, edges $e, f \in E(G)$ and integer $k$.Output: A shortest closed walk (one among possibly many, if exists) in $G$ using $e$ and $f$ which contains exactly $k$ faces of $G$. A walk $w = v_1,e_1,v_2,...,e_i,v_i$ (where $v_j \in V(G), e_j \in E(G)$ for $1 \le j \le i$) uses an edge $e$, if $e = e_j$ for some $1 \le j \le i$. Also a walk $w$ contains the face $g$ if in the embedding of $G$ on sphere when we consider $w$ and $g$ as closed 2-dimensional polytopes, then $g \subseteq w$.  A walk is allowed to have repeated vertices/edges.Can this problem be solved in polynomial time?
Closed walk in planar graphs that contains k faces
algorithms;complexity theory;graph theory;np complete;planar graphs