A polynomial-time algorithm for outerplanar diameter improvement

Nathann Cohen, Daniel Gonçalves, Eunjung Kim, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos, Mathias Weller

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationComputer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings
EditorsLev D. Beklemishev, Daniil V. Musatov, Daniil V. Musatov
PublisherSpringer Verlag
Number of pages20
ISBN (Print)9783319202969
StatePublished - 2015
Event10th International Computer Science Symposium in Russia, CSR 2015 - Listvyanka, Russian Federation
Duration: Jul 13 2015Jul 17 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference10th International Computer Science Symposium in Russia, CSR 2015
Country/TerritoryRussian Federation


  • Completion problems
  • Diameter improvement
  • Dynamic programming
  • Outerplanar graphs
  • Polynomial-time algorithms

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'A polynomial-time algorithm for outerplanar diameter improvement'. Together they form a unique fingerprint.

Cite this