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?

  • 1
    $\begingroup$ This may be a silly question, but would you need to fix an embedding for this? $\endgroup$ – G. Bach Dec 20 '13 at 2:14
  • 2
    $\begingroup$ @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. $\endgroup$ – zarathustra Dec 20 '13 at 8:03
  • 1
    $\begingroup$ Do you have an application in mind, or just curiosity? $\endgroup$ – Joe Dec 20 '13 at 21:13
  • 1
    $\begingroup$ which research databases have you searched? $\endgroup$ – orezvani May 29 '14 at 3:21
  • 7
    $\begingroup$ @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. $\endgroup$ – A.Schulz Dec 19 '14 at 8:11

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.