Résumé
We investigate the problem of strong connectivity augmentation within plane oriented graphs. We show that deciding whether a plane oriented graph$D$can be augmented with (any number of) arcs$X$such that$D+X$is strongly connected, but still plane and oriented, is NP-hard. This question becomes trivial within plane digraphs, like most connectivity augmentation problems without a budget constraint. The budgeted version, Plane Strong Connectivity Augmentation (PSCA) considers a plane oriented graph$D$along with some integer$k$ , and asks for an$X$of size at most$k$ensuring that$D+X$is strongly connected, while remaining plane and oriented. Our main result is a fixed-parameter tractable algorithm for PSCA, running in time$2^{O(k)} n^{O(1)}$ . The cornerstone of our procedure is a structural result showing that, for any fixed$k$ , each face admits a bounded number of partial solutions "dominating" all others. Then, our algorithm for PSCA combines face-wise branching with a Monte-Carlo reduction to the polynomial Minimum Dijoin problem, which we derandomize. To the best of our knowledge, this is the first FPT algorithm for a (hard) connectivity augmentation problem constrained by planarity.