@inproceedings{7a7b6f0b8b3b4f52911991ec85844f5c,

title = "A polynomial-time algorithm for outerplanar diameter improvement",

abstract = "The Outerplanar Diameter Improvement problem asks, given a graph G and an integer D, whether it is possible to add edges to G in a way that the resulting graph is outerplanar and has diameter at most D. We provide a dynamic programming algorithm that solves this problem in polynomial time. Outerplanar Diameter Improvement demonstrates several structural analogues to the celebrated and challenging Planar Diameter Improvement problem, where the resulting graph should, instead, be planar. The complexity status of this latter problem is open.",

keywords = "Completion problems, Diameter improvement, Dynamic programming, Outerplanar graphs, Polynomial-time algorithms",

author = "Nathann Cohen and Daniel Gon{\c c}alves and Eunjung Kim and Christophe Paul and Ignasi Sau and Thilikos, {Dimitrios M.} and Mathias Weller",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 10th International Computer Science Symposium in Russia, CSR 2015 ; Conference date: 13-07-2015 Through 17-07-2015",

year = "2015",

doi = "10.1007/978-3-319-20297-6_9",

language = "English (US)",

isbn = "9783319202969",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "123--142",

editor = "Beklemishev, {Lev D.} and Musatov, {Daniil V.} and Musatov, {Daniil V.}",

booktitle = "Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings",

}