  This paper optimizes path planning for a trunkand-branch topology network in
an irregular 2-dimensional manifold embedded in 3-dimensional Euclidean space
with application to submarine cable network planning. We go beyond our earlier
focus on the costs of cable construction (including labor, equipment and
materials) together with additional cost to enhance cable resilience, to
incorporate the overall cost of branching units (again including material,
construction and laying) and the choice of submarine cable landing stations,
where such a station can be anywhere on the coast in a connected region. These
are important issues for the economics of cable laying and significantly change
the model and the optimization process. We pose the problem as a variant of the
Steiner tree problem, but one in which the Steiner nodes can vary in number,
while incurring a penalty. We refer to it as the weighted Steiner node problem.
It differs from the Euclidean Steiner tree problem, where Steiner points are
forced to have degree three; this is no longer the case, in general, when nodes
incur a cost. We are able to prove that our algorithm is applicable to Steiner
nodes with degree greater than three, enabling optimization of network costs in
this context. The optimal solution is achieved in polynomialtime using dynamic
programming.
