Back to Search
Start Over
The $st$-Planar Edge Completion Problem is Fixed-Parameter Tractable
- Publication Year :
- 2023
-
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'$.
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2309.15454
- Document Type :
- Working Paper