2026-07-23T22:32:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19348 2024-03-06T11:03:50Z ddc:004 open_access

The st-Planar Edge Completion Problem Is Fixed-Parameter Tractable Khazaliya, Liana Kindermann, Philipp Liotta, Giuseppe Montecchiani, Fabrizio Simonov, Kirill st-planar graphs parameterized complexity upward planarity 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' ⊆ V × 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'. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Liana Khazaliya and Philipp Kindermann and Giuseppe Liotta and Fabrizio Montecchiani and Kirill Simonov 2023 Is Part Of LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2023.46 urn:nbn:de:0030-drops-193483 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.46 eng https://creativecommons.org/licenses/by/4.0/legalcode