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

Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani, Kirill Simonov

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'$.
BibTeX
@inproceedings{khazaliya2023st,
  author = {Liana Khazaliya and Philipp Kindermann and Giuseppe Liotta and Fabrizio Montecchiani and Kirill Simonov},
  title = {{The $st$-Planar Edge Completion Problem is Fixed-Parameter Tractable}},
  booktitle = {ISAAC},
  year = {2023},
  url = {https://openreview.net/forum?id=PvQxJzBsZ0},
}

Loading related content...

Figure