# Closed walk in planar graphs that contains $k$ faces

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?

• 3. Regardless of how you obtained $G$, I still wonder whether it might be fruitful to consider $G^*$ (the dual graph of $G$) and try to reformulate the problem in terms of $G^*$, and see if that leads to a clean formulation. 4. It might be useful to edit the question to clear up all of these. – D.W. Jan 4 '16 at 23:25
• Related (but not a duplicate): cs.stackexchange.com/q/19137/9550 – David Richerby Jan 5 '16 at 15:31