Abstract
In the embedded planar diameter improvement problem (EPDI) we are given a graph G embedded in the plane and a positive integer d. The goal is to determine whether one can add edges to the planar embedding of G in such a way that planarity is preserved and in such a way that the resulting graph has diameter at most d. Using nonconstructive techniques derived from Robertson and Seymour's graph minor theory, together with the effectivization by selfreduction technique introduced by Fellows and Langston, one can show that EPDI can be solved in time f(d)* V(G)^{O(1)} for some function f(d). The caveat is that this algorithm is not strongly uniform in the sense that the function f(d) is not known to be computable. On the other hand, even the problem of determining whether EPDI can be solved in time f_1(d)* V(G)^{f_2(d)} for computable functions f_1 and f_2 has been open for more than two decades [Cohen at. al. Journal of Computer and System Sciences, 2017]. In this work we settle this later problem by showing that EPDI can be solved in time f(d)* V(G)^{O(d)} for some computable function f. Our techniques can also be used to show that the embedded kouterplanar diameter improvement problem (kEOPDI), a variant of EPDI where the resulting graph is required to be kouterplanar instead of planar, can be solved in time f(d)* V(G)^{O(k)} for some computable function f. This shows that for each fixed k, the problem kEOPDI is strongly uniformly fixed parameter tractable with respect to the diameter parameter d.
BibTeX  Entry
@InProceedings{lokshtanov_et_al:LIPIcs:2019:10226,
author = {Daniel Lokshtanov and Mateus de Oliveira Oliveira and Saket Saurabh},
title = {{A StronglyUniform Slicewise PolynomialTime Algorithm for the Embedded Planar Diameter Improvement Problem}},
booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
pages = {25:125:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770842},
ISSN = {18688969},
year = {2019},
volume = {115},
editor = {Christophe Paul and Michal Pilipczuk},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10226},
URN = {urn:nbn:de:0030drops102265},
doi = {10.4230/LIPIcs.IPEC.2018.25},
annote = {Keywords: Embedded Planar Diameter Improvement, Constructive Algorithms, Nooses}
}
Keywords: 

Embedded Planar Diameter Improvement, Constructive Algorithms, Nooses 
Collection: 

13th International Symposium on Parameterized and Exact Computation (IPEC 2018) 
Issue Date: 

2019 
Date of publication: 

05.02.2019 