The $st$-Planar Edge Completion Problem is Fixed-Parameter Tractable

Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta +2

The problem of deciding whether a biconnected planar digraph $G=(V,E)$ can be augmented to become an $st$-planar graph by adding a set of oriented edges $E^{\prime }\subseteq V\times V$ i…