  This paper provides an optimized cable path planning solution for a
tree-topology network in an irregular 2D manifold in a 3D Euclidean space, with
an application to the planning of submarine cable networks. Our solution method
is based on total cost minimization, where the individual cable costs are
assumed to be linear to the length of the corresponding submarine cables
subject to latency constraints between pairs of nodes. These latency
constraints limit the cable length and number of hops between any pair of
nodes. Our method combines the Fast Marching Method (FMM) and a new Integer
Linear Programming (ILP) formulation for Minimum Spanning Tree (MST) where
there are constraints between pairs of nodes. We note that this problem of MST
with constraints is NP-complete. Nevertheless, we demonstrate that ILP running
time is adequate for the great majority of existing cable systems. For cable
systems for which ILP is not able to find the optimal solution within an
acceptable time, we propose an alternative heuristic algorithm based on Prim's
algorithm. In addition, we apply our FMM/ILP-based algorithm to a real-world
cable path planning example and demonstrate that it can effectively find an MST
with latency constraints between pairs of nodes.
