English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

13 In the embedded planar diameter improvement problem (EPDI) we are given as input a graph 14 G embedded in the plane and a positive integer d. The goal is to determine whether one can add 15 edges to G in such a way that the resulting graph is still planar but has diameter at most d. Using 16 non-constructive techniques derived from Robertson and Seymour’s graph minor theory, together 17 with the effectivization by self-reduction technique introduced by Fellows and Langston, one can 18 show that EPDI can be solved in time f(d) · |V (G)|O(1) for some function f(d). The caveat is 19 that this algorithm is not strongly uniform in the sense that the function f(d) is not known to be 20 computable. On the other hand, even the problem of determining whether EPDI can be solved in 21 time f1(d) · |V (G)|f2(d) for computable functions f1 and f2 has been open for more than two decades 22 [Cohen at. al. Journal of Computer and System Sciences, 2017]. In this work we settle this problem 23 by showing that EPDI can be solved in time f(d) · |V (G)|O(d) for some computable function f . Our 24 techniques can also be used to show that the embedded k-outerplanar diameter improvement 25 problem (k-EOPDI), a variant of EPDI where the graph G′ is required to be k-outerplanar instead 26 of planar, can be solved in time f(d) · |V (G)|O(k) for some computable function f . This shows that 27 for each fixed k, the problem k-EOPDI is strongly uniformly fixed parameter tractable with respect 28 to the diameter parameter d. 29

A Strongly-Uniform Slicewise Polynomial-Time Algorithm for the Embedded Planar Diameter Improvement Problem.