Fully Dynamic Algorithm for the Steiner Tree Problem in Planar Graphs

In this paper, we propose a fully dynamic algorithm for the Steiner tree problem in a planar graph. We consider an undirected weighted planar graph
$G=(V, E)$
with positive real edge weights and a sequence of updates comprising of edge insertions and deletions. The goal is to maintain a Steiner tree (on the terminals) which is a good approximation of the minimum Steiner tree of the updated graph. We show that the proposed fully dynamic algorithm maintains a
$(2+\epsilon)$
approximate Steiner tree in
$\tilde{O}(\vert S\vert ^{2}\sqrt{n}+\vert S\vert D+n)$
worst case update time where the symbols have usual meanings. The update time reduces to
$O(n(\epsilon^{\prime})^{-2})$
in a special case.