# Finding an $st$-path in a planar graph which is adjacent to the fewest number of faces

I am curious whether the following problems has been studied before, but wasn't able to find any papers about it:

Given a planar graph $$G$$, and two vertices $$s$$ and $$t$$, find an $$s$$-$$t$$ path $$P$$ which minimizes the number of distinct faces of $$G$$ containing vertices of $$P$$ on their boundaries.

Does anybody know any references?

• This may be a silly question, but would you need to fix an embedding for this? – G. Bach Dec 20 '13 at 2:14
• @G.Bach: from an algorithmic point of view, when we say "given a planar graph", we usually mean "given a combinatorial map for a graph", hence the embedding is indeed fixed. – zarathustra Dec 20 '13 at 8:03
• Do you have an application in mind, or just curiosity? – Joe Dec 20 '13 at 21:13
• which research databases have you searched? – orezvani May 29 '14 at 3:21
• @zarathustra: No, if we say "given a planar graph" we mean "given a planar graph". If we assume that this graph is equipped with a combinatorial embedding we say, "given a plane graph". Of course, if the graph is 3-connected then the combinatorial embedding is fixed up to a global reflection. – A.Schulz Dec 19 '14 at 8:11