Dynamic upward planarity testing of single source embedded digraphs

In this paper, we present a dynamic algorithm that checks if a single-source embedded digraph is upward planar in the presence of edge insertions and edge deletions without changing the embedding of the digraph. We show that it can be checked in O(log n) amortized time whether the updated graph is a single-source upward planar digraph with a fixed external face.