Here is what is known and what is not known about the “planar, boundary-terminal” version of Node-Multiway-Cut:

1. Classical Node-Multiway-Cut (in arbitrary graphs) is NP-complete already for 3 terminals (Dahlhaus, Johnson, Papadimitriou, Seymour & Yannakakis ’92).

2. If you restrict to planar graphs but allow the terminals to live anywhere, the vertex-deletion version remains NP-complete by essentially the same reductions.

3. By contrast, the edge-deletion version of Multiway-Cut becomes polynomial on planar graphs once all terminals lie on a single face. One shows (via the planar dual) that finding a minimum set of edges that separates all terminals is exactly the problem of finding a minimum Steiner‐forest in the dual, which can be done in polynomial time when the terminals all lie around one face.

4. However, for the vertex-deletion problem on planar graphs with all terminals on the outer face there is no known polynomial‐time algorithm and also no NP-hardness proof in the literature. In other words, the complexity of

   “Given a plane graph G, a set S of vertices all incident with the outer face, and an integer k, does there exist X⊆V(G), |X|≤k, that separates every pair of S-terminals in G–X?”

   remains open.

People have tried to adapt the usual planar‐gadget reductions so as to force the terminals onto the outer face, and also to reinterpret vertex-cuts in the primal as edge-cuts in some dual‐like construction, but so far no convincing NP-hardness reduction (and no polytime algorithm) has appeared. Thus at present one can only say:

• Edge-Multiway-Cut on planar + outer-face terminals is in P.
• Vertex-Multiway-Cut on general planar is NP-complete.
• Vertex-Multiway-Cut on planar + outer-face terminals: open problem.