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?

  • 3
    $\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
  • 12
    $\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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.