# 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? Dec 20, 2013 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. Dec 20, 2013 at 8:03
• Do you have an application in mind, or just curiosity?
– Joe
Dec 20, 2013 at 21:13
• @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. Dec 19, 2014 at 8:11
• @zarathustra you need only go to Wikipedia for this distinction. Apr 20, 2015 at 5:19