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


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.