I have a plane graph $G$ and a set of $k$ vertex pairs $\{s_1,t_1\}, \dots, \{s_k, t_k\}$. The goal is to find $k$ non-crossing paths connecting the pairs of terminals $s_i$ with $t_i$ in the graph so that the sum of path lengths is minimized. Note that the paths may "touch" each other, that is, share graph vertices and edges; the only requirement is that they do not cross.
It is easy to see that a solution always exists. Is finding an optimal solution NP-hard? I'm interested in the variant when $k$ is arbitrary and $G$ is a planar graph. However, the problem seems non-trivial even when $k=O(1)$ and/or $G$ is restricted. Say, is it possible to efficiently find such paths on a tree or a star?
An example of an input instance and a (possibly non-optimal) solution follows.
Most of the existing works (e.g., Shortest Non-Crossing Walks in the Plane) consider a similar problem in which the paths are not restricted to a graph and can be routed arbitrarily in the plane. In this setting, the terminals lie on obstacles and a solution might not exist. I'm not aware of a paper considering my variant of the problem.
