Abstract
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' \subseteq V \times V$ is known to be NP-complete. We show that the problem is fixed-parameter tractable when parameterized by the size of the set $E'$.
Introduction
In graph drawing and visualization, $st$-planar graphs are considered the "gold standard" for representing hierarchies or flows. These are directed acyclic graphs (DAGs) that can be embedded in the plane without edge crossings such that exactly one source ($s$) and one sink ($t$) lie on the outer boundary.
The $st$-Planar Edge Completion problem asks: given a directed graph $G$ and an integer $k$, can we add at most $k$ edges to $G$ to obtain an $st$-planar graph? This problem is inherently difficult due to its NP-completeness even for biconnected graphs, its sensitivity to planar embeddings, and its deep connection to upward planarity testing. This paper demonstrates that the problem is Fixed-Parameter Tractable (FPT), solvable in $2^{O(k^2)} \cdot n^2$ time, making it efficiently solvable for small values of $k$.
Methodology
The proposed solution employs a sophisticated dynamic programming (DP) approach on the SPQR-tree decomposition of the graph. SPQR-trees allow for the systematic decomposition of a biconnected graph into its triconnected components: Series (S), Parallel (P), and Rigid (R) nodes. The DP proceeds bottom-up on this tree.
A core innovation is the use of signatures. To avoid exhaustive search over all possible completions, the authors define a signature—a string encoding the sequence of "switches" (sources and sinks) along a component's boundary. By tracking angle assignments within faces and bounding the number of relevant switches by a function of $k$, the DP table size remains manageable. Specifically, each added edge can "fix" at most one source and one sink; thus, if the input graph contains more than $2k+2$ sources and sinks, it cannot be completed within the budget $k$.
Key Insights
The algorithm relies on the concept of saturation—adding edges to transform sources or sinks into internal nodes of a flow. The problem is reduced to finding the most cost-effective way to saturate these vertices until only one source and one sink remain.
Handling "Rigid" nodes in the SPQR-tree is particularly challenging because their structure is fixed. However, the authors show that one can efficiently branch over possible angle assignments for these structures due to the bounded number of switches. This parameterization is the hallmark of the FPT approach.
Results and Conclusion
The primary result is a deterministic FPT algorithm with a complexity of $2^{O(k^2)} \cdot n^2$. While the core proof addresses biconnected digraphs, the authors outline extensions to simply connected graphs using block-cutvertex trees. This work provides a general framework for applying SPQR-trees to edge modification problems in directed planar graphs.
While the $2^{O(k^2)}$ complexity is a significant theoretical milestone, practical implementations for $k > 10$ would require additional heuristics. Future research directions include investigating the existence of a polynomial kernel and seeking a "Fixed-Parameter Linear" (FPL) algorithm with $O(f(k) \cdot n)$ time complexity.
Summary updated