# A polynomial-time algorithm for Outerplanar Diameter Improvement

1 GALaC - LRI - Graphes, Algorithmes et Combinatoire (LRI)
LRI - Laboratoire de Recherche en Informatique
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Document type :
Journal articles
Domain :

Cited literature [26 references]

https://hal.inria.fr/hal-01592242
Contributor : Nathann Cohen <>
Submitted on : Friday, September 22, 2017 - 9:34:52 PM
Last modification on : Thursday, July 8, 2021 - 3:50:26 AM
Long-term archiving on: : Saturday, December 23, 2017 - 2:28:17 PM

### File

Outerplanar-JCSS-revised.pdf
Files produced by the author(s)

### Citation

Nathann Cohen, Daniel Gonçalves, Eun Jung Kim, Christophe Paul, Ignasi Sau Valls, et al.. A polynomial-time algorithm for Outerplanar Diameter Improvement. Journal of Computer and System Sciences, Elsevier, 2017, 89, pp.315 - 327. ⟨10.1016/j.jcss.2017.05.016⟩. ⟨hal-01592242⟩

Record views