Polynomial-time solvability of Directed Plane Strong Connectivity Augmentation
Polynomial-time solvability of Directed Plane Strong Connectivity Augmentation
Let be a connected plane digraph and let be an integer. The Directed Plane Strong Connectivity Augmentation problem asks whether there is a set with such that is strongly connected, directed, and plane for the same embedding of . Directed-PSCA conjecture. The Directed Plane Strong Connectivity Augmentation problem is polynomial-time solvable. The paper establishes fixed-parameter tractability for this problem, while polynomial-time solvability remains open.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Stéphane Bessy, Daniel Gonçalves, Amadeus Reinald and Dimitrios M. Thilikos, “Plane Strong Connectivity Augmentation”, arXiv:2512.17904 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.