Is connecting islands with pontoons NP-complete?
After looking at the new diagrams, I see that you may need multiple pontoons to cross between islands. Given that, you could get very close to a solution of the Steiner Tree problem by turning the nodes into islands and creating a sufficiently diverse collection of pontoons with small arcs. Wikipedia says that there is in fact a PTAS for the Steiner tree problem, so I can't say immediately that this renders it NP-complete. However looking at the details of the Steiner tree might either get you a good approximate solution or show that the problem is NP-Complete.