Time: 3:00pm Tuesday 20th May.
Location: SIT 459
Speaker: Dr. Mathias Weller
Title: A Polynomial-Time Algorithm for Outerplanar Diameter Improvement
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.